Linked List

每個節點自己記住下一個是誰。 · ⏱ 約 40 分鐘

你會學到三件事

1. 一個結構裡放一個指向自己這種結構的指標
2. new 配一個節點，-> 走過去
3. 為什麼它在「中間插入」上贏 vector，而在「拿第 k 個」上輸

開始之前

⚠️ 這一課要先會指標。沒碰過的話先走 C 銜接第 3 課（指標）—— &、*、-> 那三個符號在這裡每一行都會用到。

前面五課用的都是標準函式庫給你的容器。這一課要自己做一個 ——而它同時是第 11 課（圖）和第 13 課（樹）的地基： 那兩種東西也是「節點 ＋ 指向別的節點」。

vector 是一整塊連續的記憶體。

好處是「拿第 k 個」只要算一次位址，O(1)。 壞處是中間插入一個要把後面全部往後搬，O(n)。

Linked List 反過來。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、節點指向下一個節點

一個節點裝著自己的值，和「下一個在哪」：

1struct Node {2    int val;3    Node* next;4};

⚠️ next 是一個指標，而不能是 Node next;。

寫成 Node next; 的話，Node 裡面就會包含一個完整的 Node， 而那個又包含一個……大小無限，編譯器會直接擋你。

指標的大小是固定的（8 個位元組），所以它可以。

積木盤上這一顆寫著「定義結構 …」， 而 Node* next; 那一行是「建立 … 指標變數 … 初始值 …」。

這是「為什麼需要指標」的第二個答案 （第一個是 C 銜接課 C 銜接第 3 課的「改到外面」）： 一個型別可以包含指向自己的指標，而不能包含自己。

二、串起來

new 那一顆在積木上寫著「建立 … 物件（…）」。

把第二個接在第一個後面：

1Node* second = new Node;2second->val = 2;3second->next = NULL;      // ← 最後一個，後面沒有了4 5Node* head = new Node;6head->val = 1;7head->next = second;      // ← 接上去

head              second
┌───┬────┐       ┌───┬──────┐
│ 1 │  ●─┼──────▶│ 2 │ NULL │
└───┴────┘       └───┴──────┘

⚠️ 最後一個的 next 一定要設成 NULL。

不設的話它裡面是垃圾，而走訪會走到一個不存在的地方—— 程式可能當掉，也可能印出一堆亂數然後看起來很正常。

三、走過整條

從頭開始，一直跟著 next 走：

1Node* p = head;2while (p != NULL) {3    cout << p->val << endl;4    p = p->next;5}

p 從頭開始，每一圈往後跳一格，跳到 NULL 就停。

⚠️ p = p->next; 那一行不能忘——這就是C++ 入門第 10 課「迴圈的三樣東西」 裡的變動。忘了就是無窮迴圈。

⚠️ 不要用 head 當那個 p。走完之後 head 會變成 NULL， 而整條串列就找不回來了（那些節點還在記憶體裡，只是沒有人記得它們在哪）。

四、它跟 vector 各自贏在哪

「中間插入是 O(1)」有一個前提：你已經站在那個位置了。

而「走到那個位置」是 O(n)。所以它真正的優勢在 「一邊走一邊改」的情境，不是「隨機插入」。

⚠️ 而現實中 vector 常常贏——因為連續的記憶體對快取友善， 而 Linked List 的每個節點散在各處。大 O 不是全部。

五、⚠️ 用完要還

new 出來的每一個都要自己還回去：

1Node* p = head;2while (p != NULL) {3    Node* nxt = p->next;      // 🔴 先記住下一個4    delete p;5    p = nxt;6}

先存下一個，再 delete。 順序反了的話 p->next 讀的是 一塊已經還掉的記憶體（C 銜接課 C 銜接第 4 課的 use-after-free）。

積木盤上它寫著「刪除物件 …」——與第二節那顆「建立 … 物件」成對。

（這一課的範例沒有 delete，因為程式結束時作業系統會全部收回。 而一支長時間跑的程式不能這樣。）

完成的樣子

1#include <iostream>2using namespace std;3struct Node {4    int val;5    Node* next;6};7 8int main() {9    Node* second = new Node;10    second->val = 2;11    second->next = NULL;12    Node* head = new Node;13    head->val = 1;14    head->next = second;15    Node* p = head;16    while (p != NULL) {17        cout << p->val << endl;18        p = p->next;19    }20    return 0;21}

換你了

在 head 和 second 中間插入一個值為 99 的節點。

head ──▶ [99] ──▶ second

⚠️ 兩行的順序不能反：

mid->next = head->next;    // ① 先接後面
head->next = mid;          // ② 再接前面

反過來的話 head->next 已經被蓋掉，second 就掉了—— 而程式不會報錯，只會少印一個數字。

到編輯器做這一題：練習：在中間插一個 99——而兩行的順序不能反

做一個

做一條 1 → 2 → 3 的串列，把它反過來變成 3 → 2 → 1，再走一遍印出來。

🔴 你需要三個指標：前一個、現在這個、下一個。 ⚠️ 少了「下一個」那一個，你會在改掉 cur->next 的那一瞬間把後面整條弄丟。 先在紙上畫三個箭頭再動手。

到編輯器做這一題：做一個：把串列反過來

這一課你做了什麼

• 你做了一個包含「指向自己這種結構的指標」的結構
• 你用 new 配節點、用 -> 走過整條串列
• 你知道它和 vector 各自贏在哪，以及大 O 不是全部

如果卡住了