Java 深度研究：LinkedList 源碼解析 - 雙向循環鏈表核心機制全揭秘

LinkedList 是 Java 集合框架中基於雙向循環鏈表實作的 List 與 Deque 實現。本文深入源碼（JDK 8 為基準），解析類結構、節點設計、核心操作（增刪查）、迭代器機制、序列化與轉陣列，助你徹底掌握其內部運作原理。

一、類定義與繼承體系

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

• 繼承 AbstractSequentialList：獲得 get/set/add/remove(int index) 骨幹實作，降低實作複雜度
• 實作 List：支援列表操作
• 實作 Deque：可作堆疊、佇列、雙端佇列
• 實作 Cloneable、Serializable：支援複製與序列化
• 非同步，多執行緒環境需外部同步或用 Collections.synchronizedList()

二、底層資料結構：雙向循環鏈表

節點類 Entry<E>（JDK 8 稱 Node<E>）

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

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

關鍵點：header 哨兵節點不存放資料，header.next == header.previous == header 表示空表。形成循環結構，頭尾操作統一邏輯。

核心欄位

private transient Entry<E> header = new Entry<>(null, null, null);
private transient int size = 0;

三、建構子

public LinkedList() {
    header.next = header.previous = header;  // 自循環，空表
}

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

四、核心操作源碼解析

1. 新增元素 add(E e) / addBefore(E, Entry)

public boolean add(E e) {
    addBefore(e, header);  // 在 header 前插入，即尾部
    return true;
}

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

圖解：新節點插入 entry 之前，修改四個指標，O(1)。

2. 指定位置插入 add(int index, E element)

public void add(int index, E element) {
    addBefore(element, (index == size ? header : entry(index)));
}

entry(int index) 智慧雙向遍歷：index < size/2 從頭往後，否則從尾往前，減少遍歷步數。

3. 批量新增 addAll(int index, Collection)

Entry<E> successor = (index == size ? header : entry(index));
Entry<E> predecessor = successor.previous;
for (Object o : c.toArray()) {
    Entry<E> e = new Entry<>((E)o, successor, predecessor);
    predecessor.next = e;
    predecessor = e;
}
successor.previous = predecessor;
size += numNew;

一次串接整個鏈表片段，效率極高。

4. 刪除 remove(Entry<E> e)

private E remove(Entry<E> 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;
}

O(1) 刪除，無需像 ArrayList 移動元素。

5. 取得元素 get(int index)

private Entry<E> entry(int index) {
    if (index < 0 || index >= size) throw new IndexOutOfBoundsException(...);
    Entry<E> 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;
}

雙向遍歷優化，平均步數 size/4。

6. 清空 clear()

public void clear() {
    Entry<E> e = header.next;
    while (e != header) {
        Entry<E> next = e.next;
        e.next = e.previous = null;
        e.element = null;
        e = next;
    }
    header.next = header.previous = header;
    size = 0;
    modCount++;
}

逐節點斷開引用，助 GC 回收。

五、迭代器機制

ListItr 實作 ListIterator

• lastReturned：上次返回節點
• next：下一個節點
• nextIndex：下一個索引
• expectedModCount：快速失效機制，檢測並發修改

核心方法

public E next() {
    checkForComodification();
    if (nextIndex == size) throw new NoSuchElementException();
    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.element;
}

public void add(E e) {
    checkForComodification();
    lastReturned = header;
    addBefore(e, next);
    nextIndex++;
    expectedModCount++;
}

DescendingIterator 反向迭代器

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

巧妙復用 ListItr 邏輯實現反向遍歷。

六、複製與轉陣列

clone() 深複製

public Object clone() {
    LinkedList<E> clone = (LinkedList<E>) super.clone();
    clone.header = new Entry<>(null, null, null);
    clone.header.next = clone.header.previous = clone.header;
    clone.size = 0;
    clone.modCount = 0;
    for (Entry<E> e = header.next; e != header; e = e.next)
        clone.add(e.element);
    return clone;
}

toArray() / toArray(T[])

• 建立目標大小陣列，遍歷複製元素
• toArray(T[])：輸入陣列足夠用它，不足用反射建立新陣列；長度大於 size 時 a[size] = null 標記結束

七、ArrayList vs LinkedList 選型指南

* 尾部擴容攤銷 O(1)

八、總結

LinkedList 以雙向循環鏈表 + 哨兵節點實現，核心優勢在於 O(1) 頭尾增刪與無需擴容，劣勢在隨機存取慢、記憶體開銷大。源碼中雙向遍歷優化、快速失效迭代器、哨兵節點統一邊界邏輯等設計模式值得學習借鑑。