LinkedList 源碼分析(JDK 1.8)

來源：https://www.cnblogs.com/chanshuyi/p/java_collection_linkedlist.html

概述

LinkedList 是 Java 集合框架中一個重要的實現，其底層採用的雙向鏈表結構。和 ArrayList 一樣，LinkedList 也支持空值和重複值。由於 LinkedList 基於鏈表實現，存儲元素過程中，無需像 ArrayList 那樣進行擴容。但有得必有失，LinkedList 存儲元素的節點需要額外的空間存儲前驅和後繼的引用。另一方面，LinkedList 在鏈表頭部和尾部插入效率比較高，但在指定位置進行插入時，效率一般。原因是，在指定位置插入需要定位到該位置處的節點，此操作的時間複雜度為O(N)。最後，LinkedList 是非線程安全的集合類，併發環境下，多個線程同時操作 LinkedList，會引發不可預知的錯誤。

以上是對 LinkedList 的簡單介紹，接下來，我將會對 LinkedList 常用操作展開分析，繼續往下看吧。

繼承體系

LinkedList 的繼承體系較為複雜，繼承自 AbstractSequentialList，同時又實現了 List 和 Deque 接口。繼承體系圖如下（刪除了部分實現的接口）：

LinkedList 繼承自 AbstractSequentialList，AbstractSequentialList 又是什麼呢？從實現上，AbstractSequentialList 提供了一套基於順序訪問的接口。通過繼承此類，子類僅需實現部分代碼即可擁有完整的一套訪問某種序列表（比如鏈表）的接口。深入源碼，AbstractSequentialList 提供的方法基本上都是通過 ListIterator 實現的，比如：

public E get(int index) {
 try {
 return listIterator(index).next();
 } catch (NoSuchElementException exc) {
 throw new IndexOutOfBoundsException("Index: "+index);
 }
}

public void add(int index, E element) {
 try {
 listIterator(index).add(element);
 } catch (NoSuchElementException exc) {
 throw new IndexOutOfBoundsException("Index: "+index);
 }
}

// 留給子類實現
public abstract ListIterator listIterator(int index);

所以只要繼承類實現了 listIterator 方法，它不需要再額外實現什麼即可使用。對於隨機訪問集合類一般建議繼承 AbstractList 而不是 AbstractSequentialList。LinkedList 和其父類一樣，也是基於順序訪問。所以 LinkedList 繼承了 AbstractSequentialList，但 LinkedList 並沒有直接使用父類的方法，而是重新實現了一套的方法。

另外，LinkedList 還實現了 Deque (double ended queue)，Deque 又繼承自 Queue 接口。這樣 LinkedList 就具備了隊列的功能。比如，我們可以這樣使用：

Queue queue = new LinkedList<>();

除此之外，我們基於 LinkedList 還可以實現一些其他的數據結構，比如棧，以此來替換 Java 集合框架中的 Stack 類（該類實現的不好，《Java 編程思想》一書的作者也對此類進行了吐槽）。

關於 LinkedList 繼承體系先說到這，下面進入源碼分析部分。

源碼分析

查找

LinkedList 底層基於鏈表結構，無法向 ArrayList 那樣隨機訪問指定位置的元素。LinkedList 查找過程要稍麻煩一些，需要從鏈表頭結點（或尾節點）向後查找，時間複雜度為 O(N)。相關源碼如下：

public E get(int index) {
 checkElementIndex(index);
 return node(index).item;
}

Node node(int index) {
 /*
 * 則從頭節點開始查找，否則從尾節點查找 

 * 查找位置 index 如果小於節點數量的一半，
 */ 
 if (index < (size >> 1)) {
 Node x = first;
 // 循環向後查找，直至 i == index
 for (int i = 0; i < index; i++)
 x = x.next;
 return x;
 } else {
 Node x = last;
 for (int i = size - 1; i > index; i--)
 x = x.prev;
 return x;
 }
}

上面的代碼比較簡單，主要是通過遍歷的方式定位目標位置的節點。獲取到節點後，取出節點存儲的值返回即可。這裡面有個小優化，即通過比較 index 與節點數量 size/2 的大小，決定從頭結點還是尾節點進行查找。查找操作的代碼沒什麼複雜的地方，這裡先講到這裡。

遍歷

鏈表的遍歷過程也很簡單，和上面查找過程類似，我們從頭節點往後遍歷就行了。但對於 LinkedList 的遍歷還是需要注意一些，不然可能會導致代碼效率低下。通常情況下，我們會使用 foreach 遍歷 LinkedList，而 foreach 最終轉換成迭代器形式。所以分析 LinkedList 的遍歷的核心就是它的迭代器實現，相關代碼如下：

public ListIterator listIterator(int index) {
 checkPositionIndex(index);
 return new ListItr(index);
}

private class ListItr implements ListIterator {
 private Node lastReturned;
 private Node next;
 private int nextIndex;
 private int expectedModCount = modCount;

 /** 構造方法將 next 引用指向指定位置的節點 */
 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 方法後，next 引用都會指向他的後繼節點
 nextIndex++;
 return lastReturned.item;
 }
 
 // 省略部分方法
}

上面的方法很簡單，大家應該都能很快看懂，這裡就不多說了。下面來說說遍歷 LinkedList 需要注意的一個點。

我們都知道 LinkedList 不擅長隨機位置訪問，如果大家用隨機訪問的方式遍歷 LinkedList，效率會很差。比如下面的代碼：

List<integet> list = new LinkedList<>();
list.add(1)
list.add(2)
......
for (int i = 0; i < list.size(); i++) {
 Integet item = list.get(i);
 // do something
}
/<integet>

當鏈表中存儲的元素很多時，上面的遍歷方式對於效率來說就是災難。原因在於，通過上面的方式每獲取一個元素，LinkedList 都需要從頭節點（或尾節點）進行遍歷，效率不可謂不低。在我的電腦（MacBook Pro Early 2015, 2.7 GHz Intel Core i5）實測10萬級的數據量，耗時約7秒鐘。20萬級的數據量耗時達到了約34秒的時間。50萬級的數據量耗時約250秒。從測試結果上來看，上面的遍歷方式在大數據量情況下，效率很差。大家在日常開發中應該儘量避免這種用法。

插入

LinkedList 除了實現了 List 接口相關方法，還實現了 Deque 接口的很多方法，所以我們有很多種方式插入元素。但這裡，我只打算分析 List 接口中相關的插入方法，其他的方法大家自己看吧。LinkedList 插入元素的過程實際上就是鏈表鏈入節點的過程，學過數據結構的同學對此應該都很熟悉了。這裡簡單分析一下，先看源碼吧：

/** 在鏈表尾部插入元素 */
public boolean add(E e) {
 linkLast(e);
 return true;
}

/** 在鏈表指定位置插入元素 */
public void add(int index, E element) {
 checkPositionIndex(index);

 // 判斷 index 是不是鏈表尾部位置，如果是，直接將元素節點插入鏈表尾部即可
 if (index == size)
 linkLast(element);
 else
 linkBefore(element, node(index));
}

/** 將元素節點插入到鏈表尾部 */
void linkLast(E e) {
 final Node l = last;
 // 創建節點，並指定節點前驅為鏈表尾節點 last，後繼引用為空
 final Node newNode = new Node<>(l, e, null);
 // 將 last 引用指向新節點
 last = newNode;
 // 判斷尾節點是否為空，為空表示當前鏈表還沒有節點
 if (l == null)
 first = newNode;
 else
 l.next = newNode; // 讓原尾節點後繼引用 next 指向新的尾節點
 size++;
 modCount++;
}

/** 將元素節點插入到 succ 之前的位置 */ 

void linkBefore(E e, Node succ) {
 // assert succ != null;
 final Node pred = succ.prev;
 // 1. 初始化節點，並指明前驅和後繼節點
 final Node newNode = new Node<>(pred, e, succ);
 // 2. 將 succ 節點前驅引用 prev 指向新節點
 succ.prev = newNode;
 // 判斷尾節點是否為空，為空表示當前鏈表還沒有節點 
 if (pred == null)
 first = newNode;
 else
 pred.next = newNode; // 3. succ 節點前驅的後繼引用指向新節點
 size++;
 modCount++;
}

上面是插入過程的源碼，我對源碼進行了比較詳細的註釋，應該不難看懂。上面兩個 add 方法只是對操作鏈表的方法做了一層包裝，核心邏輯在 linkBefore 和 linkLast 中。這裡以 linkBefore 為例，它的邏輯流程如下：

• 創建新節點，並指明新節點的前驅和後繼
• 將 succ 的前驅引用指向新節點
• 如果 succ 的前驅不為空，則將 succ 前驅的後繼引用指向新節點

對應於下圖：

以上就是插入相關的源碼分析，並不複雜，就不多說了。繼續往下分析。

刪除

如果大家看懂了上面的插入源碼分析，那麼再看刪除操作實際上也很簡單了。刪除操作通過解除待刪除節點與前後節點的鏈接，即可完成任務。過程比較簡單，看源碼吧：

public boolean remove(Object o) {
 if (o == null) {
 for (Node x = first; x != null; x = x.next) {
 if (x.item == null) {
 unlink(x);
 return true;
 }
 }
 } else {
 // 遍歷鏈表，找到要刪除的節點
 for (Node x = first; x != null; x = x.next) {
 if (o.equals(x.item)) {
 unlink(x); // 將節點從鏈表中移除
 return true;
 }
 }
 }
 return false;
}

public E remove(int index) {
 checkElementIndex(index);
 // 通過 node 方法定位節點，並調用 unlink 將節點從鏈表中移除
 return unlink(node(index));
}

/** 將某個節點從鏈表中移除 */
E unlink(Node x) {
 // assert x != null;
 final E element = x.item;
 final Node next = x.next;
 final Node prev = x.prev;
 
 // prev 為空，表明刪除的是頭節點
 if (prev == null) {
 first = next;
 } else {
 // 將 x 的前驅的後繼指向 x 的後繼 

 prev.next = next;
 // 將 x 的前驅引用置空，斷開與前驅的鏈接
 x.prev = null;
 }

 // next 為空，表明刪除的是尾節點
 if (next == null) {
 last = prev;
 } else {
 // 將 x 的後繼的前驅指向 x 的前驅
 next.prev = prev;
 // 將 x 的後繼引用置空，斷開與後繼的鏈接
 x.next = null;
 }

 // 將 item 置空，方便 GC 回收
 x.item = null;
 size--;
 modCount++;
 return element;
}

和插入操作一樣，刪除操作方法也是對底層方法的一層保證，核心邏輯在底層 unlink 方法中。所以長驅直入，直接分析 unlink 方法吧。unlink 方法的邏輯如下（假設刪除的節點既不是頭節點，也不是尾節點）：

• 將待刪除節點 x 的前驅的後繼指向 x 的後繼
• 將待刪除節點 x 的前驅引用置空，斷開與前驅的鏈接
• 將待刪除節點 x 的後繼的前驅指向 x 的前驅
• 將待刪除節點 x 的後繼引用置空，斷開與後繼的鏈接

對應下圖：

結合上圖，理解 LInkedList 刪除操作應該不難。好了，LinkedList 的刪除源碼分析就講到這。

總結

通過上面的分析，大家對 LinkedList 的底層實現應該很清楚了。總體來看 LinkedList 的源碼並不複雜，大家耐心看一下，一般都能看懂。同時，通過本文，向大家展現了使用 LinkedList 的一個坑，希望大家在開發中儘量避免。好了，本文到這裡就結束了，感謝閱讀！