Java 集合深度剖析：LinkedList 底層原理、Queue/Deque 介面與效能實測

LinkedList 核心定位

LinkedList 實作 List、Queue、Deque 三大介面，底層為雙向鏈表。適用於頻繁頭尾增刪、作為堆疊/佇列/雙端佇列；不適合隨機存取（get(index) 為 O(n)）。

繼承體系與關鍵介面

LinkedList
  → AbstractSequentialList (基於迭代器實作隨機存取)
  → AbstractList → AbstractCollection
  → List, Queue, Deque, Cloneable, Serializable

Queue 介面核心方法（單端佇列）

最佳實踐：優先使用 offer/poll/peek，避免異常控制流程。注意 LinkedList 允許 null 元素，佇列語義下不應插入 null（無法區分「隊列空」與「隊頭為 null」）。

Deque 介面核心方法（雙端佇列）

繼承 Queue，新增頭尾對稱操作：

• 入隊：addFirst/offerFirst、addLast/offerLast
• 出隊：removeFirst/pollFirst、removeLast/pollLast
• 查看：getFirst/peekFirst、getLast/peekLast
• 堆疊語義：push(e) ≡ addFirst(e)、pop() ≡ removeFirst()
• 反向迭代：descendingIterator()

底層原始碼深度解讀

節點結構

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 Node<E> first（頭節點）、last（尾節點）、size、modCount（快速失效計數）。

poll() 出隊原理

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

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

O(1) 時間，僅調整頭指標與 GC 清理。

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

雙向遍歷優化，但仍為 O(n)，嚴禁在大量資料場景下頻繁呼叫 get(index)。

效能實測：LinkedList vs ArrayList 隨機存取

// 10,000 筆資料，各存取 10,000 次
LinkedList: 56 ms
ArrayList:   1 ms

結論：隨機存取 ArrayList 完勝（連續記憶體 + CPU 快取友善）。LinkedList 僅在頭尾增刪、中間插入/刪除已知節點 時具優勢。

選型決策樹

1. 需隨機存取/遍歷為主 → ArrayList
2. 需佇列/堆疊/雙端佇列語義 → ArrayDeque（陣列實作，效能優於 LinkedList）
3. 極少數場景：頻繁中間插刪且已有節點引用 → LinkedList
4. 多執行緒環境 → Collections.synchronizedList 或 ConcurrentLinkedQueue

原始碼級避坑指南

• modCount 機制：迭代過程中結構性修改會拋 ConcurrentModificationException。
• toArray() 回傳 Object[]，需強轉或用 toArray(new String[0])。
• 序列化時 transient 節點會重建，writeObject/readObject 手動處理。