块状链表(Unrolled Linked List)

定义

块状链表(Unrolled Linked List,展开链表)是链表与数组的混合体:链表的每个节点不再存单个元素,而是存放一个容量固定(如数百个元素)的小数组,节点之间用指针串联。

原理

块大小通常取约 sqrt(n) 或按缓存行/内存页对齐。随机访问先沿链表跳块(每次跳过一块的元素数),再在块内数组定位;插入时若块满则分裂为两块,删除后相邻块过空则合并,保证每块保持在半满以上,整体操作复杂度约 O(sqrt(n))。

应用

文本编辑器用块状链表管理大文档的行或字符序列,使中部插入删除不必整体搬移;部分内存分配器和早期数据库页管理也用类似分块思路;算法竞赛中的"块状链表"题型(如维护带插入删除的序列)是其直接应用,与分块(sqrt decomposition)思想同源。

优缺点

优点是缓存命中率远高于普通链表、指针开销摊薄、中部修改比数组便宜;缺点是实现比两种基础结构都复杂,随机访问仍慢于纯数组,块的分裂合并需要仔细处理。