链表：从不搬家，代价是问路

上一篇咱们给动态数组留了一道坎：往头部插一个 99，后面 8 个老元素全体右移一格，插得越靠前挪得越多。根子在一个字上——连续。格子必须连成一排，a[i] 才有地址公式可算，缓存才有局部性可用；可也正是这个"连成一排"，定了中间插删的搬运义务：第 0 格要腾给新人，后面所有人都是挡路的。

那把"连续"拆掉呢？数据不需要再挤在一条街上，每个人住自己的房子，房子里留一张纸条写着"下一家在哪"。这一拆，插删的搬运义务没了——代价是找元素再无捷径，只能顺着纸条一家家问过去。这一篇咱们就把链表从节点搭起，把它的便宜和它的代价都拿真跑数据摊开。

把格子拆成节点，用指针串起来

链表的零件是节点：一块数据，加一个指向前方的指针，住在堆上。您可以把 next 想成一张写着"下一家在哪"的纸条，这个比喻咱们整篇都要用。

struct Node {
    int   val;    // 存的数据
    Node* next;   // 指向下一个节点；链尾这里存 nullptr
};

咱们手工串一串三个节点，感受一下这个结构的手感：

Node* head = nullptr;             // 入口指针：空链

Node* c = new Node{30, nullptr};  // 链尾：next 存 nullptr
Node* b = new Node{20, c};        // 中间节点：next 指向 c
Node* a = new Node{10, b};        // 头节点：next 指向 b
head = a;                         // 入口指向头节点

跟上一篇对照着看：head 的角色相当于 IntVec::data，是咱们攥在手里的句柄；区别在于 data 指向的 8 格是一整块连续内存，而 head 指向的第一个节点跟它的下一家毫无地缘关系：三个节点是三次独立的 new，分配器把它们放在哪，它们就住在哪。想访问第三个节点的 30，没有公式，只有一条路：从 head 走到第一家，读它的纸条，走到第二家，再读纸条，第三家才到。

链条的尽头是 nullptr：最后一家纸条上写着"没有了"，这就是咱们遍历的终止条件。整条链的完整性全靠纸条维系：弄丢一张，后面整段就成了找不回的孤儿（泄漏）；写错一张，就会走到不该去的人家（未定义行为）。

插入和删除：改的是纸条，不是房子

现在咱们回来看那道坎。往链表头部插一个 99，要动谁？

void push_front(Node*& head, int x) {
    Node* n = new Node{x, head};  // 新节点的 next 指向原来的头节点
    head = n;                     // head 改指新节点
}

两行，完事。新节点搬进来之前就把纸条写好（指向旧的第一家），然后入口改口。老节点们呢？咱们挨个去问，答案都是：不知道、不关心、不动窝，它们手里纸条上的地址一个都没变。删除同理：拿掉一家，只需要它的前一家把纸条从"指向它"改成"指向它的下一家"，然后 delete 掉这个节点。从"后半段全体挪座"到"改两张纸条"，这就是拆掉连续换来的头一样好处。

咱们把这套动作放到了在线编译器，您可以自己跑、自己改：

Compiler Explorer

手工串链与头插

三个节点手工串起来，push_front 插一个 99，遍历打印，最后逐个释放。您还可以在编辑器里自己加一段中间插入的代码，体会只改指针的插法。

code/examples/vol3/primer_02_node_chain.cpp

咱们拿 std::list（标准库的双向链表，下一篇收尾再细说它）跟 std::vector 对着跑：各自往头部插 10 万元素，三轮计时（MSVC x64 /O2）：

run 1: front-insert 100000 elems | vector =   317366 us | list =   2783 us
run 2: front-insert 100000 elems | vector =   316133 us | list =   2785 us
run 3: front-insert 100000 elems | vector =   317236 us | list =   2546 us

咱们看数字：vector 约 317 毫秒，list 约 2.7 毫秒，百倍上下。这百倍不是什么玄学，原因上一篇就拆过：vector 每次头插都要挪走全部已有元素，10 万元素总共约 50 亿次元素移动；list 每次头插都是常数个动作，分配节点、写两张纸条。O(n) 对 O(1)，规模一大就是数量级。

不过咱们先把话说到前头：上面比的是"头插"，比的是两家结构各自的贵项对便宜项。要论综合胜负，还得把 list 这边的代价也摊开，下面三节挨个算。

没有下标：找元素只剩问路

vector 的 v[900000] 为什么是一步到位？因为格子连续，地址有公式：基地址加 900000 乘以格子宽度，一步算出，纯算术。链表的节点散落堆上，第 900000 个节点住在哪，没有任何公式能算——咱们唯一的办法是从头走 900000 步。所以 std::list 干脆没有 operator[]，写 L[5] 编译都过不了：这不是标准库偷懒，O(1) 的下标链表真的做不到，接口给出来，也只能每次从头走。

咱们真跑对比：同样访问第 90 万元素各 100 次（std::next 是"沿着链走 n 步"的标准写法）：

jump to elem #900000 x 100 tries | vector = 2 us | list = 164761 us

vector 单次约 20 纳秒，list 单次约 1.6 毫秒，差四个数量级开外。更要命的是这份代价没法摊还：vector 的搬家贵在偶尔，摊还之后是常数；链表的问路是每次都贵，走 i 步就是 i 步，咱们问第 10 次和问第 100 万次一样实打实。

于是链表的世界里，"位置"这个概念变了味道。vector 里下标就是位置，拿到就能跳；链表里能一步跳到的位置只有两头（begin() 和 end()，end() 的上一格 rbegin() 也算，双链表尾部有入口），中间的任何位置咱们都得走着去。这也是为什么上一节说删除只需要前驱改纸条、成本 O(1)，却处处带着前提——前提是您已经走到了那儿、手里攥着迭代器。位置本身，是要花 O(n) 买的。

⚠️ "链表插删 O(1)"这句话省略了主语：是"在已知位置插删"O(1)，找位置另算 O(n)。咱们拿它去跟"vector 下标访问 O(1)"打擂台，比的根本不是同一件事。

缓存这一关：散落堆上的代价

第二份代价更隐蔽：它藏在硬件里，咱们光看代码看不出来。

按理说顺序遍历是链表最体面的活：从头走到尾，一步不绕路，复杂度 O(n) 跟 vector 一样。但咱们真跑一下：两容器各装 100 万元素，从头到尾求和，跑 20 轮计时：

walk 1000000 elems x 20 rounds | vector = 2462 us | list = 37271 us | sink = 19999980000000

咱们同样 100 万元素、同样走一遍，list 慢约 15 倍。复杂度一样，常数差出一个数量级，差在缓存上。

CPU 取内存不是按字节取的，是按缓存行（cache line，通常 64 字节）整块搬的。vector 的 100 万个 int 挤在约 4 MB 的连续内存里：一次缓存未命中，64 字节进缓存，16 个 int 全在里面，后面 15 次访问全是缓存命中；而且访问模式是严格的"地址递增"，硬件预取器（prefetcher）认得这个节奏，会提前把后面的行搬进来，等 CPU 真要用时数据已就位。咱们遍历 vector，几乎全程不等待。

链表的节点呢？咱们在地址实验里能直接看到它们住得多散。看真跑输出（std::list 装 8 个元素，打印每个元素的地址）：

list of 8, element addresses:
  [ 0] 0000019B99206B80
  [ 1] 0000019B99206BC0
  [ 2] 0000019B99206C00
  [ 3] 0000019B99206C20
  [ 4] 0000019B99206C40
  [ 5] 0000019B99206C60
  [ 6] 0000019B991FEBB0
  [ 7] 0000019B991FE670

咱们看这份输出：前六个节点恰好住进了同一片街区（这已经是运气好了，连续 push_back 时分配器习惯性地把同尺寸的块往一处放），第七、第八个就被分到了 30 多 KB 之外的另一条街。这还只是 8 个节点；百万节点的链，物理地址上天南海北。每走一步，next 指向的地址都是一次跳跃：一个节点 24 字节，塞不满一条缓存行，一次未命中只服务一个元素；跳跃的地址毫无规律，预取器彻底失业。每个元素一次缓存未命中，这 15 倍就是这么攒出来的。

这条经验值得咱们单独记下：复杂度相同，物理布局不同，性能可以差一个数量级。往后您读到任何"链表还是数组"的讨论，局部性都是绕不开的隐藏变量；本教程后面讲容器选择、讲数据结构设计，还会反复回到这一课。

每个节点多背的指针

第三份代价最直白：内存。节点要带纸条，纸条本身占地方，咱们真跑一下（x64）：

sizes: int=4 ptr=8 DNode=24 SNode=16 std::list<int>=16 std::forward_list<int>=8

咱们拿 DNode 算算：它是双向链表的节点（数据加 next、prev 两个指针），4 字节的 int，配上 16 字节指针再加 4 字节对齐填充，一个节点 24 字节。装 4 字节数据，住 24 字节的房子，六倍开销。单链表的 SNode 少一个 prev，16 字节，也有四倍。这不是 std::list 笨，是链表这个结构天生就得这么造：标准库的 std::list 节点同样是"一个值加两个指针"的身材。

好消息是这个比例随元素变大而摊薄：存 int 时指针占三分之二，您要是存 1 KB 的结构体，指针就只占百分之一点五了。所以"链表内存开销大"要辩证着说：小元素密集的场景才是重灾区，恰好这类场景又最吃上一节的缓存亏，两个短板经常一起出现。

输出里最后两个数也值得咱们多看一眼：std::list<int> 对象本身只有 16 字节，双链表两头各一个入口指针，苗条得很；std::forward_list<int> 更是只有 8 字节，单指针。不过 forward_list 省得不只是节点：它连 size() 都没提供。为什么？因为单链表要数清自己有几个元素，只能全链走一遍 O(n)，标准索性不给这个接口，逼着不需要计数的使用方省下每个节点里的计数开销。省到这个份上，连 API 都跟着改了。

从不搬家意味着什么：地址、迭代器与 splice

三份代价都摊完了，咱们回头看链表最值钱的性质：节点从生到死住在同一个地址。不搬家，意味着指向节点的指针、引用、迭代器不会因为别的插入删除而失效；对照上一篇 vector"搬家等于旧地址全废"，这是方向性的差别。空口无凭，上真跑。

第一个实验：咱们删掉链表中间一个节点，看其余节点的地址如何？

after erasing the node holding 4:
  [ 0] 0000019B99206B80
  [ 1] 0000019B99206BC0
  [ 2] 0000019B99206C00
  [ 3] 0000019B99206C20
  [ 5] 0000019B99206C60
  [ 6] 0000019B991FEBB0
  [ 7] 0000019B991FE670

咱们对照删除前的清单：剩下的 7 个节点，地址一位都没动。被删的那家房子退了（delete），前后两家纸条重写，其余人照旧过日子。同一实验里 vector 删掉 v[4] 之后呢？元素 5 住进了原来 4 的地址，6 住进原来 5 的，7 住进原来 6 的，后半段全体往前挪一格，物理上真搬了。

这个实验您也可以在线跑：

Compiler Explorer

删除节点，其余地址纹丝不动

删掉值为 4 的节点，其余 7 个节点的地址和删除前完全一致。您有兴趣的话把 std::list 换成 std::vector 做同样的事，地址会集体前移：上一篇那一幕就重演了。

code/examples/vol3/primer_02_address_stability.cpp

第二个实验更有味道，是链表的招牌菜 splice（剪接）：把一条链中间的一段，整段剪下来接到另一条链上。咱们把 b 链中间的 11、12、13 剪到 a 链尾部：

after splice: a = 0 1 2 11 12 13 | b = 10 14
node addresses now: 11@0000019B991FE5F0 12@0000019B991FE5B0 13@0000019B991FE990 (unchanged)

咱们把三个节点的地址再对一遍：换了主人，一字不变——搬的是归属，不是房子。这个操作只重写了边界上的几根指针（a 尾接到 11、13 接 b 剩下的 14），一个元素都没碰，O(1) 完工。同样的事让 vector 做，得把三个元素拷过去再把 b 的尾巴前移补洞，两头都是 O(n)。凡是"把一段数据在容器间倒手"的场景（任务队列合流、缓冲区移交、定时器轮片搬迁），链表这个"只改归属"的能力都是独门优势。

⚠️ 链表迭代器唯一的失效方式是指向的节点被删。咱们删除时用 it = L.erase(it) 接住返回的下一个位置继续走，这是链表遍历删除的标准姿势；拿着已删节点的迭代器继续解引用，跟上一篇悬空指针是同一种事故。

什么时候轮到链表

三份代价（问路 O(n)、缓存吃亏、指针开销）对一项长处（已知位置插删 O(1) 且地址稳定），选择的轮廓其实清楚了：咱们手里已经攥着位置、且之后要在这些位置上频繁插删的，链表赢：维护一堆长期活着的观察者/回调、LRU 缓存的淘汰链、定时器队列，都是这个形态；反过来，按下标访问、整段扫描为主的，vector 赢，而且赢得比复杂度表上更狠（那 15 倍的常数差）。

还有个常被忽略的中间派：对象大、移动贵的元素，链表的"从不搬家"和 vector 的"扩容整体搬迁"对比会进一步放大：搬一个 8 字节 int 是 memmove 里的一瞬，搬一百万个非平凡对象就是实打实的析构加构造风暴（上一篇提过的 move_if_noexcept 讲究就在那）。正式的 std::list、std::forward_list 用法与坑（merge、sort 为什么是链表特有的版本、跟 deque 的三角关系），在本卷 deque、list 与 forward_list 一篇展开；想亲手搓一条，vol8 的 mini STL 实战在排队等咱们。

primer 的下一站是哈希表：一个把这两篇捏在一起的结构——数组做索引、链表做货舱，随机访问的快和插删的活，它各借了一半。咱们下篇见。

参考资源

• cppreference：std::list——复杂度承诺、迭代器失效规则、splice/merge 的语义
• cppreference：std::forward_list——单链表，以及"为什么没有 size()"的设计说明
• 本卷 deque、list 与 forward_list——std::list 的深讲与容器间取舍
• 本系列 上一篇：动态数组，一块会搬家的内存——连续存储的代价清单，本篇的对照组