Java 集合框架精講：LinkedList 實現原理、源碼分析與遍歷性能實測

前言：雙向鏈表的工程化實現

LinkedList 實現 List、Deque、Cloneable、Serializable，底層採用**非循環雙向鏈表**（JDK 1.7+），以 first/last 直接引用頭尾節點。本文從繼承體系、核心字段、源碼關鍵方法、遍歷方式性能實測四個維度全景剖析。

一、類繼承體系與設計定位

java.lang.Object
  ↓
java.util.AbstractCollection<E>
  ↓
java.util.AbstractList<E>
  ↓
java.util.AbstractSequentialList<E>  // 關鍵：針對順序訪問優化
  ↓
java.util.LinkedList<E> implements List<E>, Deque<E>, Cloneable, Serializable

• AbstractSequentialList：為「順序訪問優於隨機訪問」的列表提供骨架實現，默認 get/set/add/remove(int index) 通過 listIterator(index) 實現，子類只需實現 listIterator() 和 size()。
• 實現 Deque：原生支持雙端隊列操作（棧/隊列語義）。

二、核心字段與 Node 結構

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

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

• transient：自定義序列化，不依賴默認機制。
• 無 header 哨兵節點（JDK 1.6 有），簡化邊界判斷。

三、源碼關鍵方法深度解析

1. 節點定位：node(index) 雙向查找

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

**優化本質**：將最長遍歷路徑從 n 縮減至 n/2，索引操作均受益。

2. 統一鏈接：linkFirst / linkLast / linkBefore

// 核心模式：創建新節點 → 修改鄰居指針 → 更新 first/last → size++/modCount++
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++;
}

三個方法覆蓋所有插入場景：頭插、尾插、中間插（linkBefore(e, succ)）。

3. 統一解鏈：unlinkFirst / unlinkLast / unlink

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、返回元素值**。

4. 批量操作：addAll(index, Collection)

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    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); 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;
}

**工程亮點**：單次遍歷數組完成所有節點創建與鏈接，**僅查找一次插入點**，避免循環調用 add(index+i, e) 導致 O(n²)。

5. 異常檢查：checkElementIndex / checkPositionIndex

private boolean isElementIndex(int index) { return index >= 0 && index < size; }
private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }
// Element 用於訪問現有元素，Position 用於插入位置（含尾後）

四、隊列/棧/雙端隊列語義映射表

五、ListIterator 雙向迭代器實現

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() { return nextIndex < size; }
    public boolean hasPrevious() { return nextIndex > 0; }

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

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

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null) linkLast(e);
        else linkBefore(e, next);
        nextIndex++; expectedModCount++;
    }

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

    final void checkForComodification() {
        if (modCount != expectedModCount) throw new ConcurrentModificationException();
    }
}

• DescendingIterator：包裝 ListItr(size)，委託 hasPrevious/previous/remove 實現反向遍歷。

六、遍歷方式性能實測（50 萬元素）

public class LinkedListThruTest {
    // 測試 7 種遍歷方式耗時（毫秒）
    // 1. Iterator 迭代器
    // 2. for-each (內部用 Iterator)
    // 3. 索引隨機訪問 get(i)  ← 最慢！
    // 4. pollFirst() 彈出遍歷
    // 5. pollLast() 彈出遍歷
    // 6. removeFirst() 刪除遍歷
    // 7. removeLast() 刪除遍歷
}

實測結果

iteratorLinkedListThruIterator：10 ms      ← 推薦
iteratorThroughFor2 (for-each)：10 ms      ← 推薦
iteratorThroughPollFirst：8 ms             ← 破壞性遍歷
iteratorThroughPollLast：10 ms             ← 破壞性遍歷
iteratorThroughRemoveFirst：7 ms           ← 破壞性遍歷
iteratorThroughRemoveLast：6 ms            ← 破壞性遍歷
iteratorLinkedListThruForeach (get(i))：414648 ms  ← **極慢！O(n²)**

性能結論

1. 嚴禁隨機訪問遍歷：for (int i=0; i 產生 O(n²) 災難。
2. 首選 Iterator / for-each：順序訪問 O(n)，代碼簡潔，非破壞性。
3. 需消費並清空：pollFirst/Last、removeFirst/Last 最快（O(1) 單次），但**破壞原數據**。
4. 反向遍歷：descendingIterator() 或 ListIterator.hasPrevious/previous。