LinkedList 核心原理與雙向鏈表實現深度解析

LinkedList 基於雙向鏈表實現 List 與 Deque 接口，擅長頻繁插入刪除、頭尾操作。本文深入剖析其節點結構、核心方法實現、迭代器機制及與 ArrayList 的選型邊界。

一、節點結構：雙向鏈表基石

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

關鍵字段：first 指向頭節點，last 指向尾節點，size 記錄元素數量，modCount 記錄修改次數(用於 fail-fast)。

二、構造方法

三、核心鏈表操作原語

3.1 linkLast(E e) - 尾部添加

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

時間複雜度：O(1)，直接操作尾指針。

3.2 linkFirst(E e) - 頭部添加

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

3.3 unlink(Node<E> x) - 節點刪除

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; // 助 GC
    size--;
    modCount++;
    return element;
}

時間複雜度：O(1)，給定節點直接斷開鏈接。

四、核心公開方法實現

4.1 add(E e) / addLast(E e) - 尾部添加

public boolean add(E e) { linkLast(e); return true; }
public void addLast(E e) { linkLast(e); }

4.2 addFirst(E e) - 頭部添加

public void addFirst(E e) { linkFirst(e); }

4.3 get(int index) - 按索引獲取

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // 優化：index < size/2 從頭遍歷，否則從尾遍歷
    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)，雖有雙向優化，但仍需遍歷。

4.4 set(int index, E element) - 按索引替換

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

4.5 remove(Object o) - 按值刪除首個匹配

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next)
            if (x.item == null) { unlink(x); return true; }
    } else {
        for (Node<E> x = first; x != null; x = x.next)
            if (o.equals(x.item)) { unlink(x); return true; }
    }
    return false;
}

時間複雜度：O(n)，需線性查找節點。

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

六、ListIterator 實現：雙向游標

LinkedList.listIterator(index) 返回 ListItr 內部類，維護 lastReturned、next、nextIndex，支持雙向遍歷、add/set/remove 原地修改，modCount 機制保證 fail-fast。

七、性能特徵總結與選型建議

選型鐵律

1. 默認優先 ArrayList：現代 CPU 緩存友好、內存效率高、隨機訪問快
2. 明確需要 頻繁頭部增刪、實現 隊列/棧 語義 → ArrayDeque (性能優於 LinkedList)
3. 極少數場景：中間頻繁增刪且已定位節點、需 ListIterator 雙向游標 → LinkedList
4. 避免在高性能路徑使用 LinkedList，其 GC 壓力與緩存未命中開銷往往被低估