1、 简述
在开展计算机算法时，大家常见的二种线形算法设计是二维数组和链表。他们都有优点和缺点。二维数组特性是原素在运行内存中紧挨着储存，因此优势是精准定位快（O(1)），缺陷是插进删掉慢（O(n)）；而链表则不一样，它根据表针将不一样部位的原素连接起來，因此优点和缺点与二维数组恰好反过来：精准定位慢（O(n)），插进删掉快（O(1)）。文中详细介绍一种新的算法设计：小块链表，它将二维数组和链表的优势融合来，各种各样实际操作的算法复杂度均为O(sqrt(n))。
2、 小块链表的操作过程
小块链表融合了二维数组和链表的优点和缺点，促使各种各样那一个实际操作的算法复杂度均为O(sqrt(n))。 从总体上看，小块链表是一个链表， 而在链表的每一个连接点上，以二维数组的方式储存一组原素。实际以下：
操作过程：
（1）精准定位：先精准定位原素所属的链表连接点，随后再精准定位该原素在二维数组中的部位。
（2）瓦解：将某一链表连接点瓦解成2个连接点。
（3）插进：最先精准定位要插进的部位，随后将所属连接点瓦解成2个连接点，并将数据信息放进第一个连接点的结尾。 假如要插进的是一大块数据信息，最先要将数据信息切割成好几个block（每一个block相匹配一个小块链表的一个连接点）并将这种block链起來，随后将他们插进那2个连接点中间。
（4）删掉：最先精准定位删掉原素的部位，随后依照数组删除原素的方式删掉该数据信息。假如删掉一大块数据信息，最先要精准定位数据信息块首原素和末原素所属的部位，随后各自将他们所属的连接点瓦解成2个连接点，最终删掉首原素和末原素中间的连接点就可以。
3、 关键环节和复杂性剖析
该优化算法的关键是明确链表长短和每一个连接点的数组长度，及其如何确保这一长短值？设小块链表中原素总数量为X，链表长短为n，每一个连接点中数据长短为m，则当m=n=sqrt(X)时，可确保m和n另外最少，这时各种各样实际操作的算法复杂度最少。在具体运用时，需保持小块链表的每一个连接点尺寸在[sqrt(n)/2, 2*sqrt(n)]，不然，小块链表会衰退。维护保养方式是，适度的情况下，对连接点开展合拼与瓦解（维护保养自身不容易使复杂性提升）。
4、 运用
（1） 文本编辑设计方案：http://download.noi.cn/T/noi/noi2002A.pdf
程序代码参照：
http://hi.baidu.com/wuyijia/blog/item/7085fa004423cd86e850cdeb.html
（2） 维护保养序列：http://download.noi.cn/T/noi/noi2005A.pdf
程序代码参照：
http://hi.baidu.com/zbwmqlw/blog/item/54cce1004e799c0c1d9583b7.html
5、 小结
因为小块链表的每一个连接点储存的是一个二维数组，假如二维数组是静态数据的（的尺寸固定不动），则会消耗储存空间；如果是动态性的，则必须经常的申请办理或是释放出来室内空间，比较严重减少系能。因而，当信息量十分巨大时，设计方案有效的二维数组室内空间维护保养对策看起来至关重要。
6、 参考文献
（1） 毕业论文《对块状链表的一点研究》
（2） 二维数组 链表=小块二维数组：http://starforever.blog.hexun.com/3184024_d.html
