1. 什么情况下我才会认真考虑 LinkedList

1.1 先看 List 的删除到底做了什么

很多从 C++ 或者算法书转过来的开发者，一看到"C# 里的 LinkedList"，第一反应是"这不就是标准库里的链表吗，增删肯定比 List 快"。但实际上，我在真实项目里见过太多次 LinkedList 被误用，性能反而更差的情况。要弄清楚这个问题，先得知道 List 删除元素时到底做了什么。

List 底层是一个动态数组，连续内存。它的 Remove(T item) 方法做了两件事：先按值找到目标元素的位置（O(n) 的线性查找），然后把该位置之后的所有元素全部向前移动一格（又是一个 O(n) 的搬移操作）。也就是说，List 的按值删除本质上付了两次 O(n) 的代价。就算你手里已经握着元素下标，调用 RemoveAt(index)，照样要把后面的元素整体搬一次，这个"搬移"成本不可忽略。当集合长度达到十万、百万级别，每一次删除都会让 CLR 去做大量数组内存拷贝，CPU 缓存会被反复冲刷，耗时肉眼可见。

LinkedList 走的完全是另一条路线：它把"查找元素"和"删除元素"这两件事彻底拆开。删除动作本身，只要你手里拿的是一个 LinkedListNode 节点引用，理论上只要调整几个指针就可以了，跟集合里有多少个元素没有关系。这才是链表的核心价值——不是"增删快"，而是"在已知节点位置的前提下，增删只付出常数时间的指针调整代价"。

1.2 双向链表的底层结构：每个节点都是一条独立的小船

LinkedList 在 .NET 里实现的是双向链表。每个 LinkedListNode 都包含三个关键信息：一个 Value 存放实际数据，一个 Previous 指向前一个节点，一个 Next 指向后一个节点。多个节点通过 Prev/Next 指针首尾相连，像一串被线穿起来的小船。LinkedList 本身只维护两个指针——指向第一个节点的 First 和指向最后一个节点的 Last，同时记录 count（节点总数）和 version（版本号，用于防止迭代时修改集合）。

这里有个细节值得注意：.NET 的 LinkedList 并没有像某些教科书里那样使用"哨兵节点"（dummy head），它直接用真正的数据节点作为链表的头和尾。这意味着当你向链表头部插入节点时，必须额外处理"原来没有头节点"的边界情况；删除头节点时也要更新 First 指针。这个设计对使用者的直接影响是：不要试图在链表里"空转"一个假头部，所有节点都是真实数据。

每一个节点在内存里都是独立分配的，同一链表里的各个节点大概率分布在托管堆的各个角落，不连续。这跟 List 的"一整块连续内存"有本质区别。后面我要专门讲这个区别在实际性能上的巨大影响。

1.3 什么时候不该用 LinkedList（先排雷）

写代码之前，先排除掉那些"看似能用链表，实际用链表就是给自己挖坑"的场景：

• 需要频繁按下标随机访问：链表没有 C# 里的索引器，想拿第 500 个元素只能从头一个个走过去。这属于 O(n) 操作，而 List 是 O(1)。这种情况用 LinkedList，等于自废武功。
• 存储的是大量小型值类型：链表每个节点是独立对象，光是对象头、两个指针引用就要多占十几字节甚至更多。如果你存的是 int、bool 这类小数据，内存开销很容易翻好几倍，GC 压力也随之上升。
• 集合规模只有几十个元素：这种规模下，List 的搬移成本微乎其微，而 LinkedList 的节点分配、指针维护、引用追踪反而更慢。算法导论里的大 O 复杂度在数据量不够大的时候，常常干不过工程实现里的常数开销。

真正值得考虑 LinkedList 的场景，核心只有一条：你经常需要在一个已经确定的节点位置旁边插入或删除元素，并且你能高效拿到这个节点的引用。比如 LRU 缓存、导航历史记录、消息队列两侧的插入弹出等。先想清楚这一点，再看下面的 API 和踩坑记录，你会有完全不同的感受。

2. 操作链表的第一步是抓住 LinkedListNode，而不是链表本身

2.1 五个关键的 O(1) 节点操作

很多新手拿到 LinkedList ，第一反应是像用 List 那样 Add(item)、Remove(item)。这样用当然没错，但你把 LinkedList 最大的优势丢掉了。LinkedList 有一组专门针对"节点"的操作方法，全部是 O(1) 的时间复杂度：

• AddFirst(LinkedListNode ) / AddFirst(T)：把头节点换成指定节点，原头节点往后挪。O(1)
• AddLast(LinkedListNode ) / AddLast(T)：在尾节点后面追加。O(1)
• AddAfter(LinkedListNode , T)：在指定节点后面插入一个新节点。O(1)
• AddBefore(LinkedListNode , T)：在指定节点前面插入一个新节点。O(1)
• Remove(LinkedListNode )：从链表中摘除指定节点。O(1)

这套 API 的使用前提是：你已经拿到了目标位置的节点引用。怎么拿？最典型的是在遍历过程中用变量记录当前访问到的节点。比如你要写一个"历史访问记录"，用户浏览一个新页面时，你想把当前页面插到某个已有记录后面，手里握着那个页面对应的节点，AddAfter 一步搞定，速度快到基本测不出来。

一个小技巧是：当你要在链表头部反复插入、在尾部反复弹出时，直接使用 First 和 Last 这两个属性，不要在循环里一遍遍调用 Find 去找节点。Find 是 O(n) 的，一旦放进循环，整体复杂度立刻变成 O(n^2)，性能翻车是必然的。

2.2 复杂度对照表：哪些操作快，哪些操作一定慢

整理一份直接能抄的复杂度对照表，列清楚 LinkedList 和 List 在常见操作上的差异：

从表格里能清楚地看到：LinkedList 的"快"是有前提的。只有当你把查找和增删分离，提前握着节点引用，它才会真正展现出 O(1) 增删的威力。如果每一次操作都要先 Find 一遍，那你付出的代价仍然是 O(n)，跟 List 相比，除了省掉搬移那一下之外，没有本质优势。

2.3 为什么 AddBefore(First) 这种边界操作需要特殊处理

没有哨兵节点的另一个影响是边界操作。你可以在任意节点前调用 AddBefore，这在链表中间毫无问题；但如果目标节点正好是 First（链表头），AddBefore 实际上要把新节点变成新的 First。同理，在 Last 节点后 AddAfter，新节点直接变 Last。

实际项目中容易出问题的往往不是这些 API 本身，而是你对"节点属于哪个链表"的判断。.NET 的 LinkedListNode 有一个 List 属性，指向它所属的 LinkedList ；如果一个节点不在任何链表里，List 为 null。在跨链表移动节点时，你要么用 Remove 把原节点摘下来，要么用 AddLast(node) 把别的链表节点怼过来——但要知道：一个节点同一时刻只能属于一个链表，往第二个链表里 Add 一个已经在别的链表中的节点，会直接抛出 InvalidOperationException。

我见过一个真实的 bug 场景：某开发者想实现"缓存命中后，把命中节点挪到链表头部"，他直接用 AddFirst(node) 想把一个仍然挂在链表尾部的节点往头部挪。结果呢？异常直接抛出来，程序崩溃。正确姿势是先 Remove(node)，再 AddFirst(node)。这个"先摘下来再接上去"的操作在链表里太基础了，但没踩过坑的人是真的容易忽略。

3. 实战中容易踩的 LinkedList 的坑（附带排查思路）

3.1 坑一：foreach 里删除节点直接抛异常，正确解法是什么

我要讲的第一个坑，几乎每个用过 LinkedList 的人都踩过。场景是这样的：你在遍历一个 LinkedList ，想把所有满足条件的节点删掉，于是很自然地写出下面的代码：

var list = new LinkedList<int>(Enumerable.Range(1, 10)); foreach (var item in list) { if (item % 2 == 0) { list.Remove(item); // 这里会抛 InvalidOperationException } }

一股脑写到这儿，第一次运行直接炸了。原因是 LinkedList 内部维护了一个 version 字段，每次 Add/Remove 都会让 version 自增。foreach 的枚举器在 MoveNext 时检查当前 version 跟创建枚举器时的 version 是否一致，不一致立刻抛异常。这个机制是为了防止你在迭代过程中修改集合，导致枚举状态错乱。

正确做法有好几种。最朴素也最稳的方案：用一个 while 循环，自己维护节点游标：

var node = list.First; while (node != null) { var next = node.Next; // 先记录下一个节点，防止链表结构变化后丢失位置 if (node.Value % 2 == 0) { list.Remove(node); } node = next; }

这里有个关键细节：每次循环开始前，先把 next 记录下来。因为如果你先删除了当前节点，节点上的 Next 指针虽然还指向下一个节点，但当前节点已经跟链表断开了；如果再把 node 重新赋值为 next，逻辑上确实没问题，但新手很容易在"删除节点后继续用 node = node.Next"这条路上绕晕。提前记录 next，代码清晰且安全。

还有一个很多人不知道的用法：for 循环 + First/Next 手动递进。这跟 while 方案本质一样，只是写法上更紧凑。至于 foreach 里那种一行代码删光所有偶数的写法，抱歉，C# 不给你这个便利，老老实实用 while。

3.2 坑二：用 Contains / 按值删除构建 O(n^2) 陷阱

第二个坑比第一个隐蔽得多，因为它不报错，只是悄悄变慢。有些场景下，你反复判断"某个值是否在链表里"，或者在循环里通过 Remove(value) 删除元素。单看一次 Remove(value)，复杂度 O(n)，好像还能接受；但如果你在一个循环里做 n 次这种操作，整个程序的时间复杂度变成 O(n^2)，数据量一旦过万，程序卡到让你怀疑是不是死循环了。

我印象很深的一个线上问题：某模块维护了一套任务队列，任务完成时需要从队列中移除对应任务。开发者直接用了 LinkedList ，然后每次移除时调用 Remove(taskById)，也就是在长链表中按值查找并删除。队列一旦积累到几万条，每次删除都扫一遍链表，系统响应时间从毫秒级飙升到几秒。

排查的时候我先看 CPU 占用，看到单核满载；然后用 profiler 抓热点，发现 90% 的时间消耗在 LinkedList.Remove 内部的 Find 调用上。这种问题其实很好修复：要么在 Task 对象里直接保存对应的 LinkedListNode ，借助节点做 O(1) 删除；要么干脆换 Dictionary<int, Task> 用按 key 删除。记住一个原则：如果一个数据结构的使用方式往往需要"先查找、再改动"，那它很可能不该用链表实现。

3.3 坑三：把 LinkedList 当数组用，到处 ElementAt(n)

第三个坑偏向"惯性思维"。List 用久了的人，随时想按下标拿元素；换成 LinkedList 后，很自然就会写出类似 list.ElementAt(5) 的代码。Line 开头的注释可能还写着"拿第 6 个元素"，完全忘了 ElementAt 遍历了链表的前 5 个节点才能拿到目标。单次 ElementAt 的代价是 O(n)，但如果你在循环里反复调 ElementAt，整体性能会难看得很。

这个坑的处理方式取决于业务场景：如果你真的频繁需要按下标访问，请你换回 List，而不是逼自己用 LinkedList；如果你只是偶尔需要拿到链表的第 k 个节点，那可以先判断一下 k 靠近头部还是尾部，从近的那一端开始遍历。链表最忌讳的是一遍又一遍从头开始找。

3.4 避坑原则的总结

说到底，LinkedList 的踩坑不外乎三类：找得快但删得慢（把链表当数组用）、删得快但找得慢（每次删除前现找节点）、迭代中修改集合被 version 拦截（foreach 里直接 Remove）。这三类我在不同项目里全都碰到过。把它们想明白之后，你再回头看 LinkedList 的 API 设计，就会理解为什么 .NET 团队要刻意区分"按值删除"和"按节点删除"——前者是便捷 API，后者才是真正的性能入口。实际写代码时，用一个明显的命名习惯来提醒自己：变量名但凡跟"节点"相关，比如 node、current、entry，说明这里有机会做 O(1) 操作，值得好好利用。

4. 理论快不等于实际快：LinkedList 与 List 的实测对比

4.1 为什么"O(1) 删除"在真实机器上可能输给"O(n) 删除"

理论复杂度上说，LinkedList 在已知节点删除上是 O(1)，List 是 O(n)，链表应该完胜。但真实工程里有个被低估的因素：缓存局部性。List 的内存是连续分配的，CPU 从内存读取数据时会把相邻的一大块数据一起装进高速缓存；遍历 List 时，下一个元素大概率已经在缓存里，访问速度极快。而 LinkedList 的节点分散在堆内存的各处，CPU 每访问一个节点，大概率都要重新从主存加载，缓存命中率非常低。

所以你会看到一个反直觉的现象：在集合规模较小（比如几千个元素以内）或者操作不那么频繁时，List 的"O(n) 搬移"用十余年的缓存、预取和流水线优化，硬生生地赢过了 LinkedList 的"O(1) 指针调整"。不是说大 O 没用，而是 n 不够大时，常数和硬件特性主导了一切。这也是为什么我一直强调：加一个新数据结构之前，先问数据规模到底多大。

4.2 用一组模拟基准测试验证

为了让结论不那么空洞，我在自己的开发环境里跑了一组模拟基准测试。测试分三种典型场景：

第二列的实际含义是：LinkedList 只有在"头部/尾部插入"和"已知节点删除"上才真正有优势，而 List 强在随机访问和缓存友好性。第一列里 LinkedList 的插入优势只有在数据量很大、且操作集中在头尾时才明显；如果插入位置在中间，你得先找到那个位置的节点，那前面的优势又会被找节点的成本抵消。

我还额外测过混合操作：10 万次"尾部插入 + 头部移除"的队列操作。LinkedList 在这种典型 FIFO 场景下完胜 List，因为 List 每次从头部移除都要搬移所有剩余元素。这个模拟最能说明问题：LinkedList 不是垃圾，它只是一把专门对付"两端增删"场景的雕刻刀。拿它去做随机访问，就是拿雕刻刀切西瓜，费劲且不好使。

4.3 工业级用法：LinkedList + Dictionary 实现 LRU 缓存

把 LinkedList 用出真正的工业级价值，最经典的例子是 LRU 缓存（Least Recently Used，最近最少使用）。整体思路非常简单：

• 用一个 Dictionary<TKey, LinkedListNode > 负责 O(1) 查找；
• 用一个 LinkedList 维护访问顺序，链表头部是最新访问的，尾部是最久未访问的；
• 每次 Get 或 Set 命中时，如果节点不在头部，就先 Remove 再 AddFirst；
• 缓存满时，直接 RemoveLast 淘汰最久未使用的元素。

核心代码骨架长这样：

public sealed class LruCache<TKey, TValue> { private readonly Dictionary<TKey, LinkedListNode<TValue>> _map; private readonly LinkedList<TValue> _order; private readonly int _capacity; public bool TryGet(TKey key, out TValue value) { if (_map.TryGetValue(key, out var node)) { // 命中后把节点提到链表头部 _order.Remove(node); _order.AddFirst(node); value = node.Value; return true; } value = default!; return false; } public void Add(TKey key, TValue value) { if (_map.TryGetValue(key, out var existing)) { // 更新已有值并提为最新 existing.Value = value; _order.Remove(existing); _order.AddFirst(existing); } else { // 插入新值，淘汰最久未使用的 if (_map.Count >= _capacity) { var last = _order.Last!; _map.Remove(last.Value.Key); // 实际实现里节点内要存 key _order.RemoveLast(); } _order.AddFirst(value); _map[key] = _order.First!; } } }

这段代码的精髓在于：字典负责把"按 key 查找"从 O(n) 降成 O(1)，链表负责把"调整访问顺序"从 O(n) 降成 O(1)。两个数据结构一配合，整个 LRU 缓存的 Get 和 Add 都是 O(1)。这种"一个负责查、一个负责改"的分工模式，才是 LinkedList 在工程里最正确的存在方式。如果你之前只把 LinkedList 当 List 的替代品用，看完这个模式，应该会对它有全新的理解。

5. 动手实现一个简化版双向链表，彻底弄懂内部机制

5.1 从零实现 AddLast / AddFirst / Remove 的核心逻辑

为了把前面讲的东西落到实处，我自己动手写过一个小型双向链表，不追求 .NET 源码那样完备，只保留能说明原理的核心部分。你跟着写一遍，比看十遍文档都管用——尤其是当你在调试时遇到链表断裂、遍历跳空的问题，亲手实现过一次之后，定位起来会快得多。

核心代码骨架如下：

public class MiniLinkedList<T> { private int _count; private int _version; public LinkedListNode<T>? First { get; private set; } public LinkedListNode<T>? Last { get; private set; } public int Count => _count; public void AddFirst(LinkedListNode<T> node) { node.List = this; if (First is null) { First = node; Last = node; node.Previous = null; node.Next = null; } else { node.Previous = null; node.Next = First; First.Previous = node; First = node; } _count++; _version++; } public void AddLast(LinkedListNode<T> node) { node.List = this; if (Last is null) { First = node; Last = node; node.Previous = null; node.Next = null; } else { node.Previous = Last; node.Next = null; Last.Next = node; Last = node; } _count++; _version++; } public void Remove(LinkedListNode<T> node) { if (ReferenceEquals(node.List, this) == false) throw new InvalidOperationException("节点不属于当前链表"); var prev = node.Previous; var next = node.Next; if (prev is null) First = next; else prev.Next = next; if (next is null) Last = prev; else next.Previous = prev; node.List = null; node.Previous = null; node.Next = null; _count--; _version++; } }

注意几个关键细节。第一，插入空链表和插入非空链表的处理路径不同——空链表要同时更新 First 和 Last。第二，删除节点时，prev 和 next 都有可能是 null，对应的边界操作分别是"删的是头节点"和"删的是尾节点"。第三，删除完成后要把节点的 List、Previous、Next 全部置空，这是为了隔离引用，方便 GC 回收，也防止节点被误认为还挂在链表中。第四，_version 字段，每做一次结构性修改都自增，这就是 foreach 保护机制的基石。

5.2 从 version 字段理解 .NET 的集合修改保护机制

你可能会琢磨：为什么我实现一个小链表也要维护 _version？这其实是对 .NET 集合设计的一个致敬。.NET 的集合类型（List、Dictionary、LinkedList）内部几乎都维护了类似的 version 字段，专门用来检测"枚举过程中集合被修改"。

当你写foreach (var item in list)时，编译器会生成一个枚举器；枚举器在创建的那一刻记录下当时的 version。每次调用 MoveNext，它会检查当前列表的 version 是否仍然等于创建时的版本。一旦不等，立刻抛出InvalidOperationException: Collection was modified。这个设计让你在迭代过程中意外修改集合时，能快速暴露问题，而不是等到数据错乱之后才崩溃。

我自己实现时发现的另一个有趣现象是：并不是所有删除都触发版号变化。比如Clear()会重置链表结构，version 必须自增；但如果你只是修改某个节点的 Value 值，不改变链表结构，version 可以保持不变。这一点跟 .NET 官方实现完全一致——结构性修改才需要 bump version，赋值不需要。理解这一点后，你就能解释很多奇怪的运行时异常了。

5.3 写完迷你链表之后，我对 LinkedList 的认知变化

自己动手实现了这套东西之后，我最大的体会是：写代码之前，永远先问"这个操作是结构性修改还是值修改"、"我是否持有目标节点的引用"、"数据量级到底有多大"。LinkedList 不是万能的，但它也绝对没有某些性能党黑得那么不堪。它是一把好用的雕刻刀，只不过大多数人拿它的姿势错了。

如果你也想彻底掌握这个数据结构，我强烈建议你按我上面的骨架自己敲一遍完整实现，然后对照 .NET 源码（网上很多地方能看）看看团队是怎么处理各种边界条件的。看完源码再回到项目中，你会发现那些困扰你很久的问题，答案全都写在数据结构设计里。