ArrayList是我们平时开发中最常用的集合之一，本文通过源码来解析一下ArrayList的底层实现原理。
ArrayList的构造函数很好理解，目的都是为了初始化定长数组：elementData。构造函数分为两种：
无参构造函数，也是我们使用场景最多的一种，会初始化一个空数组，然后在第一次有数据插入的时候进行扩容，第一次扩容大小为10。有参构造函数，如果在已知数据大小的时候推荐使用有参构造函数，可以通过initialCapacity参数将elementData初始化为initialCapacity大小的数组，可以避免扩容，减少资源浪费。通过阅读源码，我们可以看到，ArrayList的扩容机制是：扩容为原数组大小的1.5倍。接下来我们来看一下源码的实现。
/** 计算最小容量 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } /** 扩容的入口方法 */ private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** 扩容的核心方法 */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 扩容 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }查找数据的源码很简单，就是根据索引位置去数组里取数据，源码如下。
public E get(int index) { rangeCheck(index); return elementData(index); }对于数组(线性表)的插入方式分为两种，第一种是尾插法，第二种是在指定位置插入。我们来看一下ArrayList是如何实现这两种方法的。
尾插法 public boolean add(E e) { // 先判断是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! // 然后将待插入的元素放在线性表的尾部 elementData[size++] = e; return true; }其实尾插法实现起来很简单，第一步：检查数组是否有足够的空间插入新数据；第二步：在数组的尾部插入新数据。如下图所示。
指定位置插入 public void add(int index, E element) { rangeCheckForAdd(index); // 先判断是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! // 将指定位置后的所有元素后移 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 在指定位置插入数据 elementData[index] = element; size++; }这种插入方法相比尾插法稍微复杂一点，第一步：判断是否有足够的空间插入新数据；第二步：将指定位置后的所有数据后移；第三步：在指定位置插入元素。这种插入方法操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。在日常开发中，若非所需，我们应当尽量避免在大集合中调用第二种插入方法。
不同于插入操作，ArrayList没有无参删除方法。所以其只能删除指定位置的元素或删除指定元素，这样就无法避免移动元素（除非从元素序列的尾部删除）。
删除指定位置元素 public E remove(int index) { rangeCheck(index); modCount++; // 返回已删除的元素 E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) // 将 index + 1 及之后的元素向前移动一位，覆盖被删除值 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 将最后一个元素置空，并将 size 值减1 elementData[--size] = null; // clear to let GC do its work return oldValue; } 删除指定元素 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; } } // 如果数组里没有这个数据，返回false return false; } 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 } 遍历时删除对于遍历时删除数据的操作应该尽量避免，如果需要在遍历的过程中删除数据，正确的做法使用迭代器提供的删除方法，而不是直接删除。至于为什么，我们可以在源码中寻找到答案：
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { // 这里是重点，并发删除检查 checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); // 省略中间代码 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }ArrayList实现了 RandomAccess 接口（该接口是个标志性接口），表明它具有随机访问的能力。ArrayList 底层基于数组实现，所以它可在常数阶的时间内完成随机访问，效率很高。对 ArrayList 进行遍历时，推荐下面这种方式：
for (int i = 0; i < list.size(); i++) { list.get(i); }至于为什么不推荐foreach是因为foreach最终会变成迭代器遍历。
考虑一种情况，我们通常会往ArrayList中添加大量元素，然后移除大量元素，此时底层的数组就会有很多空闲空间浪费掉，因为ArrayList没有自动缩容机制，这些空间又不能自动释放掉，但是ArrayList提供了一个方法来解决这个问题：
/** 将数组容量缩小至元素数量 */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }以上内容通过对ArrayList的构造方法、扩容机制、遍历、添加和删除元素等常用API结合源码做了解读，看起来也不难。ArrayList是最常用的集合之一，也是高频面试题，通过本文可以对ArrayList有一个更全面、深刻的理解。
