演算法系列 · 第 7 關 · 資料結構

鏈結串列 Linked List

節點牽著節點,靠指標串起來。插入、刪除只要改幾條線,超快 —— 但要找第幾個就得從頭走。

鏈結串列是一串節點(node),每個節點裝一個值加一個指向下一個節點的指標(next)。節點不用連在一起,散在記憶體各處靠指標串成一條線。好處是插入、刪除只要改指標(O(1)),壞處是要拿第幾個得從頭一個一個走(O(n))—— 剛好跟陣列相反。

核心觀念:節點 + 指標

1. 節點裝兩樣東西 —— 一個值,加一個指向下一個節點的指標 next。

2. 不用連在一起 —— 節點散落在記憶體各處,靠指標串起來(陣列則是緊緊相鄰的一整排)。

3. head 是唯一入口 —— 只記得第一個節點 head;最後一個的 next 指向 None,代表結束。

4. 要走訪只能沿線走 —— 從 head 沿著 next 一個一個往下跳,沒有「編號直取」這回事。

陣列插一個要搬一整排;鏈結串列只要改幾條線,其他節點動都不動。

插入 —— 新節點的 next 指向後面那個,前一個的 next 改指向新節點,2 步搞定。

刪除 —— 前一個的 next 直接跳過它、指向它的下一個,那個節點就被繞過(等於刪掉)。

前提 —— 你得先「走到」那個位置。走過去是 O(n),但改指標本身是 O(1)。

一句話記住陣列 vs 鏈結串列:陣列「看得快、動得慢」(直取 O(1)、搬家 O(n)),鏈結串列「看得慢、動得快」(走訪 O(n)、改指標 O(1))。看你的程式常做哪件事來選。

O(1)頭部插入 / 刪除 —— 或已經站在某節點時插入刪除。只改幾個指標,不搬任何節點。

O(n)依序號存取 / 搜尋 —— 拿第 k 個、或找某個值,都得從 head 一步步走。

O(n)空間 —— 除了值,每個節點還要多存一個指標,比陣列費一點記憶體。

需要大量「用編號直取」就別用它。鏈結串列的甜蜜點是「常在頭尾或中間插拔、但很少用序號亂跳存取」的場景,例如實作堆疊、佇列,或 LRU 快取。

🚂

每節車廂只知道「下一節是誰」。要到第 5 節,得從車頭一節一節走過去,不能瞬間跳到。

🧭

每張紙條寫著「下一張在哪」,一張接一張找,沒辦法直接翻到最後一張。

🔗

中間要插一個人進來,只要左右兩人改牽新來的就好,其他人站著不用動。

一條 head → 5 → 8 → 2 → None 的串列。走訪得從 head 一格格走(O(n));插入、刪除只要改指標,別的節點不動(O(1))。紫色是正在看的節點或正在改的那條線、綠色是命中或新節點。選一個操作,按「下一步」。

選操作:

Python 沒有內建鏈結串列,我們用 Node class 自己兜 —— 從建立、走訪、頭尾插入,到反轉、偵測環等經典面試題。

❌ 忘了特別處理 head —— 在頭部插入、或刪除的剛好是 head 時要單獨寫,不然會接錯或漏掉。

❌ 改指標前沒先存住 next —— 反轉、刪除時一旦改了指標又沒記住下一個,後面整串就斷掉找不回來。

❌ 走訪迴圈忘了 cur = cur.next —— 指標沒往前推,會卡在原地變無窮迴圈。

❌ 把它當陣列用 —— 需要大量「用編號直取」就別用鏈結串列,那是 O(n),改回 list。

把答案打到對話裡,我幫你對。