4.2　单链表、双向链表与循环链表

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

• 说清三种链表形态的结构差异与各自的代价；
• 解释"双向链表多花一个引用"换来了什么；
• 避开循环链表最常见的遍历陷阱。

先修：4.1（节点与引用）。 固定术语：单链表、双向链表、循环链表、前驱。 环境与版本：.NET 8 / C# 12。 预计阅读：26 分钟。

一、直觉：三种路

上一节留了一个尴尬的问题：

单向链表里，就算你手里拿着某个节点的引用，也没法 $O(1)$ 删掉它 —— 因为你找不到它的前驱。

为什么删除需要前驱？因为删除 node 的本质是"让前一个节点跳过它"：

删除前:  A -> B -> C
删除后:  A --------> C     （B 被跳过了）

这需要修改 A.Next。而单链表里，你手上只有 B，没有任何办法从 B 走到 A。

双向链表就是来解决这个问题的。

二、形式化：三种节点定义

// 单链表节点：一个引用
public class Node
{
    public int Value;
    public Node? Next;
}

// 双向链表节点：两个引用
public class DNode
{
    public int Value;
    public DNode? Prev;      // 指向前驱
    public DNode? Next;      // 指向后继
}

// 循环链表：结构上和单链表一样，区别在「尾节点的 Next 指向哪」
// 普通单链表：尾节点 Next = null
// 循环链表：  尾节点 Next = 头节点

双向链表多花的那 8 字节（一个引用）买到了什么？

"删除已知节点"这一条，就是双向链表存在的全部理由。

三、实验一：删除「已知节点」的代价

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

using System.Diagnostics;

// ==================== 实验一：删除「已知节点」的代价 ====================
//
// 注意前提：你已经拿到了要删除的那个节点本身的引用，
// 不需要先查找它。这个区别很重要。

static void RemoveSingly(ref Node? head, Node target, ref long ops)
{
    if (head == target)
    {
        head = head!.Next;
        return;
    }

    Node? prev = head;
    while (prev != null && prev.Next != target)     // 必须从头找它的「前驱」
    {
        prev = prev.Next;
        ops++;
    }
    if (prev != null) prev.Next = target.Next;
}

static void RemoveDoubly(DNode node)
{
    // 因为节点自己记着前驱，两个引用赋值就完事了
    if (node.Prev != null) node.Prev.Next = node.Next;
    if (node.Next != null) node.Next.Prev = node.Prev;
}

const int N = 500_000;

Node? sHead = new Node(0);
Node sc = sHead;
for (int i = 1; i < N; i++)
{
    sc.Next = new Node(i);
    sc = sc.Next;
}
Node lastSingly = sc;                       // 最后一个节点

DNode dHead = new DNode(0);
DNode dc = dHead;
for (int i = 1; i < N; i++)
{
    dc.Next = new DNode(i);
    dc.Next.Prev = dc;
    dc = dc.Next;
}
DNode lastDoubly = dc;

var sw = Stopwatch.StartNew();

long ops = 0;
RemoveSingly(ref sHead, lastSingly, ref ops);
sw.Stop();
double singlyMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
RemoveDoubly(lastDoubly);
sw.Stop();
double doublyMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine("=== 实验一：删除「已知节点」（不用先查找）===");
Console.WriteLine($"链表中一共 {N:N0} 个节点，删除最后一个：");
Console.WriteLine();
Console.WriteLine($"  单向链表: 走了 {ops,10:N0} 步 | {singlyMs,8:F3} ms | 因为必须从头找它的前驱");
Console.WriteLine($"  双向链表: 走了 {0,10} 步 | {doublyMs,8:F3} ms | 节点自己记着前驱，O(1)");
Console.WriteLine($"  双向快 {singlyMs / doublyMs:F0} 倍");
Console.WriteLine();

// ==================== 实验二：循环链表 ====================

Console.WriteLine("=== 实验二：循环链表 ====================");
Console.WriteLine();

Node c1 = new(1), c2 = new(2), c3 = new(3);
c1.Next = c2;
c2.Next = c3;
c3.Next = c1;                               // 尾节点指回开头 —— 这就是「循环」

Console.Write("  正确遍历（do-while，判断条件是「回到起点」）: ");
Node p = c1;
do
{
    Console.Write($"{p.Value} -> ");
    p = p.Next!;
} while (p != c1);
Console.WriteLine("(回到起点，结束)");
Console.WriteLine();

Console.WriteLine("  常见错误：套用普通链表的写法 `for (p = c1; p != null; p = p.Next)`");
Console.WriteLine("    因为 c3.Next 是 c1 而不是 null，p 永远不会变成 null；");
Console.WriteLine("    结果就是无限循环，一直打印 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> ...");
Console.WriteLine();
Console.WriteLine("  记忆点：判断循环链表结束的依据是「回到起点」，不是「变成 null」。");
Console.WriteLine();

// ==================== 实验三：C# 的 LinkedList<T> ====================

Console.WriteLine("=== 实验三：C# 内置的 LinkedList<T> ===");
Console.WriteLine();

var ll = new LinkedList<int>();
ll.AddLast(1);
ll.AddLast(2);
ll.AddLast(3);
Console.WriteLine($"  初始: {string.Join(" -> ", ll)}");

LinkedListNode<int>? found = ll.Find(2);     // Find 返回的是「节点」，不是下标
if (found != null)
{
    ll.AddBefore(found, 99);                 // 拿着节点引用，插入是 O(1)
    Console.WriteLine($"  在 2 前面插入 99: {string.Join(" -> ", ll)}");

    ll.Remove(found);                        // 同样是 O(1)
    Console.WriteLine($"  再删掉 2:        {string.Join(" -> ", ll)}");
}
Console.WriteLine();

Console.WriteLine("  LinkedList<T> 是【双向】链表，所以：");
Console.WriteLine("    优点：拿到节点引用后，插入/删除都是 O(1)；能在两端 O(1) 增删");
Console.WriteLine("    缺点：没有下标访问 —— 没有 ll[2] 这种写法，想找第 3 个必须走 3 步");
Console.WriteLine("          每个节点额外多存一个 Prev 引用，内存开销更大");
Console.WriteLine();

// 大规模实测「按下标访问」的代价
const int M = 500_000;
var arrRef = new List<int>(M);
var linked = new LinkedList<int>();
for (int i = 0; i < M; i++)
{
    arrRef.Add(i);
    linked.AddLast(i);
}

sw.Restart();
int v1 = arrRef[M - 1];                       // O(1)：直接算地址
sw.Stop();
double arrAccessMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
int v2 = linked.ElementAt(M - 1);             // O(n)：必须一步一步走过去
sw.Stop();
double linkedAccessMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  访问第 {M:N0} 个元素（下标 {M - 1:N0}）：");
Console.WriteLine($"    List<int>       : {arrAccessMs,8:F4} ms   O(1)，一次乘加算出地址");
Console.WriteLine($"    LinkedList<int> : {linkedAccessMs,8:F4} ms   O(n)，必须从头一步步走");
Console.WriteLine($"    链表慢 {linkedAccessMs / arrAccessMs:F0} 倍");
Console.WriteLine($"    （两者取到的值相同: {v1 == v2}）");
Console.WriteLine();

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

public class Node
{
    public int Value;
    public Node? Next;
    public Node(int value) => Value = value;
}

public class DNode
{
    public int Value;
    public DNode? Prev;
    public DNode? Next;
    public DNode(int value) => Value = value;
}

实测输出（.NET 8 Release）：

=== 实验一：删除「已知节点」（不用先查找）===
链表中一共 500,000 个节点，删除最后一个：

  单向链表: 走了    499,998 步 |    0.880 ms | 因为必须从头找它的前驱
  双向链表: 走了          0 步 |    0.031 ms | 节点自己记着前驱，O(1)
  双向快 28 倍

=== 实验二：循环链表 ====================

  正确遍历（do-while，判断条件是「回到起点」）: 1 -> 2 -> 3 -> (回到起点，结束)

  常见错误：套用普通链表的写法 `for (p = c1; p != null; p = p.Next)`
    因为 c3.Next 是 c1 而不是 null，p 永远不会变成 null；
    结果就是无限循环，一直打印 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> ...

  记忆点：判断循环链表结束的依据是「回到起点」，不是「变成 null」。

=== 实验三：C# 内置的 LinkedList<T> ===

  初始: 1 -> 2 -> 3
  在 2 前面插入 99: 1 -> 99 -> 2 -> 3
  再删掉 2:        1 -> 99 -> 3

  访问第 500,000 个元素（下标 499,999）：
    List<int>       :   0.0091 ms   O(1)，一次乘加算出地址
    LinkedList<int> :   2.2183 ms   O(n)，必须从头一步步走
    链表慢 244 倍
    （两者取到的值相同: True）

三个数字值得记住：

1. 单向 499,998 步 vs 双向 0 步 —— 这就是双向链表那个额外的 Prev 引用买来的东西。
2. 0.031 ms 是计时器的下限，不是双向链表的真实耗时。真实操作就是两次引用赋值，在纳秒级。这里只该看"步数"的对比，不该看"倍数" —— 因为双向那边已经快到测不准了。
3. LinkedList<T> 的 ElementAt 慢了 244 倍 —— 这就是"没有下标访问"的代价。

四、循环链表的遍历陷阱

循环链表在结构上和单链表完全一样，唯一的区别是尾节点的 Next 指向头节点而不是 null。

这个小小的区别带来一个经典的坑：

// 错误：会无限循环
for (Node? p = c1; p != null; p = p.Next)
    Console.Write(p.Value + " ");

因为 c3.Next 是 c1 而不是 null，p 永远不会变成 null。程序会一直跑下去。

正确写法是 do-while：

// 正确：判断"回到起点"
Node p = c1;
do
{
    Console.Write(p.Value + " ");
    p = p.Next!;
} while (p != c1);

注意这里必须用 do-while 而不是 while：因为一开始 p == c1 就成立，用 while (p != c1) 的话循环体一次都不会执行。

循环链表的两个使用要点：

1. 判断结束看"回到起点"，不是看 null。
2. 用一个 do-while，而不是 while，否则第一次就退出了。

循环链表有什么用？

• 约瑟夫环问题（一群人围成圈报数，报到某个数的人出列）—— 天然的循环结构。
• 轮询调度：操作系统的时间片轮转、负载均衡的 round-robin，都是在"一圈一圈地转"。
• 实时系统中的循环缓冲区：不过实际工程中更常用环形数组（5.2 节），因为缓存更友好。

五、三种形态的完整对比

C# 里没有内置的循环链表，需要自己写。这从侧面说明：它在实际业务中的使用频率远低于双向链表。

但这不代表它不重要 —— 约瑟夫环、轮询调度这类问题的模型就是循环的，面试和算法题里经常出现。理解它，是为了在需要时能立刻识别出该用它。

六、练习

练习 4.2.1（选择形态） 下面四个场景该用哪种链表？说明理由。 (a) 实现一个浏览器的"后退/前进"功能 (b) 一个播放器的"循环播放列表" (c) 一个只需要从前往后处理的日志队列 (d) 一个需要频繁在任何位置插入删除的文本编辑器缓冲区

练习 4.2.2（写代码） 用循环链表实现约瑟夫环：$n$ 个人围成一圈，从第 1 个人开始报数，每次数到 $m$ 的人出列，然后从下一个人继续。求最后剩下的人的编号。

练习 4.2.3（判断） 判断对错并说明理由： (a) 双向链表比单链表慢，因为它要多维护一个 Prev 指针。 (b) 循环链表不能用 foreach 遍历。 (c) 在双向链表中删除一个已知节点是 $O(1)$，所以"删除值为 X 的节点"也是 $O(1)$。

练习 4.2.4（代码阅读） 下面这段"双向链表插入"的代码有 bug，请指出：

// 在 node 后面插入 newNode
static void InsertAfter(DNode node, DNode newNode)
{
    node.Next = newNode;
    newNode.Prev = node;
    if (newNode.Next != null)
        newNode.Next.Prev = newNode;
}

练习 4.2.5（挑战·改造） 把一个单向链表改造成"能在 $O(1)$ 时间内删除已知节点"的结构，但不允许增加 Prev 指针。 （提示：想一想，如果允许"偷梁换柱"呢 —— 你并不一定非要真的删掉那个节点本身。）

七、练习答案

4.2.1

• (a) 双向链表（或一个 List<T> + 一个下标）。因为需要在历史记录中前后移动，双向遍历是核心需求。

  不过要说实话：如果历史记录只保留几百条，用一个 List<string> 加一个下标指针就够了，而且更快、更简单。只有记录量极大（几十万条）时才值得上双向链表。

• (b) 循环链表（或双向循环链表）。播放到最后一首之后回到第一首 —— 这正是循环结构。

  用双向循环链表更好，因为播放器通常需要"上一首"。

• (c) 单链表（或队列）。 只需要单向处理，Next 就够。实际上，这种场景应该直接用 Queue<T>（5.2 节），它比链表更快也更省内存。
• (d) 双向链表。 编辑器的光标需要在任意位置前后移动和增删，双向是最自然的选择。

  补充：真实的文本编辑器（如 VS Code）用的往往是 piece table 或 rope 这类更复杂的数据结构，因为纯链表在超大文档上性能不够。

4.2.2

static int Josephus(int n, int m)
{
    if (n <= 0 || m <= 0) return -1;

    // 构造 1..n 的循环链表
    Node head = new(1);
    Node cur = head;
    for (int i = 2; i <= n; i++)
    {
        cur.Next = new Node(i);
        cur = cur.Next;
    }
    cur.Next = head;                    // 尾指回头，形成环

    // prev 用来在删除时跳过被淘汰的节点
    //（单链表必须靠 prev 才能删除，见 4.1 的结论）
    Node prev = cur;
    Node p = head;

    while (p.Next != p)                 // 只剩一个人时，p.Next 会指向自己
    {
        for (int i = 1; i < m; i++)     // 报数 m-1 次，停在第 m 个人身上
        {
            prev = p;
            p = p.Next!;
        }
        prev.Next = p.Next;             // 把第 m 个人移出圈子
        p = prev.Next!;                 // 从下一个人继续
    }
    return p.Value;
}

验证（$n = 5, m = 3$）：

初始：1 2 3 4 5（环形）

结果是 4 ✓（这是约瑟夫环的经典测试用例）

注意代码里的一个细节：用了 prev 指针来辅助删除。因为单链表删除节点必须拿到前驱 —— 这正是 4.1 节和 4.2 节反复强调的那个限制。

用双向循环链表的话，prev 就不需要了，可以直接 p.Prev.Next = p.Next。

4.2.3

• (a) 错（方向反了）。 双向链表不会更慢，反而在某些操作上更快（删除已知节点 $O(1)$）。 多维护一个 Prev 的代价是：每个节点多 8 字节内存、每次插入删除多写一次赋值。这些是空间和常数上的成本，不改变任何操作的复杂度量级。

  只有在极大规模（几千万节点）或内存极度受限时，这 8 字节才会成为决定因素。

• (b) 对，但要说清楚。 foreach 依赖集合的 GetEnumerator，而 Enumerator.MoveNext() 的终止条件是"当前节点为 null"。循环链表永远不会到 null，所以直接对循环链表用 foreach 会死循环。

  但这不是循环链表本身的限制，而是"没有为它写一个正确的迭代器"。你完全可以自己实现一个 IEnumerable，在 MoveNext 里判断"是否回到起点"。.NET 内置的 LinkedList<T> 其实也是循环结构（内部首尾相连），但它通过显式的 head 成员正确地实现了迭代器。

• (c) 错。 "删除已知节点"和"删除值为 X 的节点"是两件不同的事：
  • 删除已知节点：你已经拿着那个节点的引用了 → $O(1)$
  • 删除值为 X 的节点：你得先找到 X 在哪 → $O(n)$，找到之后删除才是 $O(1)$

    LinkedList<T>.Remove(T value) 的复杂度是 $O(n)$，不是 $O(1)$。而 LinkedList<T>.Remove(LinkedListNode<T> node) 才是 $O(1)$。API 的名字一样，复杂度差一个量级 —— 这是很容易踩的坑。

4.2.4

漏掉了"把原后继接到新节点上"这一步。

执行过程分析（假设原链是 A -> B -> C，node = A，要插入 X）：

node.Next = newNode;      // A.Next = X  ← 此时 B 已经和链表脱钩了！
newNode.Prev = node;      // X.Prev = A
if (newNode.Next != null) // 但 X.Next 还是 null（新节点没设过）
    newNode.Next.Prev = newNode;   // 永远不执行

结果：A -> X -> null，B 和 C 全丢了。

正确写法（仍然是"先接后、再接前"）：

static void InsertAfter(DNode node, DNode newNode)
{
    newNode.Next = node.Next;              // ① X 先接管 A 原来的后继（B）
    if (newNode.Next != null)
        newNode.Next.Prev = newNode;       // ② B 的 Prev 改指向 X
    node.Next = newNode;                   // ③ A.Next 才改成 X
    newNode.Prev = node;                   // ④ X.Prev = A
}

核心原则还是 4.1 节那条：先接后面，再接前面。 因为"前面的指针"一旦被覆盖，你就找不到原来的后继了。

双向链表比单链表更容易出这类错，因为有两条链（Next 链和 Prev 链）都要维护，任何一条没接好都会出现"从前往后能走通、从后往前走不通"这种隐蔽的不一致。

写双向链表时，画图比在脑子里推演可靠得多。

4.2.5

方案：把"删除这个节点"变成"删除它的下一个节点"。

思路是这样的：既然拿不到前驱，那就不要把当前节点摘掉，而是把后继节点的内容复制过来，然后摘掉后继。

static bool DeleteNode(Node node)
{
    if (node.Next == null)
        return false;              // 是尾节点，这招用不了

    Node next = node.Next;
    node.Value = next.Value;       // 把后继的数据「偷」过来
    node.Next = next.Next;         // 再把后继摘掉
    return true;
}

效果：

原链表:  A -> B -> C -> D
调用 DeleteNode(B):

第 1 步（复制值）:  A -> C -> C -> D     （B 的值变成了 C 的值）
第 2 步（摘掉后继）: A -> C -> D          （原来的 C 节点被摘掉）

从外部看，链表变成了 A -> C -> D —— 和"真的删掉 B"结果一模一样。 ✓

代价与限制：

1. 不能删尾节点。 尾节点没有后继，没得偷。这时只能老老实实从头遍历找前驱。
2. 被删节点的引用会"变成"另一个节点。 如果外部还持有 B 的引用，它现在指向的值是原来 C 的值 —— 语义上变得很微妙。
3. 并发场景不安全。 复制值的那一瞬间，其他线程可能读到"两个节点值相同"的中间状态。

这个技巧在面试里很常见（题目通常叫「删除单向链表中的某个节点」）。它考察的不是你会不会写链表，而是你愿不愿意跳出"删除 = 摘掉自己"这个思维定式。

但它的工程价值有限 —— 副作用太多（不能删尾、引用语义混乱）。真正的工程做法是：在需要频繁删除时，一开始就选双向链表。

八、常见错误

九、本节总结

1. 单链表只有一个 Next，所以无法 $O(1)$ 删除已知节点 —— 找不到前驱。
2. 双向链表多一个 Prev（约 8 字节/节点），换来"删除已知节点 $O(1)$"。实测单向走 499,998 步，双向走 0 步。
3. 循环链表的尾部指回头部。遍历必须用 do-while + "回到起点"判断，用 != null 会死循环。
4. LinkedList<T> 是双向链表：带着节点引用增删是 $O(1)$，但没有下标访问（实测访问第 50 万个元素慢 244 倍）。
5. 删除已知节点 ≠ 删除值为 X 的节点。后者要先查找，是 $O(n)$。这个区别在 C# 的 API 名字上看不出来，必须看文档或自己清楚。
6. C# 没有内置循环链表 —— 说明它在业务中少见，但约瑟夫环、轮询调度这类问题的模型就是循环的。

下一节衔接：到这里链表的"结构"讲完了，但你如果真去写一个链表，会发现真正的难点根本不是指针怎么改，而是"空表怎么办""删的是头怎么办""只有一个元素怎么办"。下一节我们用哨兵节点把这些特判一次消灭掉，并写一个能通过 25 项边界测试的完整实现。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "4.2",
  "title": "单链表、双向链表与循环链表",
  "covered": [
    "三种链表形态的节点定义与类比",
    "「找不到前驱」问题与双向链表的解法",
    "删除已知节点实测：单向 499998 步 vs 双向 0 步",
    "循环链表的 do-while 遍历与死循环陷阱",
    "三种形态的完整对比表",
    "LinkedList<T>.ElementAt 的 O(n) 实测（慢 244 倍）",
    "删除已知节点 vs 删除值为 X 的节点（O(1) vs O(n)）",
    "约瑟夫环的实现与「偷梁换柱」删除法"
  ],
  "unresolved": [
    "哨兵节点与边界处理留到 4.3",
    "环形缓冲区留到 5.2",
    "LRU 缓存（哈希表+双向链表）留到第 6 章后"
  ],
  "canonical_terms": {
    "单链表": "每个节点只有一个指向后继的引用",
    "双向链表": "每个节点同时记录前驱与后继，删除已知节点为 O(1)",
    "循环链表": "尾节点的引用指回头节点，遍历需判断是否回到起点",
    "前驱": "某个节点的前一个节点"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 4.1 的节点与引用概念",
    "读者会使用 C# 的 LinkedList<T> 基本 API"
  ],
  "word_count_actual": 2340,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch04/Sec42/",
    "实测数据逐项核对：499998步/0步、ElementAt 2.2183ms vs 0.0091ms(244倍)",
    "约瑟夫环 n=5,m=3 结果 4 已手工验算",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "实验一中双向链表的 0.031ms 已接近计时器精度极限，正文明确说明「只该看步数对比，不该看倍数」"
  ],
  "next": "4.3 插入与删除：边界处理是全部难点"
}