Linked List

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

你會學到三件事

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

開始之前

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

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

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

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

Linked List 反過來。

一、節點指向下一個節點

struct Node {
    int val;
    Node* next;
};

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

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

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

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

二、串起來

Node* second = new Node;
second->val = 2;
second->next = NULL;      // ← 最後一個，後面沒有了

Node* head = new Node;
head->val = 1;
head->next = second;      // ← 接上去

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

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

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

三、走過整條

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

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

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

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

四、它跟 vector 各自贏在哪

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

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

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

五、⚠️ 用完要還

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

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

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

完成的樣子

struct Node {
    int val;
    Node* next;
};

int main() {
    Node* second = new Node;
    second->val = 2;
    second->next = NULL;
    Node* head = new Node;
    head->val = 1;
    head->next = second;
    Node* p = head;
    while (p != NULL) {
        cout << p->val << endl;
        p = p->next;
    }
    return 0;
}

換你了

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

head ──▶ [99] ──▶ second

⚠️ 兩行的順序不能反：

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

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

這一課你做了什麼

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

如果卡住了