Java LinkedList 源碼深度解析：雙向鏈表實現與多功能特性

LinkedList 概述

LinkedList 基於雙向循環鏈表實現，不僅可作為列表使用，還實現了 Deque 接口，可作為棧、隊列、雙端隊列使用。它不是線程安全的，僅適用於單線程環境。LinkedList 實現了 Serializable 和 Cloneable 接口，支持序列化與克隆。

核心數據結構

Entry 節點

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

每個節點包含元素值、前驅指針、後繼指針，構成雙向鏈表。

哨兵節點

private transient Entry header = new Entry<>(null, null, null);
// 構造函數初始化
header.next = header.previous = header;

header 是不存儲數據的哨兵節點，next 指向首節點，previous 指向尾節點，形成循環結構，簡化邊界條件判斷。

核心方法解析

構造函數

• LinkedList()：創建空鏈表，header 指向自己
• LinkedList(Collection c)：調用無參構造，然後 addAll 添加元素到尾部

節點定位優化：entry(int index)

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

優化策略：比較 index 與 size/2，選擇較短路徑遍歷，平均查找步數減半。

添加元素

public boolean add(E e) {
    addBefore(e, header); // 添加到尾部（header.previous）
    return true;
}

private Entry addBefore(E e, Entry entry) {
    Entry newEntry = new Entry<>(e, entry, entry.previous);
    entry.previous.next = newEntry;
    entry.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

尾部添加 O(1)，指定位置插入需先定位節點 O(n)，再調整指針 O(1)。

刪除元素

public E remove(int index) {
    Entry e = entry(index);
    return remove(e);
}

private E remove(Entry e) {
    E result = e.element;
    e.previous.next = e.next;
    e.next.previous = e.previous;
    e.next = e.previous = null;
    e.element = null;
    size--;
    modCount++;
    return result;
}

刪除同樣需先定位 O(n)，調整指針 O(1)，並幫助 GC 回收節點。

獲取元素

public E get(int index) {
    return entry(index).element;
}

隨機訪問 O(n)，不實現 RandomAccess 接口。

Deque 接口實現：棧、隊列操作

LinkedList vs ArrayList 核心對比

最佳實踐建議

1. 頻繁頭尾操作：優先選 LinkedList（作為隊列/棧）
2. 頻繁隨機訪問：必須用 ArrayList
3. 未知訪問模式：默認 ArrayList，性能通常更好
4. 大量數據：ArrayList 內存效率更高，GC 壓力更小
5. 多線程：兩者都不安全，考慮 ConcurrentLinkedQueue 或 Collections.synchronizedList

總結

LinkedList 以雙向循環鏈表為基礎，通過哨兵節點簡化邊界處理，雙向指針支持高效頭尾操作，實現 Deque 提供豐富棧隊功能。但隨機訪問性能弱、內存開銷大、緩存不友好，現代架構中除特定隊列棧場景外，ArrayList 往往是更優選擇。