Java 進階：LinkedList 源碼深度解析（基於 JDK 1.7）

前言：版本差異的關鍵提示

JDK 1.6 LinkedList 採用**循環雙向鏈表**（header 節點 prev 指向尾、next 指向頭），JDK 1.7+ 簡化為**非循環雙向鏈表**（first/last 直接指向頭尾節點，null 表示邊界）。本文基於 **JDK 1.7/8** 源碼分析，切勿混淆舊版博客資料。

一、核心數據結構

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

• 三字段：item 數據、next 後繼、prev 前驅。
• 構造參數順序：prev, element, next。

類級字段

transient int size = 0;        // 節點數
transient Node<E> first;       // 頭節點引用
transient Node<E> last;        // 尾節點引用

• transient：序列化時自定義寫入（writeObject 手動序列化節點數據），不依賴默認字段序列化。

二、構造方法

// 無參：空實現，first=last=null, size=0
public LinkedList() {}

// Collection 構造：轉數組 → 批量鏈接
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

addAll 批量鏈接邏輯

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // index ∈ [0, size]
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) return false;

    Node<E> pred, succ;
    if (index == size) { // 尾部插入
        succ = null;
        pred = last;
    } else { // 中間插入
        succ = node(index);      // 獲取 index 處節點
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) first = newNode;
        else pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) last = pred;
    else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

關鍵點：單向遍歷數組，雙向鏈接節點，O(numNew) 時間，避免重複查找插入點。

三、核心輔助方法

node(index) 定位節點：雙向查找優化

Node<E> node(int index) {
    // assert isElementIndex(index); // index ∈ [0, size-1]
    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;
    }
}

• 時間複雜度 **O(min(index, size-index))**，最多遍歷半個鏈表。
• 支撐 get/set/add/remove 所有索引操作。

linkFirst / linkLast / linkBefore 統一鏈接邏輯

// 頭插
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;
    else f.prev = newNode;
    size++; modCount++;
}

// 尾插
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;
    else l.next = newNode;
    size++; modCount++;
}

// 指定節點前插入
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;
    else pred.next = newNode;
    size++; modCount++;
}

unlinkFirst / unlinkLast / unlink 統一解鏈邏輯

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

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

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; // help GC
    size--; modCount++;
    return element;
}

• 核心：**斷開雙向引用，置 null 協助 GC**，更新 first/last 邊界。
• 返回被刪除元素值，支持 pop()/remove() 等語義。

四、核心公開 API 實現

五、隊列/棧/雙端隊列語義映射

實現 Deque<E> 接口，提供豐富別名方法：

六、ListIterator 雙向迭代器

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null; // 上次返回節點
    private Node<E> next;                // 下一個待返回節點
    private int nextIndex;               // 下一個索引
    private int expectedModCount = modCount; // 快速失效檢查

    // next()：向後
    public E next() {
        checkForComodification();
        if (!hasNext()) throw new NoSuchElementException();
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    // previous()：向前
    public E previous() {
        checkForComodification();
        if (!hasPrevious()) throw new NoSuchElementException();
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    // add()：在 lastReturned 之前插入（next 之前）
    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null) linkLast(e);
        else linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    // remove()：刪除 lastReturned
    public void remove() {
        checkForComodification();
        if (lastReturned == null) throw new IllegalStateException();
        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned) next = lastNext;
        else nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }
}

• 游標模型：迭代器位於元素**之間**，nextIndex 指向下一個元素索引。
• add(e) 插入到游標前（即 next 之前），不影響後續 next()。
• remove() 刪除最近一次 next()/previous() 返回的元素（lastReturned）。
• modCount 機制：結構性修改（add/remove）+1，迭代器操作同步更新 expectedModCount，檢測併發修改拋 ConcurrentModificationException。

七、序列化與克隆

writeObject / readObject 自定義序列化

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject(); // 寫入非 transient 字段（此處無）
    s.writeInt(size);       // 寫入 size
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item); // 逐節點寫入元素
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    int size = s.readInt();
    for (int i = 0; i < size; i++)
        linkLast((E) s.readObject()); // 重建鏈表
}

• 不序列化 first/last 引用（transient），避免反序列化後引用失效。
• 只序列化 size 和**元素順序**，反序列化時重新 linkLast 重建結構。

clone() 淺拷貝

public Object clone() {
    LinkedList<E> clone = superClone(); // 父類 Object.clone() 淺拷貝字段
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item); // 逐元素 add，共享元素對象
    return clone;
}

• **淺拷貝**：新鏈表節點新建，但元素對象**共享引用**（不可變對象安全，可變對象需業務層深拷貝）。

八、性能特徵總結

適用場景

• 頻繁頭尾操作：隊列、棧、雙端隊列、滑動窗口。
• 迭代器雙向遍歷、需在遍歷中增刪：ListIterator。
• **不適用**：大量隨機訪問（用 ArrayList）、極大數據量內存敏感（用數組/專用結構）。

九、常見誤區與避坑

1. 以為 get(i) 是 O(1)：實為 O(n)，大量隨機訪問性能災難。
2. 並發環境直接用：非線程安全，需 Collections.synchronizedList 或 CopyOnWriteArrayList（讀多寫少）或自行加鎖。
3. foreach 中 remove：拋 ConcurrentModificationException，必須用 Iterator.remove() 或 ListIterator。
4. clone 以為深拷貝：僅節點新建，元素共享引用。
5. 序列化後 first/last 非 null：transient 字段反序列化為 null，但 readObject 中 linkLast 會正確重建。

總結

LinkedList 以**非循環雙向鏈表**實現 List、Deque、Cloneable、Serializable，核心優勢在**頭尾 O(1) 操作**與**雙向迭代器**。源碼中 node() 雙向查找、link/unlink 統一鏈接邏輯、ListItr 游標模型、自定義序列化重建鏈表，均體現經典鏈表數據結構的工程化實現智慧。選型時務必權衡「隨機訪問弱」與「頭尾操作強」的業務契合度。

1. 上一篇文章： Java 入門進階：方法定義、重載、參數傳遞與返回值機制詳解
2. 下一篇文章： Java 集合框架精講：LinkedList 實現原理、源碼分析與遍歷性能實測

Java 綜合教學

Java 正則表達式超詳細指南：從基礎語法到 java.util.regex 與 Jakarta-ORO 兩大庫實戰

Java 正則表達式完整指南 第一部分：正則表達式基礎語法

Java 連接 Oracle 數據庫完整實戰：從環境搭建到 CRUD 操作全流程

Java 連接 Oracle 數據庫完整實戰 Oracle

Struts 2 框架深度解析：從 MVC 基礎到核心機制

Struts 2 框架深度解析：從 MVC 基礎到核心機制

Web Service 核心架構詳解：XML、SOAP、WSDL、UDDI 協議與跨平台調用原理

Web Service 核心架構詳解：XML、SOAP、WS