跳到主要內容
Jasonmel Online

資料結構

資料怎麼排，決定了哪些操作便宜

主題 · 鏈結串列

鏈結串列

每個節點記住下一個在哪：在手上的位置插入或刪除只要改兩個指標，但要找第 i 個就得從頭一個一個走。

  1. head →
  6. null

方框下面是節點的位址：插入和刪除之後，其他節點的位址都不變。

沿著指標走過新節點／找到的節點

每個節點只知道下一個節點的位址。點一個節點選取它，再試試在它後面插入：沒有任何節點會被搬動。

節點
4
這次走過幾個節點
–
這次改了幾個指標
–
亮起來的是這一步執行的程式碼
class ListNode {
  next: ListNode | null = null;
  constructor(public value: number) {}
}
 
class LinkedList {
  head: ListNode | null = null;
 
  pushFront(value: number): void {
    const node = new ListNode(value);
    node.next = this.head;
    this.head = node;
  }
 
  get(index: number): number | undefined {
    let node = this.head;
    for (let i = 0; i < index && node; i++) {
      node = node.next;
    }
    return node?.value;
  }
 
  insertAfter(index: number, value: number): void {
    let node = this.head;
    for (let i = 0; i < index && node; i++) {
      node = node.next;
    }
    if (!node) return;
    const fresh = new ListNode(value);
    fresh.next = node.next;
    node.next = fresh;
  }
 
  removeAt(index: number): void {
    if (!this.head) return;
    if (index === 0) {
      this.head = this.head.next;
      return;
    }
    let prev = this.head;
    for (let i = 0; i < index - 1 && prev.next; i++) {
      prev = prev.next;
    }
    if (prev.next) prev.next = prev.next.next;
  }
 
  indexOf(value: number): number {
    let i = 0;
    for (let node = this.head; node; node = node.next) {
      if (node.value === value) return i;
      i++;
    }
    return -1;
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 常常在已經拿到的位置插入或刪除（例如 LRU（Least Recently Used，最近最少使用）快取把節點移到最前面），而不需要用索引直接讀第幾個。
  • 需要穩定的位址：節點不會因為擴容被搬走，別人手上的指標一直有效。
  • 當作其他結構的零件：雜湊表的鏈、LRU、堆疊和佇列的另一種實作。

和其他主題的關係

延伸閱讀
動態陣列

語言內建的版本

class ListNode

JavaScript 沒有內建的鏈結串列。題目（例如 LeetCode）都會給一個 ListNode 類別，自己用 next 串起來。

操作寫法成本
頭端插入head = new ListNode(0, head)O(1)
在節點後插入node.next = new ListNode(9, node.next)O(1)
刪除下一個node.next = node.next!.nextO(1)
找第 i 個for (let i = 0; i < 2; i++)O(n)
class ListNode {
  constructor(public val = 0, public next: ListNode | null = null) {}
}
const toArray = (node: ListNode | null) => {
  const out: number[] = [];
  for (; node; node = node.next) out.push(node.val);
  return out;
};
 
let head: ListNode | null = new ListNode(1, new ListNode(2, new ListNode(3)));
head = new ListNode(0, head);
toArray(head);                       // → [0, 1, 2, 3]
 
let node = head;
for (let i = 0; i < 2; i++) node = node.next!;
node.val;                            // → 2
node.next = new ListNode(9, node.next);
toArray(head);                       // → [0, 1, 2, 9, 3]
node.next = node.next!.next;
toArray(head);                       // → [0, 1, 2, 3]
 
// Reverse in place: three pointers, one pass.
let prev: ListNode | null = null;
for (let cur: ListNode | null = head; cur; ) [cur.next, prev, cur] = [prev, cur, cur.next];
toArray(prev);                       // → [3, 2, 1, 0]

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • 實務上很少需要自己寫鏈結串列：陣列加索引幾乎總是比較快。會寫它主要是為了面試題和理解 LRU 快取這類組合結構。
  • 刪除或插入時先想清楚頭節點會不會變。常見做法是在最前面放一個假的 dummy 節點，回傳 dummy.next。

時間與空間複雜度（Big O）

操作平均最差
讀第 i 個O(n)O(n)
在開頭插入或刪除O(1)O(1)
在手上的節點後面插入
先走到那個位置的話就是 O(n)
O(1)O(1)
刪除某個節點
單向串列要先找到前一個；雙向串列拿著節點就是 O(1)
O(n)O(n)
找某個值O(n)O(n)

空間：O(n)，每個節點多一個指標，雙向串列多兩個

Big O 實測：n 變大時步數怎麼長

數的是：走過的節點或寫入的指標（200 次取平均）

Big On = 1,000n = 10,000n = 100,000成長倍數：實測（理論）
讀第 i 個（平均）O(n)5015,00150,001×100 (×100)
找某個值（平均）O(n)5015,00150,001×100 (×100)
在開頭插入O(1)222×1.0 (×1.0)

和其他做法比

鏈結串列動態陣列
讀第 i 個500.51
在開頭插入21,001
在手上的位置後面插入2500.5
找某個值500.5500.5

1,000 個元素，數走過的節點、改的指標或搬動的格子（取平均）。兩者剛好互補：陣列讀得快、插入要搬；串列插入只改 2 個指標、讀取要走。找值兩邊都得一個一個看。

真實世界裡的它

  • LRU 快取的雙向串列、雜湊表每個桶子裡的鏈（見上方的關聯）。
  • Linux 核心到處都是 list_head 雙向串列：行程清單、等待佇列、空閒記憶體區塊。
  • Java 的 LinkedList、C++ 的 std::list；Lisp 和 Haskell 的 list 本身就是單向串列。

取捨與陷阱

  • 讀第 i 個要走 i 步：在迴圈裡用 get(i) 走訪整個串列，整段會變成 O(n²)，要用迭代器一路往下走。
  • 節點散在記憶體各處，CPU 快取幾乎幫不上忙：同樣是 O(n) 的掃描，實際上常比陣列慢好幾倍。
  • 每個節點多存一到兩個指標：存小整數時，指標可能比資料本身還大。

LeetCode 練習