鏈結串列

尋寶遊戲，而非一排書架

把陣列想像成一排緊挨著、編了號的置物櫃。要找第 5 號櫃，你徑直走過去就行。鏈結串列更像一場尋寶遊戲：每條線索只告訴你*下一條*線索在哪。每件物品叫一個節點，每個節點存著一個值，外加一個指標——也就是下一個節點的位址。

正因為節點不必在記憶體裡彼此相鄰，鏈結串列可以一次只加一個節點地增長，而無需把全部元素複製到更大的記憶體塊——這是固定大小的陣列做不到的。

head -> [1|.] -> [2|.] -> [3|/]    (/ = nullptr)
        |          ^
        value      pointer to next node

用 C++ 寫一個節點

一個節點就是一個小小的結構體：一個值，加一個指向同類型下一個節點的指標。整條鏈結串列只用一個指向首節點的 `head` 指標來標識；末節點指向 `nullptr`，表示結束。

struct Node {
    int v;            // the value
    Node* next;       // pointer to the next node (or nullptr)
};

// Build  1 -> 2 -> 3  by hand:
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};

要走訪鏈結串列，從 `head` 出發，沿著 `next` 走，直到碰上 `nullptr`。這叫走訪，它會把每個節點存取一次——所以走訪全部節點是 O(n)。

for (Node* cur = head; cur != nullptr; cur = cur->next) {
    std::cout << cur->v << ' ';   // prints: 1 2 3
}

鏈結串列的強項與軟肋

一句話講清這個權衡。一旦你已經握有指向某個位置的指標，在那裡插入或刪除就是 O(1)：只需重接兩個指標，無需移動元素。但要先找到那個位置，就得從頭走訪——O(n)。對比陣列：按索引存取是 O(1)，但在中間插入是 O(n)，因為後面的元素都得挪位。

1. 在頭部插入：新建一個節點，讓它的 next 指向舊 head，再把 head 移到它身上。O(1)。
2. 刪除你手裡已有指標的節點：讓前一個節點的 next 越過它。O(1)——然後釋放記憶體。
3. 按位置存取第 k 個元素：沒有捷徑——從 head 走 k 個節點。O(n)。

單向鏈結串列與雙向鏈結串列

上面那條是單向鏈結串列：每個節點只知道它的後繼，所以只能向前走。雙向鏈結串列給每個節點再加一個 `prev` 指標，於是你也能往回走——而且只要拿到某個節點本身就能刪除它（因為能找到它的前驅）。代價是每個節點多花一個指標的記憶體。

      .---.     .---.     .---.
null<-|prev|<-->|prev|<-->|prev|->null
      | 1 |     | 2 |     | 3 |
      |next|<-->|next|<-->|next|
      '---'     '---'     '---'

在真實的 C++ 裡，你通常會直接用 `std::list`（雙向）或 `std::forward_list`（單向），而不是自己手寫節點——但親手寫一遍，指標的那套來回騰挪才會真正豁然開朗。接下來手寫堆疊和佇列時，我們會用到這些。