java 手撕arrayList

public class ArrayList {

//申明存储变量的容器
E[] elements;

//定义默认的容器大小
private static final int INIT_CAPACITY = 10;

//待添加元素位置的索引 or 容器中元素的个数
private int size;

//当前数组容量
private int capacity;

//创建默认容器
public ArrayList(){

    //调用有一个 int 类型参数的构造方法
    this(INIT_CAPACITY);
}

//创建指定容量的容器
public ArrayList(int capacity){

    //this调用类中声明的容器、初始化
    this.elements = (E[]) new Object[capacity];

    this.capacity = capacity;

}

//判断容器是否为空
public boolean isEmpty(){
    return size==0;
}

//返回当前容器中的元素个数
public int getSize(){
    return size;
}

//存储元素
public void add(E e) {

    addLast(e);
}

//添加元素到指定的位置上
public void add(E e, int index) throws IllegalAccessException {

    //验证 index
    checkIndex(index);

    //判断是否扩容
    if (size==capacity){
        grow(capacity*2);
    }

    // index 后面的数据向后移一位
    for (int i=size;i>index;i--){

        elements[i] = elements[i-1];
    }

    //在 index 插入数据
    elements[index] = e;

    //维护size
    size++;

}

//删除指定索引的元素
public E remove(int index) throws IllegalAccessException {

    //判断 index 合法性
    checkIndex(index);

    //存储要删除的元素以便返回
    E ret = elements[index];

    //覆盖指定索引的元素
    for (int i=index;i<size-1;i++){

        elements[i] = elements[i+1];
    }

    //维护size
    size--;

    //多余元素为null
    elements[size] = null;

    //如果数组元素数量等于数组容量的一半则缩容
    if (size==capacity/4 && capacity/2!=0){
        grow(capacity/2);
    }

    //返回删除元素
    return ret;
}

//删除指定元素
public void remove(Object e) throws IllegalAccessException {

    //获取指定元素下标
    int index = indexOf((E)e);

    //若没找到指定元素则抛出异常
    if (index == -1){
        throw new IllegalAccessException("element e: " + e + " is not found");
    }

    //利用索引删除指定元素
    remove(index);
}

//删除首元素
public void removeFirst() throws IllegalAccessException {

    //利用索引删除首元素
    remove(0);
}

//删除尾元素
public E removeLast(){

    //存储要删除的元素
    E ret = elements[size-1];

    //删除元素，维护size
    elements[--size] = null;

    //如果数组元素数量等于数组容量的一半则缩容
    if (size==capacity/4&&capacity/2!=0){
        grow(capacity/2);
    }

    //返回要删除的元素
    return ret;

}

//根据元素返回元素下标
public int indexOf(E e){

    if (e == null){
        for (int i=0;i<size;i++){
            if (elements[i] == null){
                return i;
            }
        }
    }else{
        for (int i=0;i<size;i++){
            if (e.equals(elements[i])){
                return i;
            }
        }
    }

    //没找到元素返回 -1
    return -1;
}

//判定 index 的合法性
private void checkIndex(int index) throws IllegalAccessException {

    if (index<0 || index>size){
        throw new IllegalAccessException("index out of bounds index:" + index);
    }
}

//扩容/缩容
private void grow(int newCapacity){

    //创建新数组
    E[] newElements = (E[]) new Object[newCapacity];

    //把原来的数组值赋给新数组
    for (int i=0;i<size;i++){
        newElements[i] = elements[i];
    }

    //容器指向新数组
    this.elements = newElements;

    //维护数组容量
    this.capacity = newCapacity;
}


//添加首元素
public void addFirst(E e) throws IllegalAccessException {

    add(e, 0);
}


//添加尾元素
public void addLast(E e){

    //判断是否扩容
    if (size==capacity){
        grow(capacity*2);
    }

    //存元素
    elements[size] = e;

    //更新待添加元素位置的索引
    size++;

}

//判断集合中是否存在e元素
public boolean contains(E e){

    return indexOf(e) != -1;
}

//通过下标返回元素
public E getElement(int index){

    return elements[index];
}

//通过下标存储元素
public E setElement(E e, int index){

    elements[index] = e;

    return e;
}

@Override
//定义 Arraylist 输出格式的方法
public String toString(){

    StringBuilder str = new StringBuilder();
    str.append("size: " + size + " [");

    for (int i=0;i<size;i++){
        str.append(elements[i]);
        if (i!=size-1){
            str.append(", ");
        }
    }
    str.append("] capacity: " + capacity);
    return str.toString();

}

}