知識星球（點選上方公眾號，可快速關註）
來源：Yikun，
yikun.github.io/2015/04/04/Java-ArrayList工作原理及實現/
1. 概述
關於Java集合的小抄中是這樣描述的：
http://calvin1978.blogcn.com/articles/collection.html
以陣列實現。節約空間，但陣列有容量限制。超出限制時會增加50%容量，用System.arraycopy()複製到新的陣列，因此最好能給出陣列大小的預估值。預設第一次插入元素時建立大小為10的陣列。
按陣列下標訪問元素—get(i)/set(i,e) 的效能很高，這是陣列的基本優勢。
直接在陣列末尾加入元素—add(e)的效能也高，但如果按下標插入、刪除元素—add(i,e), remove(i), remove(e)，則要用System.arraycopy()來移動部分受影響的元素，效能就變差了，這是基本劣勢。
然後再來學習一下官方檔案：
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
ArrayList是一個相對來說比較簡單的資料結構，最重要的一點就是它的自動擴容，可以認為就是我們常說的“動態陣列”。
來看一段簡單的程式碼：
ArrayList
list = new ArrayList (); list.add(“語文: 99”);
list.add(“數學: 98”);
list.add(“英語: 100”);
list.remove(0);
在執行這四條陳述句時，是這麼變化的：
其中，add操作可以理解為直接將陣列的內容置位，remove操作可以理解為刪除index為0的節點，並將後面元素移到0處。
2. add函式
當我們在ArrayList中增加元素的時候，會使用add函式。他會將元素放到末尾。具體實現如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
我們可以看到他的實現其實最核心的內容就是ensureCapacityInternal。這個函式其實就是自動擴容機制的核心。我們依次來看一下他的具體實現
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(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;
// 擴充套件為原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴為1.5倍還不滿足需求，直接擴為需求值
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);
}
也就是說，當增加資料的時候，如果ArrayList的大小已經不滿足需求時，那麼就將陣列變為原長度的1.5倍，之後的操作就是把老的陣列拷到新的陣列裡面。例如，預設的陣列大小是10，也就是說當我們add10個元素之後，再進行一次add時，就會發生自動擴容，陣列長度由10變為了15具體情況如下所示：
3 set和get函式
Array的put和get函式就比較簡單了，先做index檢查，然後執行賦值或訪問操作：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
4 remove函式
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);
// 把最後的置null
elementData[–size] = null; // clear to let GC do its work
return oldValue;
}
註釋很清楚：
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
參考資料
-
Class ArrayList
http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#add-E-
-
ArrayList其實就那麼一回事兒之原始碼淺析
http://www.cnblogs.com/dongying/p/4013271.html
-
關於ArrayList
http://my.oschina.net/tunie/blog/122530
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
