应用实例：真实系统中的链表

链表常被当作指针操作的练习题，但它在真实系统里应用广泛——凡是频繁在中间插入 / 删除、又不需要随机下标访问的场景，链表（或它的变体）几乎都是默认数据结构。下面六个例子，每个都标出「用了哪种链表、为什么不用数组」。

1 · LRU 缓存：哈希表 + 双向链表

最经典的链表应用之一。要求 get / put 都 $O(1)$，且容量满时淘汰最久未用的项。单靠哈希表能 $O(1)$ 查值，但「谁最久没用」需要顺序；单靠链表能维护顺序，但定位某 key 是 $O(n)$。把两者组合起来：哈希表 $key \to 节点$ 负责 $O(1)$ 定位，双向链表按访问新鲜度排序——每次访问把节点移到头部（双向才能 $O(1)$ 摘除任意节点），淘汰时移除尾部节点。

2 · 跳表 (Skip List)：多层链表当「索引」

有序链表查找是 $O(n)$（不能二分，没法随机跳）。跳表在底层有序链表之上叠几层稀疏的「快车道」：上层每隔几个节点放一个索引，查找时从顶层大步跨、够不着了再下沉一层，期望 $O(\log n)$——用多层链表换来近似二分的效果，而且实现比平衡树简单、并发友好。Redis 的有序集合 ZSet、LevelDB / RocksDB 的 MemTable 都用它。

3 · 邻接表：图的稀疏存储

存一张图，用 $V\times V$ 邻接矩阵在稀疏图上极浪费（大片是 0）。邻接表给每个顶点挂一条链表，串起它的所有邻居，空间降到 $O(V+E)$。遍历某点的边就是走它那条链。BFS / DFS、Dijkstra 默认都跑在邻接表上。

4 · 内存分配的 free list

分配器（malloc / 对象池 / GC）要管理「哪些内存块空闲」。把空闲块自身串成一条链表——每个空闲块的头几字节就存 next，不需要额外数组。分配 = 从表头摘一块 $O(1)$，释放 = 插回表头 $O(1)$。这是「侵入式链表」(intrusive list)的典型：链表指针嵌在数据自己内部，零额外分配。

5 · Redis quicklist & Linux 内核 list_head

Redis quicklist（list 类型的底层）是「双向链表 + 每个节点是一段压缩数组 ziplist」的混合体——用链表保证两端 $O(1)$ 推入弹出，用块内数组改善缓存局部性，平衡了纯链表的指针开销。Linux 内核的 struct list_head 是侵入式双向循环链表的教科书实现，内核里几乎所有「一串对象」都用它穿起来。

6 · 其他随处可见的链表

哈希表的拉链法（同桶冲突的键串成链表）、浏览器 / 编辑器的撤销重做历史、音乐播放器的循环播放列表（循环链表）、区块链的「区块 → 前一区块 hash」本质也是一条单向链……一旦你认出「next 指针 + 就地增删」这个模式，会发现它无处不在。