image.png

List接口的可调整大小的数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现List接口之外，这个类还提供了一些方法来操纵数组的大小，数组在内部用于存储列表。（这个类大致相当于Vector，只是它是不同步的。）

size、isEmpty、get、set、iterator和listIterator操作以固定时间运行。add操作以摊销的固定时间运行，也就是说，添加n个元素需要O（n）时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实现相比，常量因子较低。

每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它总是至少和列表大小一样大。当元素添加到ArrayList时，它的容量会自动增长。除了添加一个元素具有固定的摊余时间成本这一事实之外，增长策略的细节没有被指定。

在使用ensureCapacity操作添加大量元素之前，应用程序可以增加ArrayList实例的容量。这可能会减少增量重新分配的数量。

请注意，此实现不是同步的。如果多个线程同时访问<tt>ArrayList</tt>实例，并且至少有一个线程在结构上修改了该列表，则必须在外部对其进行同步。（结构修改是添加或删除一个或多个元素，或显式调整背景数组大小的任何操作；仅设置元素的值不是结构修改。）

如果不存在这样的对象，则应该使用Collections.synchronizedList方法。这最好在创建时完成使用，以防止意外对列表的非同步访问：

List list = Collections.synchronizedList(new ArrayList(...));

此类的{@link #iterator() iterator} and {@link #listIterator(int) listIterator} 方法返回的迭代器是"快速失败"：如果在创建迭代器后的任何时间列表在结构上进行了修改，除了通过迭代器自己的{@link ListIterator#remove() remove}或{@link ListIterator#add(Object) add}之外方法，迭代器将抛出ConcurrentModificationException异常。因此，在面对并发修改时，迭代器会快速而干净地失败，而不是冒着在将来不确定的时间出现任意的、不确定的行为的风险。

注意，不能保证迭代器的快速故障行为，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬保证。失败的快速迭代器会尽最大努力抛出{@code ConcurrentModificationException}。因此，编写一个依赖于此异常的程序是错误的：迭代器的fail fast行为应该只用于检测错误。

1. 添加一个元素

将指定的元素追加到此列表的末尾。

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

1.1 计算容量

先判断是否是通过new ArrayList()实例化的对象，如果是第一次添加元素会根据元素数量大小进行容量初始化，默认分配10个元素，如果摄入的元素数量大于10，则不适用默认大小，而是使用实际情况的容量大小，如果不是通过new ArrayList()实例化时，直接返回minCapacity：

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

1.2 自动扩容

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

自动扩容的依据是，如果是通过new ArrayList()实例化，一个个添加元素时，除了添加第一个元素初始化数组大小为10外，第一次扩容是在添加第11个元素的时候，而不是通过new ArrayList实例化添加元素时，每次添加元素都会进行一次扩容。

1.3 扩容策略

增加容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。

    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);
    }

从代码中总结一下：
先获取当前数组长度大小，新的数组长度计算为老的数组长度加上老的数组长度除以2，然后跟最小需要容量比较，如果大于最小长度容量，就使用系统计算出的新容量，否则直接使用最小长度容量，如果新容量大于最大容量大小则调用hugeCapacity方法，重新设置新容量。
最后调用Arrays.copyOf(elementData, newCapacity)复杂原有数组元素并扩容到新的数组大小。

2. EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别

EMPTY_ELEMENTDATA：用于空实例的共享空数组实例。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：用于默认大小的空实例的共享空数组实例。我们将其与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时要充气多少。

3. 属性modCount

此列表在结构上被修改的次数。结构修改是指那些改变列表大小的修改，或者以某种方式扰乱列表，使得正在进行的迭代可能产生不正确的结果。

此字段由迭代器和listIterator方法返回的迭代器和列表迭代器实现使用。如果此字段的值意外更改，迭代器（或列表迭代器）将抛出ConcurrentModificationException以响应next、remove、previous、set或add操作。这提供了快速失败的行为，而不是在迭代过程中面对并发修改时的不确定性行为。

子类使用此字段是可选的。如果子类希望提供fail-fast迭代器（和list迭代器），那么它只需在add（int，E）和remove（int）方法（以及它重写的任何其他方法，这些方法会导致对list的结构修改）中增加这个字段。对add（int，E）或remove（int）的单个调用只能向该字段添加一个，否则迭代器（和列表迭代器）将抛出虚假的ConcurrentModificationExceptions。如果实现不希望提供fail fast迭代器，则可以忽略此字段。