关键事实：链表只有在“已经拿到节点”时插入和删除才是 O(1)。如果先要按值查找节点，完整操作仍然是 O(n)。
链表是什么
链表由多个节点组成，每个节点保存数据和下一个节点的引用。双向链表还保存上一个节点。
与数组不同，节点不要求连续存储，因此：
- 不能 O(1) 按索引跳到任意位置
- 已知节点时能 O(1) 改变连接
- 每个节点有额外引用与对象分配
- 顺序遍历的缓存局部性通常弱于 List
单向链表实现
下面实现维护
head 和 tail，因此头尾追加都是 O(1)：RemoveFirstMatch 需要先搜索，整体 O(n)。若 API 对外暴露安全的节点句柄，则已知节点删除可以做到 O(1)，但节点所有权和失效规则会更复杂。C# LinkedList
标准库的
LinkedList<T> 是双向链表：这里
AddBefore 和 Remove(node) 是 O(1)，因为已经持有 LinkedListNode<T>。如果先调用 Find("Attack")，查找仍是 O(n)。复杂度
操作 | LinkedList | List |
按索引读取 | O(n) | O(1) |
头部插入 | O(1) | O(n) |
尾部追加 | O(1) | 均摊 O(1) |
已知节点处插删 | O(1) | O(n) |
顺序遍历 | O(n)，缓存较弱 | O(n)，缓存友好 |
Unity 中什么时候值得用
- LRU 缓存：Dictionary 找节点，双向链表维护新旧顺序。
- 需要稳定节点句柄的调度链。
- 节点池已经存在、插删频繁且顺序必须保留。
- 算法本身要求链式结构。
聊天列表、敌人列表和动态 UI 通常仍优先 List + 对象池。List 虽然中间删除要搬移引用，但连续遍历更快、分配更少、Inspector 和调试更友好。
LRU 为什么需要两种结构
单独链表能 O(1) 移动已知节点，却不能快速按 key 找节点；单独 Dictionary 能快速查找，却不知道谁最旧。
组合方式：
- Dictionary：key → LinkedListNode
- LinkedList：头部最新，尾部最旧
这样查询、更新和淘汰平均都可接近 O(1)。
节点分配与对象池
每个普通链表节点通常是一个托管对象，会增加 GC 压力。热路径可考虑：
- 预分配节点池
- 使用索引代替对象引用
- 用数组保存
NextIndex
- 使用 Native 容器实现空闲列表
数组式链表牺牲部分易读性，换取连续内存和更可控的生命周期。
遍历时删除
使用标准双向链表遍历删除时，先保存下一个节点：
直接删除当前节点后再读取
node.Next，可能丢失遍历位置。常见误区
- “链表删除永远比 List 快”：前提是已经拿到节点。
- “链表不移动元素所以一定更快”：CPU 缓存和分配成本可能更重要。
- “AddLast 天然 O(1)”：单向链表必须维护 tail，否则要 O(n) 找末尾。
- “LinkedList 可以按下标访问”：标准
LinkedList<T>不提供索引器。
- 在 Inspector 需要编辑的普通数据上强行使用链表。
系列导航
小结
链表是一种针对节点级插删优化的结构，不是通用动态数组替代品。Unity 日常代码优先 List；只有节点句柄、插删模式和性能测量都支持时，再选择 LinkedList。