1、常见数据结构
线性：数组，链表，队列，堆栈，块状数组（数组+链表），hash表，双端队列，位图（bitmap）
树：堆（大顶堆、小顶堆），trie树（字母树or字典树），后缀树，后缀树组，二叉排序/查找树，B+/B-，AVL树，Treap，红黑树，splay树，线段树，树状数组
图：图
其它：并查集
2、常见算法
（1） 基本思想：枚举，递归，分治，模拟，贪心，动态规划，剪枝，回溯
（2） 图算法：深度优先遍历与广度优先遍历， 最短路径，最小生成树，拓扑排序
（3） 字符串算法：字符串查找，hash算法，KMP算法
（4） 排序算法：冒泡，插入，选择，快排，归并排序，堆排序，桶排序
（5） 动态规划：背包问题，最长公共子序列，最优二分检索树
（6） 数论问题：素数问题，整数问题，进制转换，同余模运算，
（7） 排列组合：排列和组合算法
（8） 其它：LCA与RMQ问题
数据结构之块状链表
1、 概述
在进行算法设计时，我们常用的两种线性数据结构是数组和链表。它们各有优缺点。数组特点是元素在内存中紧挨着存储，因而优点是定位快（O(1)），缺点是插入删除慢（O(n)）；而链表则不同，它通过指针将不同位置的元素链接起来，因而优缺点与数组正好相反：定位慢（O(n)），插入删除快（O(1)）。本文介绍一种新的数据结构：块状链表，它将数组和链表的优点结合来，各种操作的时间复杂度均为O(sqrt(n))。
2、 块状链表的基本操作
块状链表整合了数组和链表的优缺点，使得各种那个操作的时间复杂度均为O(sqrt(n))。 从整体上看，块状链表是一个链表， 而在链表的每个节点上，以数组的形式存储一组元素。具体如下：
基本操作：
（1）定位：先定位元素所在的链表节点，然后再定位该元素在数组中的位置。
（2）分裂：将某个链表节点分裂成两个节点。
（3）插入：首先定位要插入的位置，然后将所在节点分裂成两个节点，并将数据放到第一个节点的末尾。 如果要插入的是一大块数据，首先要将数据切成多个block（每个block对应一个块状链表的一个节点）并将这些block链起来，然后将它们插入那两个节点之间。
（4）删除：首先定位删除元素的位置，然后按照数组删除元素的方法删除该数据。如果删除一大块数据，首先要定位数据块首元素和末元素所在的位置，然后分别将它们所在的节点分裂成两个节点，最后删除首元素和末元素之间的节点即可。
3、 关键点和复杂度分析
该算法的核心是确定链表长度和每个节点的数组长度，以及怎么保证这个长度值？设块状链表中元素总个数为X，链表长度为n，每个节点中数据长度为m，则当m=n=sqrt(X)时，可保证m和n同时最小，此时各种操作的时间复杂度最低。在实际应用时，需维持块状链表的每个节点大小在[sqrt(n)/2, 2*sqrt(n)]，否则，块状链表会退化。维护方法是，适当的时候，对节点进行合并与分裂（维护本身不会使复杂度增加）。
4、 应用
（1） 文本编辑器设计：http://download.noi.cn/T/noi/noi2003A.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
————————————————————————————————————-
更多关于数据结构和算法的介绍，请查看：数据结构与算法汇总
————————————————————————————————————-
原创文章，转载请注明： 转载自董的博客
本文链接地址: http://dongxicheng.org/structure/blocklink/ （可查看更多相关内容）
作者：Dong，作者介绍：http://dongxicheng.org/about/