大家天天在用List，ArrayList一般來講應該是程序員用的最多的集合類了。

我們今天研究一下ArrayList。

總體來講，從底層數據結構或者源碼的角度看，List比Map或者Set要簡單。

底層數據結構

ArryList其實就是可變長數組。

初始化的時候，可以指定容量，不指定容量的話，ArrayList被初始化為空數組，首次存入數據的時候才進行容量初始化，初始化最小容量為10。

ArrayList的容量控制

每次存入數據到ArrayList的時候，首先檢查容量：

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}

如果ArrayList容量不能滿足本次數據存儲的要求的話，調用grow方法擴容：

private void grow(int minCapacity) {// overflow-conscious codeint 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);}

grow方法首先檢查原容量擴容1.5倍是否能滿足要求，能滿足則擴容到原來的1.5倍，否則擴容到能滿足數據存入要求的容量。

擴容后調用Arrays.copyOf(elementData, newCapacity)把舊的數據copy到擴容后的新數組。Arrays.copyof方法其實也是調用System.arraycopy方法完成copy。

數據存入

調用add（E e）方法在ArrayList尾部追加數據。
調用addAll(Collection<? extends E> c)在ArrayList尾部追加集合c中的所有數據。

ArrayList支持追加數據到其指定位置（通過調用方法add(int index, E element)），底層通過調用System.arraycopy方法實現。

研究ArrayList源碼會發現其中大量使用System.arraycopy方法，所以，雖然ArrayList其實就是數組操作，但是性能也不至于太差。

獲取數據

使用ArrayList的時候我們一般會有兩種獲取數據的需求，一種就是獲取指定位置的數據，通過get(int index)方法獲取，因為ArrayList其實就是數組，所以，獲取指定位置的數據效率非常高，時間復雜度為O(1)。

另外一種就是判斷是否包含某一數據，調用contains(Object o)方法：

public boolean contains(Object o) {return indexOf(o) >= 0;}public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}

其實猜都能猜到他必須要遍歷數組了，所以效率不會太高。

其他

讀源碼的目的除了從底層徹底了解其工作原理之外，還有一個重要的目的就是學習最最NB的JAVA程序員的編碼思想和習慣。

比如釋放內存：

   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}

比如代碼重用：

    public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}

retainAll是只保留參數集合中的數據，removeAll則正好相反，移除參數集合中的數據，兩個方法目的正好相反，則通過調用batchRemove、傳遞complement為true或false達到目的。

值得每個尤其是新手程序員認真學習。

晚安！