Java LinkedList 深度解析：雙向鏈表源碼、Deque 棧隊列雙重身份與遍歷效率實測

java.util.LinkedList 是基於雙向鏈表實現的 List 與 Deque 雙重身份集合。它在頻繁頭尾插刪、棧/隊列場景下性能優異，但隨機訪問極弱。本文從源碼結構、核心 API、棧隊列用法、遍歷效率實測五個維度全方位剖析。

一、類定位與雙重接口

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable { }

• 繼承 AbstractSequentialList → 獲取基於索引的 get/set/add/remove 默認實現（內部委託鏈表遍歷）。
• 實現 List：支持索引操作、遍歷。
• 實現 Deque：雙端隊列語義，提供 addFirst/Last、pollFirst/Last、push/pop/peek 等豐富 API。
• 非線程安全，支持序列化與克隆。

二、核心數據結構：靜態內部類 Entry

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

關鍵字段

transient Entry<E> header = new Entry<>(null, null, null); // 哨兵節點，不存數據
transient int size = 0;

• header 形成循環雙向鏈表：header.next 指向首節點，header.previous 指向尾節點，空表時指向自身。
• 所有操作本質是指針重連，無數組搬移、擴容問題。

三、核心源碼邏輯精選

3.1 索引定位優化：雙向查找

private Entry<E> entry(int index) {
    if (index < 0 || index >= size) throw new IndexOutOfBoundsException(...);
    Entry<E> 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;
}

雖有優化，但隨機訪問仍屬 O(n) 線性級，嚴禁大量隨機訪問。

3.2 節點插入：addBefore(e, entry)

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

四步指針操作完成插入，O(1)（不含定位）。addFirst/addLast/push/offer 皆委託此法。

3.3 節點刪除：remove(Entry<E> e)

private E remove(Entry<E> e) {
    if (e == header) throw new NoSuchElementException();
    E result = e.element;
    e.previous.next = e.next;
    e.next.previous = e.previous;
    e.next = e.previous = null;
    e.element = null;   // 釋放引用助 GC
    size--;
    modCount++;
    return result;
}

3.4 ListIterator 實現與 Fail-Fast

ListItr 內部類實現 ListIterator，維護 expectedModCount，每次操作前檢查 modCount，異常拋 ConcurrentModificationException。支持雙向遍歷、add/set/remove 三大修改操作。

四、Deque 棧/隊列雙重語義速查表

棧（LIFO）等價映射

push(e)      ≡ addFirst(e)
pop()        ≡ removeFirst()
peek()       ≡ peekFirst()

隊列（FIFO）等價映射

add(e)       ≡ addLast(e)
offer(e)     ≡ offerLast(e)
remove()     ≡ removeFirst()
poll()       ≡ pollFirst()
element()    ≡ getFirst()
peek()       ≡ peekFirst()

五、七種遍歷方式效率實測（10 萬元素，JDK 8）

iteratorLinkedListThruIterator：8 ms      // Iterator 只讀遍歷
iteratorThroughFor2：5 ms                 // for-each (內部用 Iterator) ★推薦只讀
iteratorThroughPollFirst：8 ms            // pollFirst() 邊遍歷邊刪除
iteratorThroughPollLast：6 ms             // pollLast() 邊遍歷邊刪除
iteratorThroughRemoveFirst：2 ms          // removeFirst() 邊遍歷邊刪除 ★最快但銷毀數據
iteratorThroughRemoveLast：2 ms           // removeLast() 邊遍歷邊刪除
iteratorLinkedListThruForeach：3724 ms    // 下標隨機訪問 list.get(i) ★極慢，禁用！

黃金法則：

• 只讀遍歷 → for (E e : list) 或 list.forEach()。
• 需邊遍歷邊刪除 → pollFirst()/pollLast()（返回 null 終止）或 Iterator.remove()。
• 絕對禁止 使用 for (int i=0; i。

import java.util.*;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // 基礎增刪改查
        list.add("1"); list.add("2"); list.add("3");
        list.add(1, "4");  // 索引 1 插入 → [1, 4, 2, 3]
        System.out.println("基礎操作後: " + list);

        // Deque 首尾操作
        System.out.println("\n--- addFirst/removeFirst/getFirst ---");
        list.addFirst("10"); System.out.println(list);
        System.out.println("removeFirst: " + list.removeFirst()); System.out.println(list);
        System.out.println("getFirst: " + list.getFirst());

        System.out.println("\n--- offerFirst/pollFirst/peekFirst ---");
        list.offerFirst("10"); System.out.println(list);
        System.out.println("pollFirst: " + list.pollFirst()); System.out.println(list);
        System.out.println("peekFirst: " + list.peekFirst());

        // 棧模式
        System.out.println("\n--- LIFO Stack 模式 ---");
        LinkedList<String> stack = new LinkedList<>();
        stack.push("1"); stack.push("2"); stack.push("3"); stack.push("4");
        System.out.println("stack: " + stack);
        System.out.println("pop: " + stack.pop());
        System.out.println("peek: " + stack.peek());
        System.out.println("stack: " + stack);

        // 隊列模式
        System.out.println("\n--- FIFO Queue 模式 ---");
        LinkedList<String> queue = new LinkedList<>();
        queue.add("10"); queue.add("20"); queue.add("30"); queue.add("40");
        System.out.println("queue: " + queue);
        System.out.println("remove: " + queue.remove());
        System.out.println("element: " + queue.element());
        System.out.println("queue: " + queue);

        // 轉數組
        String[] arr = list.toArray(new String[0]);
        System.out.println("\ntoArray: " + Arrays.toString(arr));

        // 清空
        list.clear();
        System.out.println("isEmpty: " + list.isEmpty());
    }
}