块状链表的长度

2026-04-14

0. 引入

块状链表就是一个链表，每个节点指向一个空间大小为 的数组。一个链表长度为 ，数组空间大小为 的块状链表能装至多 个元素。

给定参数 和 ，在块状链表中查找一个元素的复杂度是 ，朴素插入和删除一个元素的复杂度是

给定总元素数量 ，我们希望固定合适的 ，让 保持尽可能小，从而让插入和删除更快。接下来介绍一种维护块状链表的策略，在这个策略下可以保证 恒成立，并且这里的 不可改进，因此只需让 尽可能小，固定 即可。

注：这里的 不可改进，是说不存在 和 使得 恒成立

1. 维护策略

为了完整描述这个策略，只需要考虑块状链表上的两个操作：插入和删除。

在某个节点中插入元素时，如果节点指向的数组未满，就直接在该数组中插入元素即可。

在某个节点中插入元素时，如果节点指向的数组已满，我们不得不开辟一个新的节点。此时，执行分裂操作，把数组中的元素尽可能均分到原节点和新节点，然后插入那个元素。这样操作的结果是，元素个数为 的节点 变成了元素个数分别为 和 的两个相邻节点

在某个节点中删除元素时，先在数组中删除这个元素，如果删除后节点为空则直接删除该节点。然后考虑该节点是否可以和左相邻的节点合并，如果数组元素个数之和 ，那么就合并两个数组的元素到一个节点。否则，再考虑是否可以和右相邻的节点合并。

2. 直观

直觉上，“分裂” 和 “合并” 让数组不会过于空。具体地，“分裂” 让分裂出的数组都至少有 那么大，而 “合并” 让相邻的小数组被合成更大的数组。它们分别暗示了两个理想中的全局性质：

  1. 任意一个数组的元素个数都
  2. 任意两个相邻数组的元素个数和都

性质 和性质 的任何一个成立都能让数组的平均元素个数控制在 级别，从而使 控制在 附近。可惜的是，这无法做到。性质 不能在 “分裂” 操作后保持，性质 不能在 “删除” 操作后保持。

实际上，把数组的平均元素个数控制在 级别是不可能的，可以构造这样的例子：

首先，通过不断插入得到这样的链表，数组元素个数序列如下：

然后，对奇数位置反复删除至 ：

最后，对所有的 都插入一次，造成分裂：

此时，数组的平均元素个数为 ，大约为 ，当元素个数趋于无穷时，可以看出 是不可改进的

幸运的是， 已经是最坏情况了！我们接下来就给出 的证明！

3. 证明

引理 1：任何时刻，对于链表上连续的两个节点，其数组元素个数分别为 ，则 和 不能同时成立

证明：

对数组操作进行数学归纳：

base case：当链表为空时，命题平凡成立。

case 1：如果最后一步是不产生分裂的插入，那么设受到影响的区间是 ，它变为了 ，考虑新的二元组 ，都保持了目标性质，这是因为

case 2：如果最后一步是产生分裂的插入，那么设受到影响的区间是 ，可以知道 ，它变为了 ，考虑新的二元组 ，都保持了目标性质，这是因为

注意，这里的 和 可以为空，例如当 为空时，应理解为 是链首节点，区间 变为了 ，新的二元组有 ，其他情形和接下来的证明类似，不再强调

case 3：如果最后一步是不产生合并的删除，那么设受到影响的区间是 ，它变为了 ，考虑新的二元组 ，都保持了目标性质，这是因为不不发生合并说明

case 4：如果最后一步是产生合并的删除，那么设受到影响的区间是 ，它变为了 ，考虑新的二元组 ，都保持了目标性质，这是因为

证毕。

引理 2：任何时刻，对于链表上连续的三个节点，其数组元素个数分别为 ，如果 ，则 和 不能同时成立

证明：

对数组操作进行数学归纳：

base case：当链表为空时，命题平凡成立。

case 1：如果最后一步是不产生分裂的插入，那么设受到影响的区间是 ，它变为了 ，考虑新的三元组 ，都保持了目标性质，原因如下：

  1. 和 保持了性质，是因为
  2. 保持了性质。如果 ，那么由引理 1，，那么如果 ，可知 ；如果 ，那么由归纳假设，，

case 2：如果最后一步是产生分裂的插入，那么设受到影响的区间是 ，可以知道 ，它变为了 ，考虑新的三元组 ，都保持了目标性质，原因如下：

  1. 保持了性质，是因为 ，若 ，则
  2. 和 保持了性质，是因为
  3. 保持了性质，是因为 ，若 ，则

case 3：如果最后一步是不产生合并的删除，那么设受到影响的区间是 ，它变为了 ，考虑新的三元组 ，都保持了目标性质，这是因为不发生合并说明

case 4：如果最后一步是产生合并的删除，那么设受到影响的区间是 ，它变为了 ，考虑新的三元组 ，都保持了目标性质，原因如下：

  1. 和 保持了性质，是因为
  2. 保持了性质，是因为由引理 1， 和 必有一个 ，不妨设是 ，那么由于 满足性质，可以知道 或 ，而 ，如果 ，则 ，如果 ，则

证毕。

引理 3：任何时刻，对于链表上连续的三个节点，其数组元素个数分别为 ，则

证明：

显然，节点非空，所以

如果 ，那么由引理 1，，

如果 ，那么由引理 2，要么 ，要么 ，于是

结论：

证明：

这等价于 ，进一步等价于

若 ，则恰可以将链表分为连续的 段，每段的总元素个数至少为 ，故 ，

若 ，则将链表分为连续的 段后还剩余尾部的 个节点，故 ，

若 ，则将链表分为连续的 段后还剩余尾部的 个节点，故 ，

证毕。