链表 vs 数组：为什么 Redis、ZGC、操作系统都爱链表

每个学数据结构的人，第一关就是"数组和链表有什么区别"。如果只背结论——数组随机访问快、链表插入快——那就太浅了。真正的差别，藏在内存布局里。

数组：连续内存的"快"与"笨"。数组在内存里是一段连续的格子，给定下标 i，CPU 直接算出地址就取到，O(1) 随机访问。但这个"连续"是双刃剑：在中间插入要搬移后半段（O(n)）、容量固定、还可能在内存碎片化时分配失败。

链表：指针串起的"散"与"活"。链表节点散落在内存各处，靠 next 指针相连。它没有连续约束，插入删除只改几个指针（O(1)）、容量动态增长。代价是失去随机访问（找第 k 个要 O(n)），且缓存局部性差——这正是它"遍历慢"的根源。

为什么工业界离不开链表？因为真实系统里"频繁增删、不要求随机访问"的场景太多了：Redis 的列表 / 慢查询日志用链表组织；ZGC（Java 低延迟 GC）用链表串起待回收的堆区域；Linux 内核的进程调度、文件系统目录项大量使用双向链表（经典的 list_head 宏）。这些场景要的是"随时插入摘除"，而不是"按下标秒取"。

一句话：数组赢在"查"，链表赢在"改"。选谁，看你的瓶颈在随机访问还是频繁增删。今天我们从 C3 节点系统拆解链表，顺便把数组的老底也翻一遍。

图：连续 vs 离散——两种线性结构的存储本质

参考代码（Python）

数组中间插入需搬移 O(n)，链表已知前驱插入只需 O(1)。

import time
arr=list(range(10000))
t=time.perf_counter(); arr.insert(5000, -1); t=time.perf_counter()-t
print(f"数组中间插: {t:.6f}s  # 需搬移后续元素 O(n)")
# 链表在已知前驱处插入只需改指针 O(1)（见正文 insert_after）

关联推荐

• 算法与问题求解入门 — 先建立"为什么同样的任务不同结构快慢天差地别"的认知
• 插入、选择、冒泡排序 — 排序里的"近乎有序用插入排序"正是链表思想的近亲
• 哈希表：为什么 Redis、Python 字典都靠它"秒查" — 另一个"结构决定性能"的经典