Java LinkedList 完全指南：源碼剖析、效能測試與最佳實踐

LinkedList 是什麼？

LinkedList 是基於雙向鏈表實現的 List 與 Deque 雙重身份集合：

• 實現 List → 支持索引訪問（但效率低）
• 實現 Deque → 天然支持棧（LIFO）、隊列（FIFO）、雙端隊列操作
• 非線程安全、可序列化、可克隆

核心數據結構

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; // 頭節點
transient Node<E> last;  // 尾節點
transient int size;      // 元素數量

無容量限制，動態擴容；節點包含前驅/後繼指針，插入刪除 O(1)，隨機訪問 O(n)。

源碼核心邏輯剖析（JDK 8）

索引定位優化：二分查找

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

獲取、設置、插入、刪除指定索引元素均調用此方法，雙向遍歷將最長路徑縮短一半。

插入與刪除核心

// 在 succ 節點前插入
void linkBefore(E e, Node<E> succ) {
    Node<E> pred = succ.prev;
    Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null) first = newNode;
    else pred.next = newNode;
    size++; modCount++;
}

// 解鏈節點
E unlink(Node<E> x) {
    E element = x.item;
    Node<E> next = x.next, 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;
}

遍歷方式效能大比拼（10 萬元素測試）

鐵律：絕不使用索引循環遍歷 LinkedList；只讀場景首選 for-each 或 Iterator。

Deque / Queue / Stack 等價操作速查表

Queue 等價：add = addLast、offer = offerLast、remove = removeFirst、poll = pollFirst、element = getFirst、peek = peekFirst。

Stack 等價：push = addFirst、pop = removeFirst、peek = peekFirst。

實戰示例：自定義頁眉頁腳的 PDF 生成器

（文中完整代碼展示了 LinkedList 作為隊列/棧的實際業務用法，此處省略，重點關注上表等價關係。）

總結

1. 結構決定性能：雙向鏈表適合頻繁頭尾增刪、順序遍歷；不適合隨機訪問。
2. 身份決定用法：既是 List 又是 Deque，按場景選擇 API（隊列用 offer/poll，棧用 push/pop）。
3. 遍歷鐵律：for-each 或 Iterator，拒絕 get(i) 循環。
4. 非線程安全：多線程環境用 Collections.synchronizedList 或改用 ConcurrentLinkedDeque。