链表优于数组的场景

在现代CPU架构下（拥有L1/L2/L3缓存、硬件预取器），数组（Array/Vector）在绝大多数通用场景下都优于链表。因为数组不仅具有空间局部性（Spatial Locality），还节省了指针的内存开销。

然而，“链表完全优于数组”的情况依然存在，主要集中在算法复杂度级差、内存布局约束、并发模型以及引用稳定性这几个领域。

以下是真实世界中链表优于数组的具体场景：

1. 侵入式链表（Intrusive Lists）与 O(1) 删除

这是游戏引擎和操作系统内核中最常见的场景，也是链表最不可替代的场景。

场景描述：你拥有一个对象的指针，想要将它从它所属的容器中移除。
数组的做法：即便你有对象的指针，要从数组中删除它，你必须先扫描数组找到它的索引（ $O(N)$ ），然后将后面的元素前移（ $O(N)$ ）。
非侵入式链表（如 std::list）的做法：你需要一个迭代器才能做到 $O(1)$ 删除，光有对象指针是不够的。
侵入式链表（Intrusive List）的做法：链表节点结构体（Prev/Next指针）直接嵌入在业务对象的数据结构中。
- 优势：只要拿到了这个对象的指针，就能通过偏移量直接访问前后指针，实现真正的 $O(1)$ 将自己从链表中摘除，无需任何查找。
真实案例：
- Linux 内核：struct list_head 被用在内核的几乎所有角落（进程调度队列、驱动设备列表）。内核代码经常需要在持有某个结构体指针时，迅速将其从调度队列中移除。
```
// /include/linux/types.h
struct list_head {
  struct list_head *next, *prev;
}
```
- 游戏引擎：例如渲染列表，物体对象本身包含节点信息。当物体销毁时，它可以直接把自己从渲染层级中移除，而不需要引擎去遍历成千上万个物体的数组。

当涉及将两个大数据集合并，或者将一个大集合拆分成两段时，链表的物理优势无法被缓存弥补。

场景描述：将列表 B 的所有元素移动到列表 A 的尾部。
数组的做法：需要重新分配 A 的内存（如果空间不足），然后将 B 的所有数据 memcpy 到 A 中。这是 $O(M)$ 的操作（M为B的大小）。
链表的做法：只需要修改 A 的尾指针指向 B 的头，B 的尾指针修正一下即可。这是严格的 $O(1)$ 。
真实案例：
- IO 缓冲区管理：网络协议栈中，数据包可能需要分片或重组。使用链表（如 Linux 的 sk_buff 在某些层面的组织，或 Nginx 的 ngx_chain_t）可以零拷贝地重新组织数据块的顺序。
- 斐波那契堆（Fibonacci Heap）：这种数据结构依赖于 $O(1)$ 的合并操作来实现高效的优先队列算法，底层必须基于链表。

这往往是业务逻辑层的强需求，而非单纯的性能需求。

场景描述：外部系统持有指向容器内部某个元素的指针或引用。
数组的做法：std::vector 的扩容（reallocate）或中间插入/删除，会导致内存地址变更，所有指向该容器内部元素的指针瞬间失效（Dangling Pointers）。为了解决这个问题，你必须使用索引（ID）代替指针，但这会增加一次查找开销。
链表的做法：链表节点的物理地址永远不会改变，除非该节点被显式删除。无论你在链表中其他位置插入或删除了多少数据，你持有的指向某个特定节点的指针永远有效。
真实案例：
- DOM 树结构：浏览器中的 DOM 节点。你依然持有一个 div 的引用，即便它的兄弟节点被删除了，或者父节点插入了新子节点，你的引用必须依然指向那个内存块。
- 观察者模式：很多 GUI 框架维护一个“监听者列表”。当一个监听者决定注销自己时，它不仅需要 $O(1)$ 删除，还要求其他监听者的回调指针不被移动。

在多线程高并发环境下，锁的开销远大于缓存未命中的开销。

场景描述：多线程同时向队列推入或弹出数据。
数组的做法：实现一个无锁的、动态扩容的环形数组队列（Unbounded Lock-free Queue）是非常极其困难的。因为扩容涉及到内存回收和指针切换，很难通过 CAS（Compare-And-Swap）原子操作安全完成。
链表的做法：Michael-Scott Queue 是经典的无锁队列实现，基于链表。因为链表只需通过 CAS 操作修改 Next 指针即可完成入队/出队，不需要处理整体数据的迁移。
真实案例：
- 高频交易系统的消息队列、Java 的 ConcurrentLinkedQueue。在这些场景下，避免线程阻塞（Lock-free）比单线程的缓存局部性更重要。

虽然现代分配器（如 jemalloc/tcmalloc）已经极大地优化了碎片问题，但在某些受限环境下依然是瓶颈。

场景描述：系统内存充足，但没有足够大的连续空间。
数组的做法：如果你需要分配一个巨大的数组（例如 1GB），即使物理内存剩余 2GB，但如果因碎片化导致最大连续块只有 500MB，数组分配就会失败（OOM）。
链表的做法：链表分散在内存的各个角落，只要总剩余空间足够，就能分配成功。
真实案例：
- 文件系统：FAT 文件系统本质上就是文件块的链表。文件不需要存储在磁盘的连续扇区，否则磁盘碎片整理将是一场噩梦。虽然这不是内存里的链表，但原理一致。

虽然稀疏矩阵通常用压缩数组（CSR）存储，但在动态构建阶段，链表更优。

在现代计算机上，如果你的操作主要是“遍历”和“随机访问”，请无脑用数组。

但在以下情况，链表（尤其是侵入式链表）完全优于数组：