从跳表到内存池：链表思想的现代延展

课本讲完单/双/循环链表，很多人以为"链表就这些了"。其实链表的灵魂——用指针把离散节点组织成结构——在现代系统里无处不在，只是穿了不同的外衣。

跳表（Skip List）。单链表查找是 O(n)，跳表在节点上"加多层前进指针"，像高速公路一样跳过一半节点，把查找压到平均 O(log n)，且实现比红黑树简单得多。Redis 的有序集合（ZSET）底层正是跳表 + 哈希表的组合——这就是链表思想的直接工业产物。

内存池与空闲链表。操作系统、游戏引擎管理小块内存时，常把空闲块用链表串起来（空闲链表），分配时摘一个、释放时挂回去，O(1) 完成，避免反复向系统申请。

图的邻接表。图（G1）最自然的存储方式就是"每个顶点挂一条链表，串起它的所有边"。可以说，没有链表，就没有高效的图算法。今天我们把 C3 学扎实，后面 C5 二叉搜索树、G1 图都会回头感谢这份功底。

链表思想的上限，远不止一道面试题——它是把"离散"组织成"有序"的通用范式，从缓存到数据库到操作系统，处处是它的回声。

图：跳表用多层"快进指针"把链表查找压到对数级

参考代码（Python）

链表的"节点+指针"思想延伸到图：邻接表就是每个顶点挂一条链表。

# 图的邻接表：每个顶点挂一条链表，串起它的边
graph = {
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': [],
}
for neighbor in graph['A']:   # 遍历 A 出发的所有边
    print(neighbor)

关联推荐

• 算法与问题求解入门 — 理解"基础思想如何长成工业系统"
• 哈希表 — 与跳表一样是 Redis 的核心结构
• 算法通关训练营·排序篇 — 顺着结构主线一路进阶