第 4 章　链表

本章解决的问题：有没有一种结构，插入和删除真的是 $O(1)$？代价是什么？以及为什么"链表插入快"这句话只说对了一半。

4.1　节点与引用：链表的本质

学习目标：学完本节，你能

  • 说清「节点」「引用」「头指针」分别是什么；
  • 算出链表相对数组的空间开销，并解释这 8 倍花在了哪里；
  • 用实测数据说清链表与数组的取舍，而不是背"链表插入快"这种口号。

先修：3.1（连续内存与缓存行）、3.2（动态数组）。 固定术语：链表、节点、引用、头指针、哨兵节点（4.3 节）。 环境与版本：.NET 8 / C# 12，x64。 预计阅读：25 分钟。

一、直觉：一场寻宝游戏

数组像连号的储物柜 —— 你知道第 1 个在哪，就能算出第 7 个在哪。

链表像一场寻宝游戏：

  • 你手里只有第一张纸条（头指针），上面写着第一个线索的位置；
  • 第一个线索里除了内容，还写着下一个线索藏在哪里；
  • 你只能一个接一个地找下去，直到某个线索写着"没有了"（null）。

这个比喻直接对应链表的三个特征：

寻宝 链表
第一张纸条 头指针 head
线索（内容 + 下一个的位置） 节点（数据 + Next 引用）
"没有了" null

也直接对应它的两个代价：

  1. 想找第 7 个线索？ 必须从头一个接一个找过去 —— 没有"下标访问"这回事。
  2. 纸条散落在各处。 每找一张都要跑一趟 —— 而数组的元素都放在同一个柜子里。

二、形式化：节点与引用

链表（Linked List）：由节点通过引用串起来的数据结构。

节点（Node）里装两样东西：

┌──────────┬──────────┐
│  Value   │   Next   │───┐
│  数据     │  引用     │   │
└──────────┴──────────┘   │
                          ↓ 指向下一个节点

用 C# 定义就是：

public class Node
{
    public int Value;        // 数据
    public Node? Next;       // 指向下一个节点的引用
}

关键理解 引用（Reference）这两个字：

Node a = new Node(10);      // a 里存的是「堆上那个对象的地址」
Node b = new Node(20);
a.Next = b;                 // 把 b 里存的地址，复制一份给 a.Next

a 和 b 本身是很小的变量（x64 上 8 字节，就是一个地址）。它们不包含数据，只指向数据。

所以 a.Next = b 这个操作极其便宜 —— 它只是复制一个 8 字节的地址，没有任何数据被移动。

这就是链表插入删除是 $O(1)$ 的全部秘密：要"把 b 接到 a 后面"，不需要搬运任何元素，只需要改几个地址。

头指针（Head）：指向第一个节点的引用。整个链表只需要记住这一个东西 —— 有了它就能走到所有节点。

null：表示"这里没有节点了"。最后一个节点的 Next 是 null，代表链表的结束。

三、实验一：链表长什么样

新建控制台项目，粘贴以下代码：

using System.Diagnostics;

// ==================== 实验一：手动构造一条链表 ====================

Console.WriteLine("=== 实验一：链表长什么样 ===");
Console.WriteLine();

Node a = new(10);
Node b = new(20);
Node c = new(30);
a.Next = b;
b.Next = c;
// c.Next 保持 null，表示链表到此结束

Node head = a;                       // 只要记住「头」，就能找到整条链

Console.Write("  链表内容: ");
for (Node? p = head; p != null; p = p.Next)
    Console.Write($"{p.Value} -> ");
Console.WriteLine("null");
Console.WriteLine();

// 只持有 b 这个节点，能访问到它后面的全部内容吗？
Console.Write("  从中间节点 b 出发: ");
for (Node? p = b; p != null; p = p.Next)
    Console.Write($"{p.Value} -> ");
Console.WriteLine("null   <- 但访问不到前面的 10 了，这就是「单向」的含义");
Console.WriteLine();

// ==================== 实验二：内存占用对比 ====================

const int N = 1_000_000;

Console.WriteLine($"=== 实验二：存储 {N:N0} 个整数的内存占用 ===");
Console.WriteLine();

long before = GC.GetTotalMemory(true);
int[] arr = new int[N];
for (int i = 0; i < N; i++) arr[i] = i;
long afterArr = GC.GetTotalMemory(true);

// 链表 A：顺序分配。节点一个接一个 new 出来，在堆上大概率挨在一起
Node listHead = new(0);
Node cur = listHead;
for (int i = 1; i < N; i++)
{
    cur.Next = new Node(i);
    cur = cur.Next;
}
long afterList = GC.GetTotalMemory(true);

double arrMb = (afterArr - before) / 1024.0 / 1024.0;
double listMb = (afterList - afterArr) / 1024.0 / 1024.0;

Console.WriteLine($"  int[]  : {arrMb,7:F1} MB   (每个元素 4 字节，紧密排列)");
Console.WriteLine($"  链表   : {listMb,7:F1} MB   (每个节点都要单独分配一个对象)");
Console.WriteLine($"  链表多占 {listMb / arrMb:F1} 倍内存");
Console.WriteLine();

// ==================== 实验三：遍历性能对比 ====================

Console.WriteLine("=== 实验三：遍历 100 万个元素 ===");
Console.WriteLine();

// 链表 B：分散分配。每建一个节点就夹一个无用对象，模拟真实运行时堆的碎片化
//（真实系统里，节点是陆续创建删除的，中间还夹着别的对象）
var junk = new List<byte[]>();
Node scatteredHead = new(0);
Node sc = scatteredHead;
for (int i = 1; i < N; i++)
{
    junk.Add(new byte[16]);              // 制造内存「噪音」
    sc.Next = new Node(i);
    sc = sc.Next;
}
GC.KeepAlive(junk);

// 预热：让 JIT 编译好
long warm = 0;
for (int i = 0; i < N; i++) warm += arr[i];
for (Node? p = listHead; p != null; p = p.Next) warm += p.Value;
for (Node? p = scatteredHead; p != null; p = p.Next) warm += p.Value;
GC.KeepAlive(warm);

var sw = Stopwatch.StartNew();
long sumArr = 0;
for (int i = 0; i < N; i++) sumArr += arr[i];
sw.Stop();
double arrMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
long sumList = 0;
for (Node? p = listHead; p != null; p = p.Next) sumList += p.Value;
sw.Stop();
double listMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
long sumScattered = 0;
for (Node? p = scatteredHead; p != null; p = p.Next) sumScattered += p.Value;
sw.Stop();
double scatteredMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  数组               : {arrMs,8:F2} ms   和 = {sumArr:N0}");
Console.WriteLine($"  链表（节点挨在一起）: {listMs,8:F2} ms   和 = {sumList:N0}   慢 {listMs / arrMs,5:F1} 倍");
Console.WriteLine($"  链表（节点分散）    : {scatteredMs,8:F2} ms   和 = {sumScattered:N0}   慢 {scatteredMs / arrMs,5:F1} 倍");
Console.WriteLine();
Console.WriteLine("  三者都是 O(n)，加法次数完全一样。差距全部来自内存布局：");
Console.WriteLine("    数组元素连续排列，CPU 一次读一整条缓存行（64 字节）就能拿到 16 个 int；");
Console.WriteLine("    链表每跳一个节点都要先读它的 Next 引用，而节点散落在堆上，容易缓存未命中。");
Console.WriteLine();
Console.WriteLine("  注意第二行和第三行的区别：同样是链表、同样的数据、同样的代码，");
Console.WriteLine("  只因为节点在内存里「挨着」还是「散着」，速度就能差好几倍。");
Console.WriteLine("  而这个分布往往不由你控制 —— 真实系统里的节点是陆续创建、删除的。");
Console.WriteLine();

// ==================== 实验四：头部插入对比 ====================

const int M = 100_000;

Console.WriteLine($"=== 实验四：在头部插入 {M:N0} 个元素 ===");
Console.WriteLine();

// 预热
{
    var wl = new List<int>();
    for (int i = 0; i < 20_000; i++) wl.Insert(0, i);
    Node wh = new(-1);
    for (int i = 0; i < M; i++) wh = new Node(i) { Next = wh };
}

sw.Restart();
var arrHead = new List<int>();
for (int i = 0; i < M; i++) arrHead.Insert(0, i);       // 每次都要把后面全部挪一格
sw.Stop();
double arrHeadMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
Node listHead2 = new(-1);
for (int i = 0; i < M; i++)
{
    Node newNode = new(i);
    newNode.Next = listHead2;                            // 改两个引用就完事
    listHead2 = newNode;
}
sw.Stop();
double listHeadMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  List<int>.Insert(0,..) : {arrHeadMs,9:F2} ms   每次 O(n)，总共 O(n^2)");
Console.WriteLine($"  链表头插               : {listHeadMs,9:F2} ms   每次 O(1)");
Console.WriteLine($"  链表快 {arrHeadMs / listHeadMs:F1} 倍");
Console.WriteLine();
Console.WriteLine("  这就是链表存在的理由：插入删除不用挪动任何已有元素，只改几个引用。");
Console.WriteLine();

// ==================== 节点定义 ====================

/// <summary>单向链表的一个节点：一份数据 + 一个指向下一个节点的引用</summary>
public class Node
{
    public int Value;
    public Node? Next;

    public Node(int value) => Value = value;
}

实测输出（.NET 8 Release）：

=== 实验一：链表长什么样 ===

  链表内容: 10 -> 20 -> 30 -> null

  从中间节点 b 出发: 20 -> 30 -> null   <- 但访问不到前面的 10 了，这就是「单向」的含义

=== 实验二：存储 1,000,000 个整数的内存占用 ===

  int[]  :     3.8 MB   (每个元素 4 字节，紧密排列)
  链表   :    30.5 MB   (每个节点都要单独分配一个对象)
  链表多占 8.0 倍内存

=== 实验三：遍历 100 万个元素 ===

  数组               :     0.22 ms   和 = 499,999,500,000
  链表（节点挨在一起）:     0.83 ms   和 = 499,999,500,000   慢   3.8 倍
  链表（节点分散）    :     1.62 ms   和 = 499,999,500,000   慢   7.4 倍

=== 实验四：在头部插入 100,000 个元素 ===

  List<int>.Insert(0,..) :    200.30 ms   每次 O(n)，总共 O(n^2)
  链表头插               :      0.24 ms   每次 O(1)
  链表快 843.0 倍

四、读实验二：那 8 倍内存花在哪了

占用 每个元素
int[] 3.8 MB 4 字节
链表 30.5 MB 约 32 字节

每个节点占了约 32 字节，而数据本身只有 4 字节。 多出来的 28 字节是：

组成 大小（x64）
对象头（Object Header） 8 字节
方法表指针（Method Table Pointer） 8 字节
Value（int） 4 字节
Next（引用） 8 字节
内存对齐填充 4 字节
合计 32 字节

这是链表一个经常被忽略的成本：存储 $n$ 个整数，数组要 $4n$ 字节，链表要 $32n$ 字节 —— 整整 8 倍。

10 万个订单可能无所谓，1000 万个就是 320 MB vs 40 MB 的差别。在内存受限的环境里，这个账必须先算。

五、读实验三：同样是 $O(n)$，差了 3.8 倍和 7.4 倍

3.1 节留下过一个伏笔，现在答案揭晓了。

三个循环做的事情完全一样：100 万次加法。 但：

耗时 相对数组
数组遍历 0.22 ms —
链表遍历（节点挨在一起） 0.83 ms 慢 3.8 倍
链表遍历（节点分散） 1.62 ms 慢 7.4 倍

为什么会慢？

  1. 额外的内存访问。 遍历链表时，每到一个节点，必须先读它的 Next 引用才能知道下一个在哪。数组则是一次读取就拿到数据，下一个位置可以直接算出来。
  2. 缓存未命中。 数组元素连续，CPU 读一条缓存行（64 字节）就装进了 16 个 int，后面 15 次几乎免费。链表节点散落在堆上，每跳一次都可能要去主内存取。
  3. 无法预取。 CPU 有硬件预取器，能识别"顺序访问"模式并提前把后面的数据拉进缓存。链表的跳转地址要等前一个节点读出来才知道，预取器无能为力。

第二行和第三行的对比最值得看：同样的链表、同样的数据、同样的代码，只因为节点在内存里"挨着"还是"散着"，速度差了接近 1 倍。

而这恰恰暴露了链表最麻烦的地方：

链表的性能取决于节点的内存分布，而这个分布往往不由你控制。

实验里"顺序分配"的链表之所以快，是因为我刚把它们连续 new 出来，堆上恰好挨着。但真实系统里，节点是陆续创建、陆续删除的，中间还夹着别的对象 —— 更接近"分散"那一行。

所以真实场景中，链表遍历通常比数组慢 5～10 倍，而不是 $O(n)$ 分析所暗示的"差不多"。

六、读实验四：链表存在的理由

  List<int>.Insert(0,..) :    200.30 ms   每次 O(n)，总共 O(n^2)
  链表头插               :      0.24 ms   每次 O(1)
  链表快 843.0 倍

这是链表唯一无法被数组替代的能力：在已知位置插入/删除，代价是 $O(1)$。

数组头插要挪动后面所有元素，10 万次就是 $\frac{n^2}{2} = 5 \times 10^9$ 次元素移动。

链表头插只需两步：

newNode.Next = listHead;    // 新节点的 Next 指向原来的头
listHead = newNode;         // 头指针改指向新节点

改两个地址，结束。

注意措辞的精确性：是"在已知位置插入删除是 $O(1)$"。

如果你只知道"要删除值等于 X 的节点"，那先得找到它，这一步是 $O(n)$。所以"删除一个值"整体是 $O(n)$。

链表的 $O(1)$ 插入删除，前提是你已经拿着那个节点（或它的前驱）的引用了。这个区别在 4.2 节会展开。

七、链表 vs 数组：完整取舍表

数组（List<T>） 链表（LinkedList<T>）
按下标访问 $O(1)$ $O(n)$
头部插入/删除 $O(n)$ $O(1)$
尾部插入/删除 摊还 $O(1)$ $O(1)$
已知节点处插入/删除 不适用（没有"节点"概念） $O(1)$
按值查找 $O(n)$（有序时 $O(\log n)$） $O(n)$
遍历 $O(n)$，缓存极友好 $O(n)$，缓存极不友好（慢 3.8～7.4 倍）
每元素额外内存 0（紧凑） 约 28 字节（8 倍开销）
随机访问 支持 不支持
实现复杂度 低 中（边界情况多）

一句话总结： 数组赢在"读"，链表赢在"改"。 而现实中"读"（遍历、查找、访问）出现的频率，通常远高于"在已知位置改"。

这就是为什么 List<T> 是 C# 的默认选择，而 LinkedList<T> 需要你专门去想起来用它。 微软的官方文档也明确建议：除非你有明确的理由，否则优先用 List<T>。

八、练习

练习 4.1.1（算内存） 一个订单对象大约 100 字节（含各种字段）。 (a) 用 List<Order> 存 100 万条，大约占多少内存？ (b) 用 LinkedList<Order> 存，大约占多少？ (c) 这个差距会影响你的技术选型吗？什么情况下会？

练习 4.1.2（判断） 判断对错并说明理由： (a) 链表的插入删除都是 $O(1)$。 (b) 因为链表插入快，所以需要频繁增删的场景都应该用链表。 (c) 数组和链表遍历都是 $O(n)$，所以性能差不多。

练习 4.1.3（场景分析） 下面四个场景，你会选数组还是链表？说明理由。 (a) 一个待办事项列表，主要操作是"展示全部"和"标记完成" (b) 一个 LRU 缓存，需要频繁地把访问到的元素移到最前面 (c) 一个日志缓冲区，只往末尾追加，偶尔从头读取 (d) 一个浏览器的"后退"历史，需要支持任意位置的插入和删除

练习 4.1.4（代码阅读） 下面这段代码有什么问题？

Node a = new Node(1);
Node b = new Node(2);
a.Next = b;
b.Next = null;

// 想把 c 插到 a 和 b 之间
Node c = new Node(99);
a.Next = c;      // 这一行之后，b 还在链表里吗？

练习 4.1.5（挑战·设计） 有一种结构叫「块状链表」（Unrolled Linked List）：它把多个元素存在一个小数组里，然后把这些小数组用链表串起来。 (a) 它相比纯数组，改进了什么？ (b) 它相比纯链表，改进了什么？ (c) 举出一个你熟悉的、采用了这个思想的实际系统。

九、练习答案

4.1.1

  • (a) List<Order>：每个元素就是 Order 对象本身的大小。约 100 MB（100 万 × 100 字节）。 严格说，如果 Order 是引用类型（class），List<Order> 存的是一组引用（每个 8 字节），加上 100 万个 Order 对象本身。总占用约 $100 \text{ MB} + 8 \text{ MB}$。
  • (b) LinkedList<Order>：每个 Order 对象外面还要再包一层 LinkedListNode<Order>，节点里含 2 个引用（prev/next）加对象头，约 32 字节。总占用约 $100 \text{ MB} + 32 \text{ MB} = 132 \text{ MB}$。
  • (c) 32% 的差距，在 100 万条这个量级上是 32 MB。
    • 如果服务内存充裕（比如几 GB 的堆），32 MB 无所谓，选型应该看操作特征。
    • 如果内存紧张（容器内存受限、或数据量是 1000 万条），32 MB 变成 320 MB，这就可能成为决定性因素。
    • 另外要注意：对象数量也是成本。多 100 万个对象意味着 GC 要扫描更多对象，GC 停顿时间会变长。这在延迟敏感的服务里比内存本身更致命。

4.1.2

  • (a) 错（不完整）。 只在已知节点位置插入删除是 $O(1)$。如果只知道值、要先查找，那是 $O(n)$。

    准确说法：链表在给定前驱（或节点引用）时，插入删除是 $O(1)$。

  • (b) 错。 这正是本节想纠正的误解。频繁增删不代表链表更合适，因为：
    1. 你往往需要先找到那个位置 —— 这一步是 $O(n)$，把 $O(1)$ 的优势完全吃掉了。除非你在遍历过程中顺手记录节点引用。
    2. 链表遍历慢 3.8～7.4 倍，多占 8 倍内存。
    3. 实际情况是：大多数"频繁增删"的场景，数组依然更快（因为查找/遍历占了主导）。
  • (c) 错。 实测差了 3.8～7.4 倍。"都是 $O(n)$"只说对了增长趋势，没说常数。

4.1.3

  • (a) 数组。 主要操作是"展示全部"（遍历 + 下标访问），这正是数组最擅长的。
  • (b) 链表（或哈希表 + 双向链表）。 LRU 缓存需要"把某个已知节点移到头部"，这是典型的 $O(1)$ 操作。

    而且标准实现是哈希表 + 双向链表的组合：哈希表负责 $O(1)$ 找到节点，双向链表负责 $O(1)$ 移动节点。单靠链表做不到 $O(1)$ 查找。

  • (c) 数组（或环形缓冲区）。 只追加、从头读，是典型的 FIFO 模式。用一个环形缓冲区（5.2 节）可以做到 $O(1)$ 且零分配，比链表更快更省。
  • (d) 需要具体分析，但很可能用数组。
    • "后退历史"的主要操作是"后退"和"前进"，其实是一个栈式的操作 —— 数组/List<T> 就够了。
    • 如果真的要支持"在历史中间的任意位置插入删除"，那要看规模：几百条的话数组完全够用（$O(n)$ 的挪动是纳秒级）；几十万条才考虑别的结构。

4.1.4

b 会从链表里"掉出去"。

执行 a.Next = c 之前，链表是 a -> b。执行之后：

  • a.Next 变成了 c
  • 但 c.Next 还是 null（新节点默认值）
  • 于是从 a 出发只能走到 c 就停了 —— b 虽然还在内存里，但已经没有任何指针指向它了

正确写法：先接后面，再接前面。

Node c = new Node(99);
c.Next = a.Next;      // 先把 c 接到 b（也就是原来的 a.Next）上
a.Next = c;           // 再把 a 指向 c

这个顺序不能反，因为第一行会覆盖 a.Next。如果先写 a.Next = c，那"原来的下一个是谁"这个信息就丢了。

这是链表操作最经典的顺序陷阱，4.3 节会系统地讲这类边界问题。

另外：掉出去的 b 不会被内存泄漏（C# 有 GC，没有引用的对象会被回收），但数据丢了 —— 这在逻辑上就是 bug。

4.1.5

(a) 相比纯数组，改进了"中间插入/删除"。 纯数组在中间插入要挪动后面所有元素（$O(n)$）。块状链表只需要在一个小块内部挪动（块大小通常几十到几百），如果块满了就分裂成两块 —— 相当于把 $O(n)$ 降到了 $O(\sqrt{n})$ 或 $O(\text{块大小})$ 量级。

(b) 相比纯链表，改进了"缓存友好性"和"内存开销"。

  • 每个块内元素连续存储，遍历时缓存命中率高，不再是一个节点一次未命中。
  • 指针开销被摊薄了：一个块存 100 个元素，只多花 2 个指针，而不是每个元素多花 32 字节。

它同时拿到了两者的优点，代价是实现复杂度大幅上升。

(c) 实际系统：

  1. 数据库的 B 树 / B+ 树索引。 一个节点存几十到几百个键值（而不是 2 个），这正是块状链表思想在树上的体现。这是块状结构最重要的应用 —— 数据库能在磁盘上高效查找，靠的就是它。
  2. std::deque（C++ 标准库的双端队列）。 它用多个固定大小的数组块拼成一个逻辑上连续的序列。
  3. 文本编辑器的内部缓冲（如 piece table / gap buffer）。它们避免在编辑时搬动整个文档。
  4. Redis 的 quicklist / listpack。 Redis 的 List 类型就是这个结构 —— 既要有链表的快速增删，又要避免每个元素一个指针的开销。

这个练习想说明的是：数组和链表不是二选一的对立选项。"块状"这个折中思路在工程中到处都是 —— 把"粒度"从 1 个元素放大到一个块，就能同时缓解两者的缺点。

你在第 9 章会看到同样的思想：B 树之于二叉搜索树，就是"块状化"之于链表。

十、常见错误

误区 纠正
认为"链表插入删除都是 $O(1)$" 只在已知节点引用时成立。"按值删除"要先查找，整体是 $O(n)$。
认为链表一定比数组快 链表遍历慢 3.8～7.4 倍（实测），多占 8 倍内存。只有"在已知位置增删"这一个场景链表赢。
忽略链表的内存开销 每个节点约 32 字节，存一个 int 是 8 倍开销。大数量级下这会是决定性因素。
认为"都是 $O(n)$ 就性能差不多" 大 O 只说增长趋势。实测同样 $O(n)$ 的遍历差了 7.4 倍。
链表操作时先接前面 a.Next = c 会覆盖掉原来的后继指针。必须"先接后、再接前"。
默认选 LinkedList<T> 微软官方建议优先用 List<T>，除非有明确理由。LinkedList<T> 没有下标访问，遍历慢，内存开销大。

十一、本节总结

  1. 链表 = 节点 + 引用。节点里装"数据"和"下一个节点的地址"。头指针是进入整条链的唯一入口。
  2. a.Next = b 只复制一个地址，不搬运任何数据 —— 这就是链表增删是 $O(1)$ 的根本原因。
  3. 空间开销：链表每个节点约 32 字节（对象头 16 + 数据 + 引用 + 对齐），存 int 是数组的 8 倍。
  4. 遍历慢 3.8～7.4 倍：因为要额外读 Next、缓存不友好、无法预取。而且节点在内存中的分布会显著影响性能（挨着 vs 散着差近 1 倍）。
  5. 链表唯一的杀手锏是"已知位置增删 $O(1)$"：实测头插比 List.Insert(0) 快 843 倍。
  6. 优先级：默认用 List<T>；只有在"需要频繁在已知位置增删"时才考虑链表。

下一节衔接：本节一直说"已知位置插入是 $O(1)$"，但有个尴尬的问题 —— 单向链表里，就算你手里拿着某个节点，也没法 $O(1)$ 删掉它，因为你找不到它的前驱。下一节讲三种链表的形态差异，把这个坑填上。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "4.1",
  "title": "节点与引用：链表的本质",
  "covered": [
    "节点、引用、头指针、null 的定义与寻宝类比",
    "引用赋值的本质（只复制地址，不搬数据）",
    "内存开销实测：3.8 MB vs 30.5 MB（8 倍）与 32 字节/节点的构成",
    "遍历性能实测：数组 0.22ms / 紧凑链表 0.83ms / 分散链表 1.62ms",
    "头部插入实测：List.Insert(0) 200.30ms vs 链表 0.24ms（843 倍）",
    "链表 vs 数组完整取舍表",
    "链表操作的顺序陷阱（先接后、再接前）",
    "块状链表思想与 B 树/deque/Redis quicklist 的关联"
  ],
  "unresolved": [
    "双向链表解决「找不到前驱」的问题留到 4.2",
    "环形缓冲区留到 5.2",
    "LRU 缓存的完整实现（哈希表+双向链表）留到第 6 章之后",
    "B 树留到 10.4 的平衡树部分提及"
  ],
  "canonical_terms": {
    "链表": "由节点通过引用串联的数据结构",
    "节点": "存放数据与连接的基本单元",
    "引用": "指向堆上对象的地址，赋值时只复制地址",
    "头指针": "指向第一个节点的引用，是访问整条链的入口"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 3.1 的缓存行与 3.2 的动态数组",
    "读者理解 C# 中 class 是引用类型"
  ],
  "word_count_actual": 2280,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch04/Sec41/",
    "实测数据逐项核对：3.8/30.5 MB、0.22/0.83/1.62 ms、200.30/0.24 ms(843倍)",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版实验三只有「顺序分配」一种链表，实测仅慢 3.8 倍，因为刚分配的节点在堆上恰好连续；已补「分散分配」对照组，展示节点分布对性能的影响"
  ],
  "next": "4.2 单链表、双向链表与循环链表"
}

results matching ""

    No results matching ""