块状链表是什么？它如何在数组和链表之间做折中？
简化版
块状链表是每个链表节点里存一小段数组，而不是只存一个元素。它用块内连续数组改善缓存局部性，又用块之间链表连接降低大规模插入删除的搬移成本，是数组和链表之间的折中结构。
详细版
普通链表每个节点一个元素，指针开销高、缓存局部性差。块状链表把多个元素放进一个块：
- 块内部是数组，顺序访问快。
- 块之间用指针连接，插入删除只影响局部块。
- 块满时可以分裂，块太空时可以合并或借元素。
- 常用于文本编辑、序列维护、需要折中随机访问和插入删除的场景。
它不是为了替代所有数组或链表，而是在“元素很多、局部编辑多、又希望减少指针开销”时提供折中。
完整版教学
一、普通链表和数组各自的痛点
数组连续存储，遍历和随机访问很快，但中间插入删除可能要搬移大量元素。链表插入删除可以只改指针，但每个节点一个元素，指针多、分配多、缓存局部性差。
块状链表尝试折中：
[1,2,3,4] -> [5,6,7,8] -> [9,10]每个节点不是一个值，而是一小段数组。块内享受数组连续性，块间享受链表可拼接性。
二、块大小为什么重要
块太小，就退化得接近普通链表，指针开销和跳转仍然多。块太大，中间插入删除时块内搬移成本又接近数组。
假设块容量是 64。插入一个元素时，通常只需要在某个块内移动最多几十个元素；如果块满了，就把一半元素分裂到新块。
插入前：[1,2,3,4] -> [8,9]
在第一个块插入 5，若容量允许：
[1,2,3,4,5] -> [8,9]块大小常根据缓存行、元素大小、操作模式调参。它不是固定公式，而是性能工程里的折中参数。
三、插入时如何分裂块
当目标块已满时，可以分裂成两个块。例如容量 4 的块 [1,2,3,4] 要插入 5，可以先分裂：
[1,2] -> [3,4]再把 5 插入合适的块：
[1,2] -> [3,4,5]这样一次插入不会导致整条序列都移动，只影响一个或两个块。复杂度通常和块大小有关，而不是和总元素数完全绑定。当然，如果还要按下标定位块，可能需要额外索引或从头累计长度。
四、删除时为什么可能需要合并块
删除元素后，某些块可能变得很空。如果长期不处理，会出现大量半空块，浪费内存并增加链表跳转。
常见策略：
| 情况 | 处理方式 |
|---|---|
| 块仍较满 | 只在块内删除 |
| 块低于阈值 | 向相邻块借元素 |
| 两个相邻块都较空 | 合并成一个块 |
| 删除后块为空 | 移除该块 |
这和 B 树节点分裂合并有一点相似：都在维护“每个节点不要太满也不要太空”的平衡。
五、它为什么改善缓存局部性
普通链表每访问一个元素都可能跳到另一个内存位置。块状链表每进入一个块，可以连续访问块内多个元素。
如果一个块有 32 个整数，那么遍历这 32 个值时接近数组访问；只有跨块时才发生指针跳转。相比每个元素一个节点，跳转次数大幅减少。
普通链表：跳 1000 次访问 1000 个元素
块状链表：块大小 50 时，大约跳 20 次这就是它在大量顺序扫描和局部编辑混合场景下有意义的原因。
六、适用场景和限制
块状链表适合长序列的局部插入删除、文本缓冲、编辑器内部结构、需要减少单节点链表开销的场景。它不适合极端随机访问，因为按下标找块仍然可能需要遍历块列表，除非再加树状索引。
记忆钩子：块状链表是“链表节点里装数组”，用块内连续性换缓存，用块间指针换局部修改。
七、常见误区与追问
- 误区：块状链表随机访问一定是 O(1)。 只有块内下标是 O(1)，找到第几个块可能仍要遍历或依赖额外索引。
- 误区：块越大越好。 块太大会增加块内搬移成本，接近数组中间插入。
- 误区：块越小越灵活。 块太小会退化成普通链表，指针和缓存问题又回来。
- 追问：它和普通链表最大区别是什么？ 一个节点存多个元素，减少指针数量并改善局部性。
- 追问：删除后为什么要合并块？ 防止大量低利用率块造成内存浪费和遍历跳转增加。
八、加强记忆
块状链表可以记成“数组和链表握手”。它不追求单点最优，而是让块内像数组、块间像链表。回答时围绕三个词讲：块大小、分裂合并、缓存局部性，就能把这个低频结构讲得很清楚。