《征服数据结构》块状链表

摘要：

1，块状链表的介绍

2，块状链表的代码实现（Java和C++）

1，块状链表的介绍

前面我们讲过数组和链表，数组具有 O(1)的查询时间，O(N)的删除，O(N)的插入，而链表具有 O(N)的查询时间，O(1)的删除，O(1)的插入。应该说这两种数据结构都有优缺点，那么这两种数据结构能不能结合起来使用呢？当然是可以的，结合起来就是我们今天要讲的块状数组。

前面讲到链表时候，我们知道链表的每个节点只存储一个数据，如果数据量比较多的话查找起来比较麻烦，比如我们要查找第10000个节点，需要从头开始遍历链表。

如果我们使用块状链表，链表的每个节点相当于一个块，假如每个块存放1000个数据，我们只需要查找10次就可以定位到所在的块，然后在块中可以直接获取元素的值。

如果要插入元素，找到对应的块即可插入，插入的时候只需要移动待插入块中后面的元素，其他所有块中的元素不需要移动，虽然插入元素的效率比链表低，但比起数组还是有很大的提升。

对于块状链表有两点要注意，一个是插入的时候如果当前块已经满了，没法在插入了，可以把该块分裂成两个，每个存储原块一半的元素，然后在执行插入。

还有就是删除的时候如果删除之后，该块的元素个数已经很少了，并且他的前一个块或者后一个块中元素个数也非常少，这个时候可以考虑两个块进行合并。如果不合并，就会退化成链表，查找效率大大降低。