概述

ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。

size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
为追求效率，ArrayList没有实现同步(synchronized)，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

ArrayList的实现

底层数据结构

  1.     /**
  2.      * The array buffer into which the elements of the ArrayList are stored.
  3.      * The capacity of the ArrayList is the length of this array buffer. Any
  4.      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  5.      * will be expanded to DEFAULT_CAPACITY when the first element is added.
  6.      */
  7.     transient Object[] elementData; // non-private to simplify nested class access
  9.     /**
  10.      * The size of the ArrayList (the number of elements it contains).
  11.      *
  12.      * @serial
  13.      */
  14.     private int size;
  15. 复制代码

构造函数

  1.     /**
  2.      * Constructs an empty list with the specified initial capacity.
  3.      *
  4.      * @param  initialCapacity  the initial capacity of the list
  5.      * @throws IllegalArgumentException if the specified initial capacity
  6.      *         is negative
  7.      */
  8.     public ArrayList(int initialCapacity) {
  9.         if (initialCapacity > 0) {
  10.             this.elementData = new Object[initialCapacity];
  11.         } else if (initialCapacity == 0) {
  12.             this.elementData = EMPTY_ELEMENTDATA;
  13.         } else {
  14.             throw new IllegalArgumentException("Illegal Capacity: "+
  15.                                                initialCapacity);
  16.         }
  17.     }
  19.     /**
  20.      * Constructs an empty list with an initial capacity of ten.
  21.      */
  22.     public ArrayList() {
  23.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  24.     }
  26.     /**
  27.      * Constructs a list containing the elements of the specified
  28.      * collection, in the order they are returned by the collection's
  29.      * iterator.
  30.      *
  31.      * @param c the collection whose elements are to be placed into this list
  32.      * @throws NullPointerException if the specified collection is null
  33.      */
  34.     public ArrayList(Collection<? extends E> c) {
  35.         elementData = c.toArray();
  36.         if ((size = elementData.length) != 0) {
  37.             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  38.             if (elementData.getClass() != Object[].class)
  39.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  40.         } else {
  41.             // replace with empty array.
  42.             this.elementData = EMPTY_ELEMENTDATA;
  43.         }
  44.     }
  45. 复制代码

自动扩容

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

  1.     /**
  2.      * Increases the capacity of this <tt>ArrayList</tt> instance, if
  3.      * necessary, to ensure that it can hold at least the number of elements
  4.      * specified by the minimum capacity argument.
  5.      *
  6.      * @param   minCapacity   the desired minimum capacity
  7.      */
  8.     public void ensureCapacity(int minCapacity) {
  9.         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
  10.             // any size if not default element table
  11.             ? 0
  12.             // larger than default for default empty table. It's already
  13.             // supposed to be at default size.
  14.             : DEFAULT_CAPACITY;
  16.         if (minCapacity > minExpand) {
  17.             ensureExplicitCapacity(minCapacity);
  18.         }
  19.     }
  21.     private void ensureCapacityInternal(int minCapacity) {
  22.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  23.             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  24.         }
  26.         ensureExplicitCapacity(minCapacity);
  27.     }
  29.     private void ensureExplicitCapacity(int minCapacity) {
  30.         modCount++;
  32.         // overflow-conscious code
  33.         if (minCapacity - elementData.length > 0)
  34.             grow(minCapacity);
  35.     }
  37.     /**
  38.      * The maximum size of array to allocate.
  39.      * Some VMs reserve some header words in an array.
  40.      * Attempts to allocate larger arrays may result in
  41.      * OutOfMemoryError: Requested array size exceeds VM limit
  42.      */
  43.     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  45.     /**
  46.      * Increases the capacity to ensure that it can hold at least the
  47.      * number of elements specified by the minimum capacity argument.
  48.      *
  49.      * @param minCapacity the desired minimum capacity
  50.      */
  51.     private void grow(int minCapacity) {
  52.         // overflow-conscious code
  53.         int oldCapacity = elementData.length;
  54.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  55.         if (newCapacity - minCapacity < 0)
  56.             newCapacity = minCapacity;
  57.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  58.             newCapacity = hugeCapacity(minCapacity);
  59.         // minCapacity is usually close to size, so this is a win:
  60.         elementData = Arrays.copyOf(elementData, newCapacity);
  61.     }
  63.     private static int hugeCapacity(int minCapacity) {
  64.         if (minCapacity < 0) // overflow
  65.             throw new OutOfMemoryError();
  66.         return (minCapacity > MAX_ARRAY_SIZE) ?
  67.             Integer.MAX_VALUE :
  68.             MAX_ARRAY_SIZE;
  69.     }
  70. 复制代码

image.png

add(), addAll()

跟C++的vector不同，ArrayList没有push_back()方法，对应的方法是add(E e)，ArrayList也没有insert()方法，对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

  1.     /**
  2.      * Appends the specified element to the end of this list.
  3.      *
  4.      * @param e element to be appended to this list
  5.      * @return <tt>true</tt> (as specified by {@link Collection#add})
  6.      */
  7.     public boolean add(E e) {
  8.         ensureCapacityInternal(size + 1);  // Increments modCount!!
  9.         elementData[size++] = e;
  10.         return true;
  11.     }
  13.     /**
  14.      * Inserts the specified element at the specified position in this
  15.      * list. Shifts the element currently at that position (if any) and
  16.      * any subsequent elements to the right (adds one to their indices).
  17.      *
  18.      * @param index index at which the specified element is to be inserted
  19.      * @param element element to be inserted
  20.      * @throws IndexOutOfBoundsException {@inheritDoc}
  21.      */
  22.     public void add(int index, E element) {
  23.         rangeCheckForAdd(index);
  25.         ensureCapacityInternal(size + 1);  // Increments modCount!!
  26.         System.arraycopy(elementData, index, elementData, index + 1,
  27.                          size - index);
  28.         elementData[index] = element;
  29.         size++;
  30.     }
  31. 复制代码

image.png

add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
addAll()方法能够一次添加多个元素，根据位置不同也有两个版本，一个是在末尾添加的addAll(Collection<? extends E> c)方法，一个是从指定位置开始插入的addAll(int index, Collection<? extends E> c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。

  1.     /**
  2.      * Appends all of the elements in the specified collection to the end of
  3.      * this list, in the order that they are returned by the
  4.      * specified collection's Iterator.  The behavior of this operation is
  5.      * undefined if the specified collection is modified while the operation
  6.      * is in progress.  (This implies that the behavior of this call is
  7.      * undefined if the specified collection is this list, and this
  8.      * list is nonempty.)
  9.      *
  10.      * @param c collection containing elements to be added to this list
  11.      * @return <tt>true</tt> if this list changed as a result of the call
  12.      * @throws NullPointerException if the specified collection is null
  13.      */
  14.     public boolean addAll(Collection<? extends E> c) {
  15.         Object[] a = c.toArray();
  16.         int numNew = a.length;
  17.         ensureCapacityInternal(size + numNew);  // Increments modCount
  18.         System.arraycopy(a, 0, elementData, size, numNew);
  19.         size += numNew;
  20.         return numNew != 0;
  21.     }
  23.     /**
  24.      * Inserts all of the elements in the specified collection into this
  25.      * list, starting at the specified position.  Shifts the element
  26.      * currently at that position (if any) and any subsequent elements to
  27.      * the right (increases their indices).  The new elements will appear
  28.      * in the list in the order that they are returned by the
  29.      * specified collection's iterator.
  30.      *
  31.      * @param index index at which to insert the first element from the
  32.      *              specified collection
  33.      * @param c collection containing elements to be added to this list
  34.      * @return <tt>true</tt> if this list changed as a result of the call
  35.      * @throws IndexOutOfBoundsException {@inheritDoc}
  36.      * @throws NullPointerException if the specified collection is null
  37.      */
  38.     public boolean addAll(int index, Collection<? extends E> c) {
  39.         rangeCheckForAdd(index);
  41.         Object[] a = c.toArray();
  42.         int numNew = a.length;
  43.         ensureCapacityInternal(size + numNew);  // Increments modCount
  45.         int numMoved = size - index;
  46.         if (numMoved > 0)
  47.             System.arraycopy(elementData, index, elementData, index + numNew,
  48.                              numMoved);
  50.         System.arraycopy(a, 0, elementData, index, numNew);
  51.         size += numNew;
  52.         return numNew != 0;
  53.     }
  54. 复制代码

set()

既然底层是一个数组ArrayList的set()方法也就变得非常简单，直接对数组的指定位置赋值即可。

  1. public E set(int index, E element) {
  2.     rangeCheck(index);//下标越界检查
  3.     E oldValue = elementData(index);
  4.     elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
  5.     return oldValue;
  6. }
  7. 复制代码

get()

get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。

  1. public E get(int index) {
  2.     rangeCheck(index);
  3.     return (E) elementData[index];//注意类型转换
  4. }
  5. 复制代码

remove()

remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。

  1. public E remove(int index) {
  2.     rangeCheck(index);
  3.     modCount++;
  4.     E oldValue = elementData(index);
  5.     int numMoved = size - index - 1;
  6.     if (numMoved > 0)
  7.         System.arraycopy(elementData, index+1, elementData, index, numMoved);
  8.     elementData[--size] = null; //清除该位置的引用，让GC起作用
  9.     return oldValue;
  10. }
  11. 复制代码

关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

trimToSize()

ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下:

  1.     /**
  2.      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
  3.      * list's current size.  An application can use this operation to minimize
  4.      * the storage of an <tt>ArrayList</tt> instance.
  5.      */
  6.     public void trimToSize() {
  7.         modCount++;
  8.         if (size < elementData.length) {
  9.             elementData = (size == 0)
  10.               ? EMPTY_ELEMENTDATA
  11.               : Arrays.copyOf(elementData, size);
  12.         }
  13.     }
  14. 复制代码

indexOf(), lastIndexOf()

获取元素的第一次出现的index:

  1. /**
  2.      * Returns the index of the first occurrence of the specified element
  3.      * in this list, or -1 if this list does not contain the element.
  4.      * More formally, returns the lowest index <tt>i</tt> such that
  5.      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
  6.      * or -1 if there is no such index.
  7.      */
  8.     public int indexOf(Object o) {
  9.         if (o == null) {
  10.             for (int i = 0; i < size; i++)
  11.                 if (elementData[i]==null)
  12.                     return i;
  13.         } else {
  14.             for (int i = 0; i < size; i++)
  15.                 if (o.equals(elementData[i]))
  16.                     return i;
  17.         }
  18.         return -1;
  19.     }
  20. 复制代码

获取元素的最后一次出现的index:

  1.     /**
  2.      * Returns the index of the last occurrence of the specified element
  3.      * in this list, or -1 if this list does not contain the element.
  4.      * More formally, returns the highest index <tt>i</tt> such that
  5.      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
  6.      * or -1 if there is no such index.
  7.      */
  8.     public int lastIndexOf(Object o) {
  9.         if (o == null) {
  10.             for (int i = size-1; i >= 0; i--)
  11.                 if (elementData[i]==null)
  12.                     return i;
  13.         } else {
  14.             for (int i = size-1; i >= 0; i--)
  15.                 if (o.equals(elementData[i]))
  16.                     return i;
  17.         }
  18.         return -1;
  19.     }
  20. 复制代码

Fail-Fast机制:

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。