LinkedList 源碼級淺析：雙向鏈表、雙端隊列與迭代器特性全解析

LinkedList 源碼級淺析：雙向鏈表、雙端隊列與迭代器特性全解析

核心定位

關鍵源碼結構

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable {
    transient int size = 0;
    transient Node first;
    transient Node last;
    
    private static class Node {
        E item;
        Node next;
        Node prev;
        Node(Node prev, E element, Node next) { ... }
    }
    
    // Deque 操作：首尾 O(1)
    public void addFirst(E e) { linkFirst(e); }
    public void addLast(E e) { linkLast(e); }
    public E removeFirst() { return unlinkFirst(first); }
    public E removeLast() { return unlinkLast(last); }
    
    // List 操作：指定位置 O(n) 定位
    public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
    public E get(int index) { checkElementIndex(index); return node(index).item; }
}

實戰驗證：可重複、有序、雙向迭代

1. 元素可重複 + ListIterator 雙向迭代

List chinese = new LinkedList<>(Arrays.asList("甲","乙","乙","丙","丁"));
List english = new LinkedList<>(Arrays.asList("A","B","B","C","D"));

ListIterator ci = chinese.listIterator(); // 支援 hasPrevious/previous
Iterator ei = english.iterator();       // 僅單向

// 正序
while (ci.hasNext()) System.out.print(ci.next() + " - "); 
// 甲 - 乙 - 乙 - 丙 - 丁 -

// 逆序
while (ci.hasPrevious()) System.out.print(ci.previous() + " - "); 
// 丁 - 丙 - 乙 - 乙 - 甲 -

2. ListIterator 修改操作：間隔插入、條件刪除

chinese.removeAll(english); // 移除 english 中所有元素
// 結果：甲 - 乙 - 乙 - 丙 - 丁 -

4. 有序性驗證（十萬元素）

性能對比：LinkedList vs ArrayList

操作
ArrayList
LinkedList
選型建議
隨機訪問 get(i)
O(1) ✓
O(n) ✗
高頻隨機讀 → ArrayList
首尾增刪
O(n) 擴容/搬移
O(1) ✓
隊列/棧/高頻首尾操作 → LinkedList
中間增刪
O(n) 複製
O(n) 定位 + O(1) 改指針
差異不大，ArrayList 緩存友好通常更快
內存佔用
Object[] 緊湊
Node 對象額外 16-24 字節
大數據量 → ArrayList
遍歷
緩存命中率高
指針跳轉，緩存未命中
ArrayList 更快


常見誤區與最佳實踐

作為 List 高頻隨機訪問：極慢 → 改用 ArrayList
併發環境直接使用：非線程安全 → Collections.synchronizedList 或 CopyOnWriteArrayList
作為隊列/棧：首選 ArrayDeque（數組雙端隊列，無 Node 開銷、更快、無容量限制）
頻繁中間插入：考慮跳表或B+樹結構，或接受 ArrayList 複製開銷


總結
LinkedList 是教科書級雙向鏈表實現，完美支撐 Deque 雙端操作與 ListIterator 雙向游標修改。但隨機訪問 O(n)、Node 內存開銷大、緩存不友好，導致實際性能常不如 ArrayList/ArrayDeque。除非明確需要 ListIterator 的游標修改能力，否則優先選 ArrayList 或 ArrayDeque。