Java ArrayList源碼剖析
總體介紹
ArrayList實現了List接口，是順序容器，即元素存放的數據與放進去的順序相同，允許放入null元素，底層通過數組實現。除該類未實現同步外，其余跟Vector大致相同。每個ArrayList都有一個容量（capacity），表示底層數組的實際大小，容器內存儲元素的個數不能多于當前容量。當向容器中添加元素時，如果容量不足，容器會自動增大底層數組的大小。前面已經提過，Java泛型只是編譯器提供的語法糖，所以這里的數組是一個Object數組，以便能夠容納任何類型的對象。
size(), isEmpty(), get(), set()方法均能在常數時間內完成，add()方法的時間開銷跟插入位置有關，addAll()方法的時間開銷跟添加元素的個數成正比。其余方法大都是線性時間。
為追求效率，ArrayList沒有實現同步（synchronized），如果需要多個線程并發訪問，用戶可以手動同步，也可使用Vector替代。
方法剖析
set()
既然底層是一個數組ArrayList的set()方法也就變得非常簡單，直接對數組的指定位置賦值即可。
public E set(int index, E element) {
rangeCheck(index);//下標越界檢查
E oldValue = elementData(index);
elementData[index] = element;//賦值到指定位置，復制的僅僅是引用
return oldValue;
}
get()
get()方法同樣很簡單，唯一要注意的是由于底層數組是Object[]，得到元素后需要進行類型轉換。
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//注意類型轉換
}
add()
跟C++ 的vector不同，ArrayList沒有bush_back()方法，對應的方法是add(E e)，ArrayList也沒有insert()方法，對應的方法是add(int index, E e)。這兩個方法都是向容器中添加新元素，這可能會導致capacity不足，因此在添加元素之前，都需要進行剩余空間檢查，如果需要則自動擴容。擴容操作最終是通過grow()方法完成的。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//原來的3倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);//擴展空間并復制
}
由于Java GC自動管理了內存，這里也就不需要考慮源數組釋放的問題。
空間的問題解決后，插入過程就顯得非常簡單。
add(int index, E e)需要先對元素進行移動，然后完成插入操作，也就意味著該方法有著線性的時間復雜度。
addAll()
addAll()方法能夠一次添加多個元素，根據位置不同也有兩個把本，一個是在末尾添加的addAll(Collection<? extends E> c)方法，一個是從指定位置開始插入的addAll(int index, Collection<? extends E> c)方法。跟add()方法類似，在插入之前也需要進行空間檢查，如果需要則自動擴容；如果從指定位置插入，也會存在移動元素的情況。
addAll()的時間復雜度不僅跟插入元素的多少有關，也跟插入的位置相關。
remove()
remove()方法也有兩個版本，一個是remove(int index)刪除指定位置的元素，另一個是remove(Object o)刪除第一個滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程，需要將刪除點之后的元素向前移動一個位置。需要注意的是為了讓GC起作用，必須顯式的為最后一個位置賦null值。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //清除該位置的引用，讓GC起作用
return oldValue;
}
關于Java GC這里需要特別說明一下，有了垃圾收集器并不意味著一定不會有內存泄漏。對象能否被GC的依據是是否還有引用指向它，上面代碼中如果不手動賦null值，除非對應的位置被其他元素覆蓋，否則原來的對象就一直不會被回收。
來源：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/2-ArrayList.md