块状链表

块状链表
术语名称	块状链表
英语名称	unrolled linked list
别名	block linked list

块状链表(unrolled linked list)是一个结合了数组与链表的变种。 块状链表在结构上类似每个结点的内容都是数组的链表，每个数组也称为“块”(block)，所以也说成是每个结点是一块数据的链表。 这一结构利用了数组局部处的内存连续性，使得大部分相邻结点可以在内存中相邻，由于访问局部性原理对缓存更加友好； 一方面又利用了链表插入删除的低时间复杂度，在进行插入删除时可以将需要调整位置的元素限制在单个结点中，当结点溢出时进行结点的分裂。

块状链表中的数组层次通常是有长度标记或哨兵元素的静态数组，通过这一标记或元素确定其中实际元素数量，以保证结点中只有有限数量的数据。在不同实现中，这一数组可能是固定的，也可能是浮动的，作为内存数据结构时一般会接近缓存行大小。也就是说希望每次加载时都通过局部性刚好把一个块加载到缓存中。

块状链表中的链表层次也可能是单向链表、双向链表以及其循环变体。

由于每个结点的长度有区别，进行下标访问会需要找到遍历链表层找到指定结点，为了便于这一过程，块状链表中可能存有一个结点索引，用于更加方便地找到指定偏移量的结点。

也可以认为 B+-树的叶子所在层是一个固定结点内数组长度的块状链表。跳表索引将分块连接成链表也可以看成是类似把一块块数据连接成链表的操作，只是内层不是数组。

结构

以结点固定长度（[math]\displaystyle{ b }[/math]）、结点中有元素数字段、结点间是单向链表、有索引的块状链表举例。

块状链表结点可以抽象成如图所示结构。

整体结构。

语言实例

块状链表
语言	版本/库	对应内容	说明
C	C89	人工实现	-
C++	C++98	std::deque	STL