链表

寻宝游戏，而非一排书架

把数组想象成一排紧挨着、编了号的储物柜。要找第 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`（单向），而不是自己手写节点——但亲手写一遍，指针的那套来回腾挪才会真正豁然开朗。接下来手写栈和队列时，我们会用到这些。