Java 手寫雙向鏈表：無尾指針版 vs 帶尾指針版性能對比

雙向鏈表核心結構

private static class Node<E> {
    Node<E> prev;
    E item;
    Node<E> next;
    Node(Node<E> prev, E element, Node<E> next) {
        this.prev = prev; this.item = element; this.next = next;
    }
}

版本一：無尾指針 — 每次操作從頭遍歷

public class LinkedList<E> {
    private Node<E> head;
    
    // 头插 O(1)
    public LinkedList<E> addFirst(E e) {
        head = new Node<>(null, e, head);
        if (head.next != null) head.next.prev = head;
        return this;
    }
    // 尾插 O(n) — 需遍歷到尾部
    public LinkedList<E> addNode(E e) {
        if (head == null) { head = new Node<>(null, e, null); return this; }
        Node<E> last = head;
        while (last.next != null) last = last.next;
        last.next = new Node<>(last, e, null);
        return this;
    }
    // 刪除 O(n) — 需查找節點
    public LinkedList<E> remove(E e) {
        Node<E> cur = head;
        while (cur != null) {
            if (e.equals(cur.item)) {
                if (cur.prev != null) cur.prev.next = cur.next;
                if (cur.next != null) cur.next.prev = cur.prev;
                if (cur == head) head = cur.next;
                break;
            }
            cur = cur.next;
        }
        return this;
    }
    // ... getFirst(), toString() 等
}

版本二：帶尾指針 — 尾部操作 O(1)

public class LinkedList<E> {
    private Node<E> head;
    private Node<E> last; // 尾指針
    
    public LinkedList<E> addNode(E e) {
        if (last == null) { // 空鏈表
            head = last = new Node<>(null, e, null);
        } else {
            last.next = new Node<>(last, e, null);
            last = last.next;
        }
        return this;
    }
    public E getLast() { return last == null ? null : last.item; }
    // 刪除邏輯需同步維護 last 指針（刪除尾節點時 last = last.prev）
    // ... 其他方法同版本一
}

性能對比總結

* 尾刪需維護 last = last.prev，仍為 O(1)。

關鍵細節避坑

• 邊界條件：空鏈表、單節點、頭節點、尾節點四種情況全覆蓋
• 指針斷開順序：先斷開被刪節點的 prev/next，再更新鄰居指針，防止斷鏈
• 泛型擦除：節點類用 Node<E>，外部類用 LinkedList<E>
• 線程不安全：兩版本均非線程安全，多線程環境用 Collections.synchronizedList 或 ConcurrentLinkedDeque

對比 JDK LinkedList

• JDK 版維護 size、first/last、modCount（Fail-Fast）
• 提供 ListIterator 支持雙向游標操作
• 實現 Deque、Queue、List 多介面

總結

手寫雙向鏈表是理解數據結構、指針操作、邊界處理的**必修課**。帶尾指針版本在尾部高頻操作場景下優勢明顯，代價僅多一個引用。**生產代碼直接用 JDK LinkedList**，但面試、教學、嵌入式受限環境手寫能力不可或缺。