以下是基于 JDK 8 的 LinkedList 深度源碼解析，涵蓋其數據結構、核心方法實現、性能特點及使用場景。我們從 類結構、Node節點、插入/刪除/訪問操作、線程安全、性能對比 等角度進行詳細分析

一、類結構與繼承關系

1. 類定義

public class LinkedList<E> extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• AbstractSequentialList：提供按順序訪問元素的默認實現（如 get(int index)、set(int index, E element)）。
• List：支持按索引操作（如 add(int index, E element)、get(int index)）。
• Deque：雙端隊列接口，支持頭尾插入/刪除（如 addFirst()、removeLast()）。
• Cloneable 和 Serializable：支持克隆和序列化。

.

二、核心數據結構：Node節點

1. Node類定義

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;}
}

• 雙向鏈表特性：每個節點通過 prev 和 next 指針連接，支持雙向遍歷。
• 內存分配：節點分散存儲，不依賴連續內存（與 ArrayList 的數組不同）。

.

三、構造方法詳解

1. 無參構造函數

public LinkedList() {}

• 初始化時 first 和 last 均為 null，size 為 0，表示鏈表為空。

2. 帶初始集合的構造函數

public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

• 調用無參構造函數后，通過 addAll() 方法將集合元素逐個添加到鏈表尾部。

.

四、插入操作詳解

1. 尾部插入：add(E e)

public boolean add(E e) {linkLast(e);return true;
}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;
}

• 關鍵步驟：
  1. 獲取當前尾節點 l
  2. 創建新節點 newNode，其 prev 指向 l，next 為 null。
  3. 更新 last 為 newNode。
  4. 如果鏈表為空（l == null），則 first 和 last 均指向 newNode。
  5. 否則，將原尾節點的 next 指向 newNode。
  6. 更新 size 和 modCount（結構修改計數器，用于迭代器的 fail-fast 機制）。

2. 頭部插入：addFirst(E e)

private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;
}

• 關鍵步驟：
  1. 獲取當前頭節點 f。
  2. 創建新節點 newNode，其 next 指向 f，prev 為 null。
  3. 更新 first 為 newNode。
  4. 如果鏈表為空（f == null），則 first 和 last 均指向 newNode。
  5. 否則，將原頭節點的 prev 指向 newNode。

3. 中間插入：add(int index, E element)

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));
}

• 關鍵步驟：
  1. 檢查索引合法性（0 ≤ index ≤ size）。
  2. 如果 index == size，調用 linkLast() 插入尾部。
  3. 否則，調用 node(index) 找到目標節點，再調用 linkBefore() 插入到該節點前。

linkBefore(E e, Node succ)

void linkBefore(E e, Node<E> succ) {final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;
}

• 關鍵步驟：
  1. 獲取目標節點 succ 的前驅節點 pred。
  2. 創建新節點 newNode，其 prev 指向 pred，next 指向 succ。
  3. 更新 succ.prev 為 newNode。
  4. 如果 pred == null（即插入到頭部），更新 first。
  5. 否則，將 pred.next 指向 newNode。

.

五、刪除操作詳解

1. 刪除指定元素：remove(Object o)

public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}

• 關鍵步驟：
  1. 遍歷鏈表查找匹配的節點。
  2. 找到后調用 unlink(x) 刪除節點。

unlink(Node x)

E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}

• 關鍵步驟：
  1. 獲取被刪除節點 x 的前后節點 prev 和 next。
  2. 如果 prev == null，說明 x 是頭節點，更新 first 為 next。
  3. 否則，將 prev.next 指向 next，并斷開 x.prev。
  4. 如果 next == null，說明 x 是尾節點，更新 last 為 prev。
  5. 否則，將 next.prev 指向 prev，并斷開 x.next。
  6. 將 x.item 置為 null，幫助 GC 回收。
  7. 更新 size 和 modCount。

2. 刪除頭節點：removeFirst()

private E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null;first = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;
}

• 關鍵步驟：
  1. 獲取頭節點 f 的 item 和 next。
  2. 斷開 f 的引用（f.item = null、f.next = null）。
  3. 更新 first 為 next。
  4. 如果 next == null，說明鏈表為空，更新 last 為 null。
  5. 否則，將 next.prev 置為 null。

.

六、訪問操作詳解

1. 按索引訪問：get(int index)

public E get(int index) {checkElementIndex(index);return node(index).item;
}Node<E> node(int index) {if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}
}

• 關鍵步驟：

  1. 根據索引位置選擇從頭節點或尾節點開始遍歷。
  2. 如果 index < size/2，從頭節點向后遍歷；否則，從尾節點向前遍歷。
  3. 返回對應節點的 item。

• 時間復雜度：O(n)，因為需要遍歷鏈表。

.

七、線程安全與 Fail-Fast 機制

1. 線程不安全

LinkedList 不是線程安全的，多線程環境下可能導致數據不一致或 ConcurrentModificationException。

2. Fail-Fast 機制

• 通過 modCount 記錄結構修改次數（如 add、remove）。
• 迭代器遍歷時會檢查 modCount 是否與創建迭代器時的值一致。如果不一致，拋出 ConcurrentModificationException。

示例代碼

public Iterator<E> iterator() {return new Itr();
}private class Itr implements Iterator<E> {int expectedModCount = modCount;public boolean hasNext() {checkForComodification();return cursor != size;}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}
}

.

八、性能對比與使用建議

使用建議

• 頻繁插入/刪除：優先使用 LinkedList（尤其是頭部或尾部操作）。
• 頻繁隨機訪問：優先使用 ArrayList。
• 線程安全：使用 Collections.synchronizedList(new LinkedList<>()) 或 CopyOnWriteArrayList。
• 雙端隊列：LinkedList 實現了 Deque 接口，可作為雙端隊列使用（如棧、隊列）。

.

九、擴展學習建議

1. 源碼調試：使用 IDE（如 IntelliJ IDEA）調試 LinkedList 的 add、remove、get 方法，觀察 first、last、size 的變化。
2. 版本差異：對比 JDK 8 和 JDK 21 的 LinkedList 源碼，觀察是否引入新的優化（如 Spliterator 支持）。
3. 進階主題：
   • LinkedList 與 Vector 的區別（線程安全 vs 性能）。
   • Deque 接口的實現細節（如 ArrayDeque 與 LinkedList 的對比）。
   • LinkedList 在 JVM 內存模型中的表現（鏈表的離散性 vs 數組的連續性）。