块状链表（块状数组）

数组与链表

在讨论块状链表（或者称块状数组）之前，我们先回顾一下数组和链表的特点：

操作数组 （通常考虑有序）链表存储结构地址连续的存储单元，物理位置相邻地址不连续，物理位置不相邻定位O (1)O (N)插入O (N)O (1)删除O (N)O (1)

数组定位的效率很高，直接通过下标索引就能获取元素的定位，由于长度通常是固定的，因此不适合插入和删除等操作。当数组为有序时，使用二分查找法效率较高，时间复杂度为 O (logN)。

链表的插入和删除效率较高，但定位效率较低，最差情况需要遍历整个链表才能定位到目标节点元素。

块状数组

假设一个数据可以用一个大数组进行存储，当我们按照某个间距把这个大数组划分成若干个小数组，这个的结构我们称之为块状数组。

当每一个小数组作为节点存储到一个链表中时，这样的结构就能成为块状链表。实际上，两者的宏观逻辑是一致的。

块状链表

块状链表结合了数组和链表的优点，使得所有操作的时间复杂度都为 O ($\sqrt{N}$)。

从结构设计上看，块状链表实际上是个链表，但链表中每个节点又是一个数组。在处理实际问题时，我们可以先确定操作对象位于哪个区间，即位于哪个小数组中，而不用通过遍历每一个元素来定位目标对象，从而提升效率。

定位

从链表头节点开始遍历，根据某些条件（如边界值、特征值等）定位某一个节点（块、数组），再遍历节点内数组，确定偏移量。

随后即可进行查询、插入、删除等操作。

复杂度分析

假设数据总数为 N，数组的长度固定为 n，那么在理想状况下划分的块数目为 N/n，那么

定位的时间复杂度为 O (N/n)；插入、删除的时间复杂度为 O (n)。

令 N/n = n，则 n = $\sqrt{N}$，即每次操作的时间复杂度约为 O ($\sqrt{N}$)。

与平衡树相比较：时间复杂度较大，空间复杂度较小。

平衡树块状链表时间复杂度O (logN)O ($\sqrt{N}$)空间复杂度O (N)O ($\sqrt{N}$)