您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 集合源碼深度剖析 (三)：LinkedList 雙向循環鏈表實現原理與性能特徵

編輯：Java 綜合教學

Java 集合源碼深度剖析 (三)：LinkedList 雙向循環鏈表實現原理與性能特徵

`LinkedList` 基於**雙向循環鏈表**實現，同時實現 `List`、`Deque`、`Cloneable`、`Serializable` 接口，是**棧、隊列、雙端隊列**的統一實現。本文通過**源碼級剖析**、**數據結構圖解**、**核心方法執行流程**、**性能基準對比**四個維度，徹底講透 LinkedList 內核機制。

一、類定義與繼承體系

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

AbstractSequentialList：為**順序訪問**數據結構 (鏈表) 優化的抽象類，默認實現基於 `ListIterator` 的隨機訪問為拋異常，子類需實現 `listIterator(int)`、`get(int)`、`set(int, E)`、`add(int, E)`、`remove(int)`。
Deque：雙端隊列接口，提供 `addFirst/Last`、`offerFirst/Last`、`pollFirst/Last`、`peekFirst/Last`、`push/pop` 等棧/隊列操作。

二、核心數據結構：靜態內部類 Entry (Node)

private static class Entry {
    E element;
    Entry next;
    Entry previous;

    Entry(E element, Entry next, Entry previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

關鍵設計：

哨兵節點 (header)：`private transient Entry header = new Entry<>(null, null, null);` — **不存儲數據**，`header.next` 指向首節點，`header.previous` 指向尾節點，初始化時 `header.next = header.previous = header` 形成**空循環**。
雙向循環：首節點 `previous` 指向 header，尾節點 `next` 指向 header，**無 null 指針**，統一邊界處理邏輯。
transient 字段：`header`、`size`、`modCount` 均為 transient，序列化時自定義 `writeObject/readObject` 重建鏈表結構。

三、四種鏈表結構對比圖解

類型	結構特徵	圖解
單向鏈表	next → null
單向循環鏈表	尾 next → head
雙向鏈表	head.prev=null, tail.next=null
雙向循環鏈表 (LinkedList)	header 哨兵，首尾互指 header

四、核心源碼方法深度剖析

4.1 節點定位優化：二分查找策略

private Entry entry(int index) {
    if (index < 0 || index >= size) throw new IndexOutOfBoundsException(...);
    Entry e = header;
    // 核心優化：判斷索引在前半段還是後半段
    if (index < (size >> 1)) {  // 前半段：從頭向後
        for (int i = 0; i <= index; i++) e = e.next;
    } else {                    // 後半段：從尾向前
        for (int i = size; i > index; i--) e = e.previous;
    }
    return e;
}

意義： 將遍歷步數從 O(n) 降為 **O(min(index, n-index))**，但本質仍為 **O(n) 線性查找**，隨機訪問極慢。

4.2 統一插入邏輯：addBefore(E e, Entry entry)

private Entry addBefore(E e, Entry entry) {
    Entry newEntry = new Entry<>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;  // 前驅 next 指向新節點
    newEntry.next.previous = newEntry;  // 後繼 prev 指向新節點
    size++;
    modCount++;
    return newEntry;
}

所有插入操作 (`addFirst`、`addLast`、`add(index, e)`、`addAll`) **最終均委派給此方法**，插入位置由 `entry` 參數決定：**在 entry 節點之前插入**。

4.3 統一刪除邏輯：remove(Entry e)

private E remove(Entry e) {
    if (e == header) throw new NoSuchElementException();
    E result = e.element;
    e.previous.next = e.next;   // 前驅跨過 e 指向後繼
    e.next.previous = e.previous; // 後繼跨過 e 指向前驅
    e.next = e.previous = null;   // 斷開引用助 GC
    e.element = null;
    size--;
    modCount++;
    return result;
}

刪除本質：**前驅與後繼直接鏈接**，斷開目標節點引用。

4.4 ListIterator 實現與 Fail-Fast 機制

private class ListItr implements ListIterator {
    private Entry lastReturned = header;
    private Entry next;
    private int nextIndex;
    private int expectedModCount = modCount;  // 快照

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    // next(), previous(), add(), set(), remove() 均調用 checkForComodification()
}

modCount 繼承自 `AbstractList`，每次結構性修改 (add/remove/clear) 自增。迭代器構建時拍攝快照 `expectedModCount`，操作前比對，**異步修改即拋 CME**。

4.5 反向迭代器

private class DescendingIterator implements Iterator {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() { return itr.hasPrevious(); }
    public E next() { return itr.previous(); }
    public void remove() { itr.remove(); }
}

直接復用 `ListItr` 逆向邏輯，零代碼重複。

五、Deque/Queue/Stack 操作映射表

六、序列化實現：自定義 writeObject/readObject

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();  // 寫入非 transient 字段 (此處無)
    s.writeInt(size);        // 寫入 size
    for (Entry e = header.next; e != header; e = e.next)
        s.writeObject(e.element);  // 依次寫入元素
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    int size = s.readInt();  // 讀取 size
    header = new Entry<>(null, null, null);
    header.next = header.previous = header;
    for (int i = 0; i < size; i++)
        addBefore((E) s.readObject(), header); // 尾插法重建
}

**不序列化鏈表結構**，僅序列化 **size + 元素序列**，反序列化時重新構建哨兵節點並尾插，極其高效緊湊。

七、性能特徵總結與選型指南

接口方法	語義	委派實現	異常/返回值差異
addFirst / push	棧頂/隊頭入	addBefore(e, header.next)	滿拋 IllegalStateException (鏈表無容量上限，不拋)
addLast / add / offer	隊尾入	addBefore(e, header)	同左
removeFirst / remove / pop / poll	棧頂/隊頭出	remove(header.next)	空: remove/pop 拋 NoSuchElementException; poll 返回 null
getFirst / element / peek	查看棧頂/隊頭	header.next.element	空: element 拋異常; peek 返回 null
removeLast / pollLast	隊尾出	remove(header.previous)	同左

操作	時間複雜度	ArrayList	適用場景
get(index) / set(index, e)	O(n) — 線性查找	O(1)	極少隨機訪問
addFirst / addLast / push / pop	O(1)	O(n) — 需擴容/位移	棧、隊列、雙端隊列首選
add(index, e) / remove(index)	O(n) — 定位 + O(1) 插刪	O(n) — 位移	頭尾操作優；中間操作兩者同量級
內存開銷	高 (每節點 3 引用 + 對象頭)	低 (連續數組)	大數據量優先 ArrayList
GC 壓力	大 (大量小對象)	小	高頻創建/銷毀慎用

八、總結

LinkedList = 雙向循環鏈表 + 哨兵節點 + 統一 addBefore/remove 邏輯 + Fail-Fast 迭代器。
優勢： 首尾增刪 O(1)、天然支援 Deque/Stack、無擴容拷貝開銷。
劣勢： 隨機訪問 O(n)、內存開銷大、GC 壓力大、CPU 緩存不友好 (非連續內存)。
鐵律： **需要隨機訪問用 ArrayList；需要首尾高頻增刪、實現棧/隊列用 LinkedList；極大數據量考慮數組或專用結構。**

參考資料：JDK 8 源碼、Java 集合框架設計文檔、Effective Java 第 3 版 Item 28。