块状链表的长度

2026-04-14

0.引入

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

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

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

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

1.维护策略

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

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

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

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

2.直观

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

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

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

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

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

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

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

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

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

3.证明

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

证明：

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

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

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

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

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

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

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

证毕。

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

证明：

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

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

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

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

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

保持了性质，是因为，若，则
和保持了性质，是因为
保持了性质，是因为，若，则

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

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

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

证毕。

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

证明：

显然，节点非空，所以

如果，那么由引理 1，，

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

结论：

证明：

这等价于，进一步等价于

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

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

证毕。

4.补充

在实践中，链表操作和数组操作速度不同，要最小化的目标为，那么应该取为，另一个影响因素是，我们一般希望是的幂次，所以调参还是要靠测试，这篇文章仅用于展示一个漂亮的理论结果，对调参没有什么价值。