ArrayList 和 LinkedList 原始碼分析

摘要： List 表示的就是線性表，是具有相同特性的資料元素的有限序列。它主要有兩種儲存結構，順序儲存和鏈式儲存，分別對應著 ArrayList 和 LinkedList 的實現，接下來以 jdk7 程式碼為例，對這兩種實現的核心原始碼進行分析。 1. ArrayList 原始碼分析 Arr...

List 表示的就是線性表，是具有相同特性的資料元素的有限序列。它主要有兩種儲存結構，順序儲存和鏈式儲存，分別對應著 ArrayList 和 LinkedList 的實現，接下來以 jdk7 程式碼為例，對這兩種實現的核心原始碼進行分析。

1. ArrayList 原始碼分析

ArrayList 是基於 陣列 實現的可變大小的集合，底層是一個 Object[] 陣列，可儲存包括 null 在內的所有元素，預設容量為 10。元素的新增和刪除，本質就是陣列元素的移動。

1.1 add 操作

ArrayList 內部有一個 size 成員變數，記錄集合內元素總數，add 操作的本質就是 elementData[size++] = e，為了保證插入成功，會按需對陣列進行擴容，擴容程式碼如下：

private void grow(int minCapacity) {
// 有可能會溢位
int oldCapacity = elementData.length;
// 相當於 oldCapacity+(oldCapacity/2)，擴大 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 確保新容量不小於 minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 檢查擴充的最小容量是否溢位，如果溢位值會小於 0
newCapacity = hugeCapacity(minCapacity);
// 生成一個新陣列，舊陣列沒有被引用會被垃圾回收
elementData = Arrays.copyOf(elementData, newCapacity);
}

add 操作還有一個指定位置的插入，來看具體實現（本文首發於微信公眾號： 頓悟原始碼 ，qq交流群：673986158）：

public void add(int index, E element) {
// 檢查下標是否有效
// 可能會丟擲 IndexOutOfBoundsException 異常
rangeCheckForAdd(index);
// 確保足夠的容量插入成功
ensureCapacityInternal(size + 1);// Increments modCount!!
// 把從 index 位置開始的所有元素後移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 插入新元素
elementData[index] = element;
size++; // 總數加 1
}

1.2 remove 操作

remove 分為兩種，按下標刪除和按元素刪除。按元素首先會遍歷找到匹配元素的位置下標，然後按下標進行刪除：

public E remove(int index) {
// 檢查下標位置是否有效
rangeCheck(index);
// 更新列表結構的修改次數
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 將 index 後的所有元素前移一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 釋放引用
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}

1.3 遍歷

常見的遍歷程式碼如下：

for (int i=0; i<list.size(); i++) {
list.get(i); // do something
}

這種遍歷方式的缺點是，在遍歷過程中如果修改集合結構（比如呼叫 remove 或 add），沒有任何異常，可能會導致意想不到的輸出，另外一種遍歷方式，比如：

for (T obj:list) {
// do something
}

遍歷的過程中，如果使用不正當的刪除操作（比如list.remove）就會丟擲 ConcurrentModificationException，因為它預設使用的 Iterator 遍歷方式。

Iterator 是 jdk 為所有集合遍歷而設計，並且是 fail-fast 快速失敗的。在 iterator 遍歷過程中，如果 List 結構不是通過迭代器本身的 add/remove 方法而改變，那麼就會丟擲 ConcurrentModificationException。注意，在 不同步 修改的情況下，它不能保證會發生，它只是盡力檢測併發修改的錯誤。

fail-fast是通過一個 modCount 欄位來實現的，這個欄位記錄了列表結構的修改次數，當呼叫 iterator() 返回迭代器時，會快取 modCount 當前的值，如果這個值發生了不期望的變化，那麼就會在 next, remove 操作中丟擲異常，核心程式碼如下：

private class Itr implements Iterator<E> {
int cursor; // 下一個要返回的元素下標，初始為 0
// 最後一個返回的元素下標，-1 表示沒有元素
int lastRet = -1;
// 快取 modCount 的值
int expectedModCount = modCount;
// 是否還有元素可讀
public boolean hasNext() {
return cursor != size;
}
public E next() {
// 檢查 modCount 值是否變化
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];
}
// 呼叫 iterator 自身的 remove 
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
// 刪除元素，此時 modCount 值改變
ArrayList.this.remove(lastRet);
// 移除會把lastRet後面的元素前移一位
cursor = lastRet; // 所以還是從 lastRet 開始讀
lastRet = -1;
// 重置 modCount 期望值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
// 如果變化，檢測到併發修改，丟擲異常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

2. LinkedList 原始碼分析

LinkedList 底層是一個 雙向連結串列 ，它不僅實現了 List 介面，還實現了 Deque 介面，所以既可以把它當作一般線性表，也可當作受限線性表主要是 棧和佇列 。

雙向連結串列的每個資料結點中都有兩個指標，分別指向直接後繼和直接前驅。所以，從雙向連結串列中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點，LinkedList 中的節點定義如下：

private static class Node<E> {
E item;// 資料
Node<E> next; // 後繼節點
Node<E> prev; // 前驅節點
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

它包含三個成員變數：

• int size = 0: 結點總數
• Node first: 頭結點
• Node last: 尾結點

2.1 頭插法和尾插法

連結串列插入時有兩種插入方法， 頭插法 和 尾插法 ，關鍵操作就是正確的斷鏈和續鏈。頭插法的程式碼如下：

private void linkFirst(E e) {
// 使用臨時變數指向頭節點
final Node<E> f = first;
// 新節點前驅為 null，後繼為 first
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) // 連結串列為空，同時為最後一個節點
last = newNode;
else // 否則作為前驅節點
f.prev = newNode;
size++;
modCount++;
}

頭插法的結果是逆序的，尾插法的結果是順序的。尾插法的操作也比較簡單，直接修改 last 引用即可：

void linkLast(E e) {
// 使用臨時變數指向尾節點
final Node<E> l = last;
// 新節點前驅為 last，後繼為 null
final Node<E> newNode = new Node<>(l, e, null);
// 重置 last 指向節點
last = newNode;
if (l == null)// 連結串列為空
first = newNode; // 第一個節點
else // 否則作為前一個的後繼
l.next = newNode;
size++; // 更新列表總數和結構修改次數
modCount++;
}

頭插和尾插都只修改了一個引用，比較複雜的是在中間某個位置插入，其原理和程式碼如下：

// 在非null節點succ之前插入元素e
void linkBefore(E e, Node<E> succ) {
// assert succ != null; 以下程式碼順序不能變
// 記住 succ 的前驅節點
final Node<E> pred = succ.prev;
// 1-2 建立一個新節點，它的前驅指向 pred，後繼指向 succ
final Node<E> newNode = new Node<>(pred, e, succ);
// 3 succ 前驅指向新節點
succ.prev = newNode;
if (pred == null) // 如果是第一個節點
first = newNode; // 讓first也指向新節點
else // 4 否則作為 pred 的後繼節點
pred.next = newNode;
size++; // 元素總數加1
modCount++; // 列表結構修改次數加1
}

2.2 刪除節點

同樣的刪除也是分為從頭或尾刪除，頭節點的刪除，就是讓 first 指向它的後繼節點，程式碼如下：

private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 為了返回元素的資料
final E element = f.item;
// 臨時變數引用頭節點的後繼節點
final Node<E> next = f.next;
// 釋放頭節點，全部至 null
f.item = null;
f.next = null; // help GC
// 重置 first 引用
first = next;
// 如果刪除的連結串列是最後一個節點
if (next == null) 
last = null;
else // 頭節點的前驅為 null
next.prev = null;
size--;
modCount++;
return element;
}

尾節點的刪除，一樣是修改 last 引用，讓它指向它的前驅節點，與頭節點刪除邏輯差不多，可對照理解，程式碼如下：

private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}

如果在某個中間位置刪除，就需要正確的操作了，主要是防止在斷鏈的過程中導致整個鏈條斷開，程式碼如下：

E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
// 待刪除元素的前驅和後繼節點
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
// 連結串列為空
first = next;
} else {
// 1 前驅節點的後繼指向 x 的後繼節點
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
// 2 後繼節點的前驅指向 x 的前驅節點
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

2.3 棧和佇列

棧就是隻能在棧頂操作，後進先出的受限線性表，LinkedList 提供的與棧相關的方法有：

• push(E e): 將元素插入棧頂，也就是插到列表的頭，實際呼叫的是 linkFirst
• pop(): 從棧頂彈出一個元素，也就是刪除並返回列表的第一個元素，實際呼叫的是 unlinkFirst
• peek(): 檢視棧頂元素，不會刪除
• peekFirst(),peekLast(): 分別是檢視棧頂和棧尾元素

佇列就是隻能從一端插入，另一端刪除的線性表，LinkedList 提供的與佇列相關的方法：

• offer(E e): 入佇列，將元素插入列表尾部，實際呼叫的是 linkLast
• offerFirst,offerLast: 分別是從頭開始或從尾開始入隊，當然了，確認在哪端就不要更改了
• remove(): 出佇列，將列表頭結點刪除並返回
• removeFirst,removeLast: 與 offerFirst,offerLast 搭配使用

2.4 遍歷

雙鏈表有兩種遍歷方式：順序遍歷和逆序遍歷，分別通過 ListItr 和 DescendingIterator 實現。同樣這個 Iterator 也是快速失敗的，其中 ListItr 分別提供了向前和向後的遍歷方式，DescendingIterator 只是簡單對 ListItr previous() 方法使用的封裝，ListItr 核心程式碼如下：

private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;// 最後返回的節點
private Node<E> next;// 下一個要讀的節點
private int nextIndex;// 下一個要讀的節點位置
// 快取列表結構修改次數，檢查併發修改
private int expectedModCount = modCount;
// 初始化開始遍歷的位置，node(index) 會遍歷找到這個節點
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
// 順序讀時，判斷是否還有更多的後繼節點
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next; // 移動 next 指向其後繼節點
nextIndex++;
return lastReturned.item;
}
// 逆序讀時，判斷是否還有更多的前驅節點
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
// 移動 next 指向其前驅節點
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public void remove() {
// 遍歷過程中，提供刪除操作
}
public void add(E e) {
// 遍歷過程中，提供新增操作 
}
// 檢查是否存在併發修改
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

3. 非執行緒安全

ArrayList 和 LinkedList 都是 非執行緒安全 的，那為什麼呢？

ArrayList 本質操作可分為以下兩類，這也是執行緒 競爭條件 的所在：

• 對 size 變數的操作，size++ 和 --size
• System.arraycopy() 陣列拷貝

size++ 其實是一個複合操作：取值、加1和賦值，不是原子操作，非執行緒安全；System.arraycopy 它也是非執行緒安全的，所以 ArrayList 不是執行緒安全的。

LinkedList 主要 競爭條件 就是斷鏈和續鏈的操作，以尾插為例，假如執行緒 A 執行:

final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);

如果現線上程 A 被搶佔，執行緒 B 也執行相同的程式碼，並且繼續執行：

last = newNode;

不久後，執行緒 A 也執行上述程式碼，那麼問題就出來了，執行緒 B 完成操作後，執行緒 A 就操作了一次，導致執行緒 B 的要插入的節點丟失，所以不是執行緒安全的。

當然了 JDK 提供了 Collections.synchronizedList(List ) 方法可以把 ArrayList 和 LinkedList 變成執行緒安全的。

4. 效能

ArrayList 具備陣列 隨機訪問 的特性，但增加和刪除需要移動陣列元素，效率較慢。在動態擴容時，涉及到了記憶體拷貝，所以適當增加初始容量或者在新增大量資料之前提前擴大容量，減少拷貝次數是有必要的。

相比 ArrayList，LinkedList 只能順序或逆序訪問，佔用的記憶體稍微大點，因為節點還要維護兩個前後引用，但是它的插入刪除效率高。

5. 小結

這兩個是很常用的資料結構，也比較容易理解，在閱讀原始碼時，jdk裡類的設計，編碼方式也值得去重視。