展开链表：一个节点装一小段数组
普通链表一个节点只装一个值，每个值都要搭一根 next 指针——指针开销和数据量一样大，而且节点散落在堆上，遍历时缓存命中率很差。展开链表 (unrolled linked list) 把节点改造成一小段连续数组（容量 cap），是数组与链表的折中：每
cap 个元素才用一根指针，一个节点内是连续内存、对 CPU cache 友好。代价是增删更复杂——插入时目标节点装满要分裂 (split)，删除时节点过空要和邻居借调 / 合并 (borrow / merge)。下面用插入 / 删除 / 查找三种操作单步演示：插入走「定位 → 判满 → 落位或
split」，删除走「定位 → 移除 → 判过空 → 借 / 并」，查找走「逐节点比值域 → 命中则段内定位」。
**指针开销摊薄的算账。**普通链表存 n 个元素就要 n 个节点、n 根 next 指针；64 位机上一根指针 8 字节，光指针就和一个 int 数据本身一样重（甚至更重）。展开链表每 cap 个元素才用一根指针，指针数约 n / cap 根——cap = 4
时指针开销直接降到四分之一。元素越小、cap 越大，这笔账越划算。
**真正的收益是缓存局部性。**普通链表的节点由 malloc 分散在堆上，遍历时每跳一个节点几乎都是一次 cache miss,CPU 要停下来等内存。展开链表一个节点内是连续数组，一次 cache line 能拉进好几个元素，顺序遍历几乎全是 cache hit。这正是
unrolled linked list 在「需要链表的增删、又想要数组的扫描速度」时被选中的原因。
split 与 borrow / merge 是一对对称的「维持半满」操作。插入时若目标节点已满，就 split：新建一个节点、把后半元素搬过去，两个半满节点各自还能再装。删除时若某节点跌破下限（约 cap 的一半）就反过来：先尝试从元素较多的邻居借调 (borrow)
一个元素补进来；邻居也不富裕时，就把两个过空节点合并 (merge) 成一个、回收掉多出来的那根指针。一升一降都把每个节点钉在「至少半满」上，节点才不会退化成「每个只装一个值」的普通链表，指针开销与缓存的收益才守得住。
查找虽仍是 O(n)，但常数更小、缓存更友好。展开链表没有随机访问，按值查找要逐个节点走，总比较次数仍是
量级。但收益在常数：其一，遍历的节点数只有约 n / cap 个（每个节点一次性带来一批元素），指针跳转（cache miss 高发处）大幅减少；其二，节点内是连续数组，一个 cache line 能拉进多个元素，段内扫描几乎全 cache hit；其三，若节点内有序，还能先比值域（首尾元素）
快速跳过整段、命中段内再做二分。这正是上面查找演示里「先比节点值域、再进段内」的来由。
**三种结构的权衡。**展开链表坐在数组与链表中间——牺牲一点随机访问（要先定位到节点再在节点内偏移），换来比普通链表小得多的指针开销和好得多的缓存表现。
| 维度 | 普通链表 | 数组 / 动态数组 | 展开链表 |
|---|---|---|---|
| 随机访问第 k 个 | O(n) | O(1) | O(n / cap) 定位 + 段内偏移 |
| 中间插入 | O(1) 改指针 （已知位置） | O(n) 搬移 | 段内搬移 ≤ cap，偶尔 split |
| 指针 / 元数据开销 | 每元素一根指针 | 几乎为零 | 约 n / cap 根 |
| 顺序遍历缓存 | 节点分散，频繁 miss | 全连续，几乎全 hit | 段内连续，跨段才跳 |
工程里的同类思路。Redis 的 quicklist 就是把多个 ziplist（一段连续编码的小数组）用双向链表串起来，本质即展开链表；数据库与文件系统的 B+ 树叶子链也是「每个叶子装一批有序键 + 指向下一叶子的指针」，同样为批量顺序扫描而连续存放。展开链表是「把链表的节点做粗、做连续」这一思路的最小模型。