JAVA---手写ArrayList
程序员文章站
2024-03-18 11:34:52
...
JAVA—手写ArrayList
List接口
public interface List {
// 返回线性表的大小,即数据元素的个数。
public int size();
// 返回线性表中序号为 i 的数据元素
public Object get(int i);
// 如果线性表为空返回 true,否则返回 false。
public boolean isEmpty();
// 判断线性表是否包含数据元素 e
public boolean contains(Object e);
// 返回数据元素 e 在线性表中的序号
public int indexOf(Object e);
// 将数据元素 e 插入到线性表中 i 号位置
public void add(int i, Object e);
// 将数据元素 e 插入到线性表末尾
public void add(Object e);
// 将数据元素 e 插入到元素 obj 之前
public boolean addBefore(Object obj, Object e);
// 将数据元素 e 插入到元素 obj 之后
public boolean addAfter(Object obj, Object e);
// 删除线性表中序号为 i 的元素,并返回之
public Object remove(int i);
// 删除线性表中第一个与 e 相同的元素
public boolean remove(Object e);
// 替换线性表中序号为 i 的数据元素为 e,返回原数据元素
public Object replace(int i, Object e);
public Iterator iterator();
}
Iterator接口:
public interface Iterator<T> {
boolean hasNext();
T next();
}
ArrayList类
public class ArrayList implements List {
java.util.ArrayList list = new java.util.ArrayList();
private transient Object[] elementData; //数组
private int size; //数组中有效元素的个数
public ArrayList(){
this(10);
}
public ArrayList(int initialCapacity){
if (initialCapacity < 0)
throw new IllegalArgumentException("索引小于0: "+
initialCapacity);
elementData = new Object[initialCapacity];
}
@Override
public int size() {
return size;
}
@Override
public Object get(int i) {
if (i > size - 1 || i < 0)
throw new ArrayIndexOutOfBoundsException("数组越界了:" + i);
return elementData[i];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}
@Override
public int indexOf(Object e) {
if (e == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (e.equals(elementData[i]))
return i;
}
return -1;
}
@Override
public void add(int i, Object e) {
//扩容
grow();
for (int index = size - 1; index >= i; index--){
elementData[index + 1] = elementData[index];
}
elementData[i] = e;
size ++;
}
@Override
public void add(Object e) {
//扩容
grow();
elementData[size] = e;
size++;
}
@Override
public boolean addBefore(Object obj, Object e) {
return false;
}
@Override
public boolean addAfter(Object obj, Object e) {
return false;
}
@Override
public Object remove(int i) {
if (i > size - 1)
throw new RuntimeException("数组越界了:" + i);
for (int index = i; index < size - 1; index++){
elementData[index] = elementData[index + 1];
}
size--;
return elementData[i];
}
@Override
public boolean remove(Object e) {
return false;
}
@Override
public Object replace(int i, Object e) {
return null;
}
@Override
public Iterator iterator() {
return new Itr();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++){
sb.append(elementData[i] + ",");
}
if (size > 0){
//去掉最后一个逗号
sb.deleteCharAt(sb.length() - 1);
}
sb.append("]");
return sb.toString();
}
private void grow() {
//扩容
if (size == elementData.length){
//扩容1.5倍
elementData = Arrays.copyOf(elementData, size + (size >> 1));
}
}
private class Itr<T> implements Iterator <T> {
int cursor;
@Override
public boolean hasNext() {
return cursor < size;
}
@Override
public T next() {
if (cursor >= size)
throw new NoSuchElementException("没有这个元素了:" + cursor);
return (T)elementData[cursor++];
}
}
}
上一篇: java数据结构——6队列(Queue)
下一篇: 数据结构复习整理-04队列