計算機程序思維邏輯第 39 講：LinkedList 源碼深度解析與 ArrayList 對比

計算機程序思維邏輯第 39 講：LinkedList 源碼深度解析與 ArrayList 對比

上講介紹了 ArrayList（動態數組），隨機訪問 O(1) 但插入刪除 O(N)。本講深入剖析同樣實現 List 接口的 LinkedList，其底層為雙向鏈表，特點幾乎與 ArrayList 相反：兩端操作 O(1)、隨機訪問 O(N)。同時實現 Deque/Queue 接口，可作棧、隊列、雙端隊列使用。

一、核心用法速覽

構造方法

public LinkedList()                           // 空鏈表
public LinkedList(Collection<? extends E> c)  // 從集合初始化

List 接口

完全兼容 Collection/Iterable 所有方法（add/get/set/remove/contains/indexOf 等），用法與 ArrayList 一致。

Queue 隊列 (FIFO)

Queue<String> q = new LinkedList<>();
q.offer("a"); q.offer("b"); q.offer("c");  // 尾部入隊
while (q.peek() != null) System.out.println(q.poll()); // 頭部出隊: a b c

Stack 棧 (LIFO) - 通過 Deque 實現

Deque<String> stack = new LinkedList<>();
stack.push("a"); stack.push("b"); stack.push("c");
while (stack.peek() != null) System.out.println(stack.pop()); // c b a

Deque 雙端隊列

Deque<String> dq = new LinkedList<>(Arrays.asList("a","b","c"));
dq.addFirst("head"); dq.addLast("tail");
System.out.println(dq.pollFirst()); // head
System.out.println(dq.pollLast());  // tail
// 反向迭代器
for (Iterator<String> it = dq.descendingIterator(); it.hasNext(); )
    System.out.print(it.next() + " "); // c b a

二、源碼級實現原理

內部節點類

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

三大核心字段

transient int size = 0;
transient Node<E> first;  // 頭節點
transient Node<E> last;   // 尾節點

add(e) - 尾部插入 O(1)

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

get(index) - 隨機訪問 O(N/2)

Node<E> node(int index) {
    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;
    }
}

add(index, e) - 中間插入 O(N) 定位 + O(1) 鏈接

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null) first = newNode;
    else pred.next = newNode;
    size++; modCount++;
}

remove(index) - 中間刪除 O(N) 定位 + O(1) 鏈接

E unlink(Node<E> x) {
    final Node<E> next = x.next, 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; size--; modCount++; return x.item;
}

三、特點總結與選型指南

四、思考題

ArrayList 與 LinkedList 按內容查找都是 O(N)，有沒有 O(1) 或 O(logN) 的數據結構？

👉 下講揭曉：HashSet/HashMap/TreeSet 基於哈希表與紅黑樹實現高效查找。

關注公眾號「老馬說編程」獲取完整系列：從入門到高級，深入淺出探索 Java 編程本質。