简介

ArrayList是Java中对表ADT的一种可增长数组实现。
通过数组索引使其执行get(获取某索引对应的元素)和set(替换某索引对应的元素)效率高；而执行add(在某处添加元素)和remove(移除某处元素)效率较低（对应元素后的所有元素的位置都需要后推或前移），除非是对末端元素的操作。

成员变量

默认初始化容量为10。

private static final int DEFAULT_CAPACITY = 10;

用于空实例的共享空数组实例

private static final Object[] EMPTY_ELEMENTDATA = {};

用于默认大小的空实例的共享空数组实例。用于添加第一个元素时判断数组需要扩充多少。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

用于存储ArrayList元素的缓冲数组。ArrayList的容量(capacity)就是该缓冲数组的大小(size)。任何elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA形式的空ArrayLis的容量在第一个元素添加进来后都会扩充为DEFAULT_CAPACITY。

transient Object[] elementData;

ArrayList的大小(size)，指的是ArrayList中包含的元素的个数。

private int size;

容量（capacity）指ArrayList最大能存放多少个元素。
大小（size）指ArrayList当前存储的元素的个数。

初始化一个ArrayList

ArrayList提供了三种构造方式。

无参构造
构造一个空的ArrayList，容量为10。

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

API使用

add(Object obj)

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

add()方法主要有三个任务。

确定容量，并将修改数+1。（modCount，表示对该集合的操作次数。）

ensureCapacityInternal(size + 1);  // Increments modCount!!

添加新元素

elementData[size++] = e;

返回true

 return true;

其中确定容量的操作是add()方法的核心。详细步骤如下：

将集合当前的大小+1作为最小容量(minCapacity)传入ensureCapacityInternal()方法。
调用int calculateCapacity(Object[] elementData, int minCapacity)方法，计算集合扩容后的容量。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

首先判断当前缓冲数组是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA类型，如果是，则调用Math.max(DEFAULT_CAPACITY, minCapacity);方法在默认容量（10）与最小容量(minCapacity)两者之间取较大者作为缓冲数组的容量。
如果不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA类型则直接使用最小容量作为数组扩容后的容量。

调用private void ensureExplicitCapacity(int minCapacity)方法。

private void ensureExplicitCapacity(int minCapacity) {
        //累加一次修改数
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity); //该方法为扩容操作的具体实现
    }

调用private void grow(int minCapacity)方法为数组扩容。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; //获取当前数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1); //将数组长度增加原来长度的一半
        if (newCapacity - minCapacity < 0) 
            newCapacity = minCapacity; // 如果增加长度后仍小于新增元素后的实际大小，则使用实际大小作为新容量。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity); //将原数组复制到扩容后的新数组中。
    }

ArrayList新增元素的实际操作是将内部的缓冲数组复制到更大容量的新数组中，该操作是使用Arrays.copyof()实现的

remove(Object obj)

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

remove()方法有两步主要操作

使用for循环遍历缓冲数组elementData，找到需要删除的元素的下标。
若需要删除null元素，则使用elementData[index] == null；若不为null，则使用o.equals(elementData[index])。
调用fastRemove()方法删除元素。

其中fastRemove()方法为实现删除的关键操作

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

将操作数(modCount)加1；
计算要移动的元素数量。
调用System.arraycopy()得到除去指定删除元素后的新数组。
这步操作是将被删除元素后的所有元素，从被删除元素的下标位置开始复制，得到新数组。
上一步复制操作结束后，数组最后一个元素会重复，通过elementData[--size] = null;删除它，让GC回收。
删除1
执行System.arraycopy()前
执行System.arraycopy()前后
此时I元素已被它后面的五个元素替换，并在最后多处来一个末尾元素。
elementData[--size] = null; 多出的末尾元素被去除，得到新数组