动态数组

• 全局变量

private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;

size用来保存数组内部已经使用的容量，elements是用于存储数据的容器，size<=elemnets.length，DEFAULT_CAPACITY是常量，表示容器初始化时的大小

• 初始化

public ArrayList(int capacity) {
    capacity = (capacity <= DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
    elements = (E[]) new Object[capacity];
}

如果capacity<=DEFAULT_CAPACITY，就初始化容器为默认大小

• 获取指定位置的值

    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

直接通过index获取，所有的通过索引操作elements时都需要对index进行合法性校验

• index合法性校验

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            indexOutOfBoundException(index);
        }

    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            indexOutOfBoundException(index);
        }
    }

正常的校验范围时不能<0，index不能>=size，site是从1开始递增的，比如set()时不能修改size值，site此时为null，修改会越界，但是add操作时index可以=size

• 在指定位置添加元素

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);

        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

在index位置添加元素时，index位置和index后的位置元素的索引位置都需要+1，也就是index位置后的元素都需要向后移动一个位置
移动元素位置需要从后移动，如果从index位置开始移动会覆盖掉index+1位置的值
添加新元素后site+1

• 修改指定位置的值

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elements[index];
        elements[index] = element;
        return oldValue;
    }

• 找出元素在数组中的索引位置

    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

element可以为null，为null时查找数组中第一个为null的位置，for()循环不需要循环elements.length，只需要size位置就可以
element不为null时，循环查找数组，elements使用了范型数组，判断element是否在elments时，比较需要使用equals

• 删除index位置元素

    public E remove(int index) {
        rangeCheck(index);

        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }

删除时需要从index+1位置开始向前移动一个位置
最后size位置的元素一定设置为null，不然对象引用可能会造成泄漏，即不能访问，但又无法被垃圾回收

• 数组扩容

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity > capacity) return;

        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

capacity是size+1，elements.length>capacity时不需要扩容
扩容为原来容量的1.5倍，使用>>1运算