块状链表
| 块状链表 | |
|---|---|
| 术语名称 | 块状链表 |
| 英语名称 | unrolled linked list |
| 别名 | block linked list |
块状链表(unrolled linked list)是一个结合了顺序表（数组）与链表的变种。 块状链表在结构上类似每个结点的内容都是数组的链表，每个数组也称为“块”(block)，所以也说成是每个结点是一块数据的链表。 这一结构利用了数组局部处的内存连续性，使得大部分相邻结点可以在内存中相邻，由于访问局部性原理对缓存更加友好； 一方面又利用了链表插入删除的低时间复杂度，在进行插入删除时可以将需要调整位置的元素限制在单个结点中，当结点溢出时进行结点的分裂。
块状链表中的顺序表层次通常是有长度标记（若结点内头部不可动）或头尾范围指针（若结点内头部也可动）的静态数组，通过这一标记或元素确定其中实际元素数量，以保证结点中只有有限数量的数据。在不同实现中，这一数组大小可能是固定的，也可能是浮动的，作为内存数据结构时一般会希望结点大小接近且不超过缓存行大小。也就是说希望每次加载时都通过局部性刚好把一个块加载到缓存中。
块状链表中的链表层次也可能是单向链表、双向链表以及其循环变体。
由于每个结点的长度有区别，进行下标访问会需要找到遍历链表层找到指定结点，为了便于这一过程，块状链表中可能存有一个结点索引，用于更加方便地找到指定偏移量的结点。
也可以认为 B+-树的叶子所在层是一个固定结点内数组长度的块状链表。跳表索引将分块连接成链表也可以看成是类似把一块块数据连接成链表的操作，只是内层不是数组。
结构
以结点固定长度、结点中有元素数字段、结点间是单向链表、有索引的块状链表举例。
块状链表结点可以抽象成如图所示结构。
整体结构。
变体
数组层是有头尾指针的数组，或者说类似于循环数组的常见实现的结构。
加入数组作为索引层，可以代替链表层物理链接。
最常见的实现是直接使用索引层代替结点间的物理连接，用索引位置加结点内位置共同标识结构内的位置。
语言实例
| 块状链表 | |||
|---|---|---|---|
| 语言 | 版本/库 | 对应内容 | 说明 |
| C | C89 | 人工实现 | - |
| C++ | C++98 | std::deque
|
STL |
复杂度
空间复杂度
块状链表整体空间复杂度为线性复杂度，每个结点保存多个数据，且结点大小与其保存数据大小控制在正比范围，使得结点数量与数据量成正比。但是由于结点有额外预留内存，且需要额外保存链接，比起直接保存有额外常数。考虑每个数据的大小 [math]\displaystyle{ d }[/math] 和链接大小 [math]\displaystyle{ p }[/math] 的关系，并控制块大小在 [math]\displaystyle{ b/2~2b }[/math] ，近似为 [math]\displaystyle{ \sim \frac{bd+p}{bd} n=O(n) }[/math] 。
时间复杂度估计与优化
本节讨论块状链表对其逻辑结构线性表的操作实现。
首先记块状链表元素数为 [math]\displaystyle{ n }[/math] ，块目标容量为 [math]\displaystyle{ b }[/math] ，
块的合并与分割
如果没有合适的合并与分割块的机制，只考虑朴素的不够时增加多余时释放，随着数据的不断随机插入删除，经过足够长的时间，依概率块状链表的结构会走向极端场景：或者数据分散于大量结点，也就是说拥有大量结点但每个结点只有几个元素，此时接近一层链表；或者数据聚集于少数结点，这些结点中有大量元素，但是结点数极少，此时块状链表接近一层顺序表。这两种情况都使得块状链表失去了自身结合二者的优点，因此块维护机制是必要的。
一种常见的块维护机制是指定目标容量，指结点中元素个数，以下记作 [math]\displaystyle{ b }[/math] 。在插入元素时，若块的大小超过 [math]\displaystyle{ b }[/math] ，则将块拆分为两个 [math]\displaystyle{ b/2 }[/math] 的块；在删除元素时，若块小于合并阈值，如 [math]\displaystyle{ b/2 }[/math] ，且周围有合并后仍然不超过 [math]\displaystyle{ b }[/math] 的块，合并成一个块。 也有的文献中把块的大小范围描述为不足 [math]\displaystyle{ b }[/math] 合并，超过 [math]\displaystyle{ 2b }[/math] 拆分，与这一说法只是字母设置区别。
一般目标容量与合并阈值有差异，取 [math]\displaystyle{ \alpha b }[/math] 较多，以避免同一个位置反复插入删除时产生抖动。在一些材料里，认为合并阈值和目标容量直接取 [math]\displaystyle{ B/2\~2B }[/math] 范围，等效于 [math]\displaystyle{ \alpha=1/4 }[/math] 的情况。
插入删除操作
想要插入指定位置时，首先考虑插入该位置所在的结点。
如果当前结点容量足够，这一操作就是在结点动态数组中的插入，需要依次向后移动后续的数据以腾出空位，并将这个结点插入。
如果当前结点容量不足，则这一操作需要分裂结点，因此需要首先分配额外结点。 按照常见策略，结点的分裂是均匀的，也就是将后一半元素移动到新结点上，并且过程中可能可以将新元素插入。
相反，需要删除时，默认是从当前数据的删除。如果之后检查到当前结点中元素数少于合并阈值，且检查相邻结点合并也不会超过一个结点（也可以是进行标记，然后检查是否连续被标记。一般两个低于阈值的结点合并后的 [math]\displaystyle{ 2\alpha b }[/math] 距离一个结点 [math]\displaystyle{ b }[/math] 仍有些距离），那么进行合并。将后续结点中的元素合并移动到第一个结点中，然后释放掉额外的结点。
时间复杂度总结
记链表长度为 [math]\displaystyle{ n }[/math] ，每个块的目标容量为 [math]\displaystyle{ b }[/math] 个元素，且分析时静态地视为 [math]\displaystyle{ b }[/math] 。
与上面示意图不同，这里假设链表层是双向链表，这样是更常见的实现。与前面单链表的区别是这样第一可以方便地进行尾部操作，第二不会在寻找上一元素时跨结点导致需要额外时间重新找到结点。
| 操作 | 最好 | 最坏 | 平均 | |
|---|---|---|---|---|
| 基本操作 | 初始化 Create
|
不初始化结点为一次分配 | ||
长度 Length/Size
|
[math]\displaystyle{ O(\frac{n}{b}) }[/math] ，如果没维护则遍历结点累加 | |||
| 清空 | [math]\displaystyle{ O(n) }[/math] ，逐个结点逐个元素销毁 | |||
| 元素获取 | 指定索引 Get(i)
|
[math]\displaystyle{ \Theta(1) }[/math] ，头尾 | - | [math]\displaystyle{ \sim \frac{n}{b} + 1 = O(\frac{n}{b}) }[/math] ，需要遍历到指定结点并计算剩余偏移量 |
指定位置 Get(p)
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
头部 Head
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
尾部 Rear
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
| 插入删除 | 块分割代价 | [math]\displaystyle{ \sim 1 + b/2 = O(b) }[/math] ，创建新块、移动半个结点的 [math]\displaystyle{ b/2 }[/math] 个元素，连接结点 | ||
| 块合并代价 | [math]\displaystyle{ \sim 1 + b = O(b) }[/math] ，合并几个总元素不足 [math]\displaystyle{ b }[/math] 的相邻块，连接并删除结点 | |||
指定索引（不含分割合并） Insert(i,x)/Remove(i)
|
[math]\displaystyle{ \Theta(1) }[/math] ，头尾 | - | [math]\displaystyle{ \sim \frac{1}{2} \cdot \frac{n}{b} + 1 = O(\frac{n}{b}) }[/math] ，平均遍历长度 | |
指定位置（不含分割合并） InsertAfter(p,x)/RemoveAfter(p)
|
[math]\displaystyle{ \Theta(1) }[/math] ，只需要插入删除结点后校验分割合并 | |||
| 头部（不含分割合并） | [math]\displaystyle{ \Theta(1) }[/math] | |||
| 尾部（不含分割合并） | [math]\displaystyle{ \Theta(1) }[/math] | |||
| 元素顺序 | 指定位置前趋后继 Pred/Succ
|
[math]\displaystyle{ \Theta(1) }[/math] ，结点内相邻 | [math]\displaystyle{ \Theta(1) }[/math] ，涉及跨结点情况，需找到上下结点 | [math]\displaystyle{ \Theta(1) }[/math] ，虽然两种情况取值不同，都是常数时间 |
注意其中插入、删除由于有两部分，实际是一个 [math]\displaystyle{ O(\frac{n}{b}+b) }[/math] 操作。
块长调节
一般选择块状链表时，往往是为了同时平衡插入删除和随机访问的复杂度，比如文本编辑器等需要大量中间插入删除并保持索引的场景。这些场景中插入、删除复杂度为 [math]\displaystyle{ O(\frac{n}{b}+b) }[/math] ，查找是 [math]\displaystyle{ O(b) }[/math] 。而其中 [math]\displaystyle{ b }[/math] 是预先决定的参数。总是存在一定的取值范围保证复杂度的合理可接受。
尽管这个复杂度表达有均值不等式形式，但其实由于其常数系数、插入删除与查找两种操作的使用比例均存在差别，在各个场景下进行加权平均后，最小值会取到某个带有系数的 [math]\displaystyle{ b=k\sqrt{n} }[/math] 上，且这个 [math]\displaystyle{ k }[/math] 随场景变化。一般在分析时可以按渐近分析习惯省略系数简写为 [math]\displaystyle{ b \approx \sqrt{n} }[/math] ，此时查找、插入、删除的复杂度均为 [math]\displaystyle{ O(\sqrt{n}) }[/math] 。
另外考虑实际场景，缓存行能否保证一次载入同一结点会相当大地影响时间复杂度中的操作系数，因此按照缓存行大小设置块大小也是合理的选择。