我们知道用数组存放数据时，必须事先定义数组的长度（即元素个数）。当事先难以确定有多少个元素时，则必须把数组定义的足够大，以保证成功。无疑，这会造成内存浪费。因此可以考虑设计一种物理存储单元上非连续、非顺序的存储结构，来避免数组带来的问题，链表正是这样的一种数据结构。

链表由一系列结点（链表中每一个元素称为结点）组成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

更多内容参考 LinkedList

栈是一种最基本、最常用的数据结构，一个词来总结栈的特点就是后进先出。我们可以将栈看作是一个数据仓库，向栈内增加数据的操作叫入栈(push)操作，从栈内取出数据的操作叫出栈(pop)操作。不过不像一般的仓库一样，可以随意取出任何位置的物品，从一个栈取出的数据必须是最后一次增加的数据。换句话就是说，最后一个进入栈的数据，会被第一个取出来。

生活中有很多场景包含有后进先出的思想，比如刷盘子这个过程，我们将已经洗好的盘子叠在一起，每次洗好一个盘子就将堆在顶部，而我们需要用一个盘子时也是从最上面取走。

栈有许多典型应用场景，比如函数调用，表达式计算，表达式转换，模拟递归等。

更多内容参考 Stack

堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

更多内容参考 Heap

哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即 key，即可查找到其对应的值。例如若关键字为k，则其值存放在 f(k) 的存储位置上，由此不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为哈希表（散列表）。

哈希查找第一步就是使用哈希函数将键映射成索引，这种映射函数就是哈希（散列）函数。哈希函数需要易于计算并且能够均匀分布所有键。一个好的哈希函数必须在理论上非常的快、稳定并且是可确定的。

对不同的关键字可能得到同一散列地址，即k1 != k2，而f(k1)=f(k2)，这种现象称为冲突（Collision），避免hash碰撞碰撞的方法有：拉链法，开放定址法，再散列，建立一个公共溢出区等。

更多内容参考 HashTable

树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0 时，称这棵树为空树。在一棵非空树T 中：

1. 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
2. 除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm 为这个根结点的子树（subtree）。

二叉树是每个节点最多有两个子树的树结构。二叉树的每个结点至多只有二棵子树，二叉树的子树有左右之分，次序不能颠倒。

二叉查找树，也称排序二叉树，是指一棵空树或者具备下列性质的二叉树(每个结点都不能有多于两个儿子的树)：

1. 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意结点的左、右子树也分别为二叉查找树；
4. 没有键值相等的结点。

更多内容参考 BS_Tree

AVL树是最早提出的自平衡二叉树，它是一种特殊的二叉搜索树，任一节点的左子树深度和右子树深度相差不超过1，所以它也被称为高度平衡树。

更多内容参考 AVL_Tree

红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除等操作。

更多内容参考 RB_Tree

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

更多内容参考 Graph

位图（bitmap）是一种非常常用的结构，在索引，数据压缩等方面有广泛应用，能同时使存储空间和速度最优化。例如可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合，可以用 01110100100 表示集合 {1,2,4,5,8} ，对应位置数字存在标记为1，否则标记为0。

C 语言位图实现如下：

主要程序如下：

#define SHIFT 5  
#define MASK 0x1F  

//set 设置所在的bit位为1  
//clr 初始化所有的bit位为0  
//test 测试所在的bit为是否为1  

set(int i) {
    a[i>>SHIFT] |=  (1<<(i & MASK)); }  
clr(int i) {
    a[i>>SHIFT] &= ~(1<<(i & MASK)); }  
test(int i){
    return a[i>>SHIFT] & (1<<(i & MASK)); } 

字节位置=数据/32 (采用位运算即右移5位)
位位置=数据%32 (采用位运算即跟0X1F进行与操作)。

特定适用场合：

1. 对10亿个不重复的整数进行排序。
2. 找出10亿个数字中重复的数字。

如果用普通的排序算法，数据放进内存就需要 ( 10^9 * 4)/( 2^30 ) = 3.7G。改用 Bitmap 的话，一个数字占一位，一共需要 3.7/32 ＝ 0.1 G 内存。

《剑指 Offer》
树、森林与二叉树的转换
数据结构之树
轻松搞定面试中的二叉树题目
卡特兰数
详解bitmap算法
浅谈算法和数据结构: 十一 哈希表
哈希碰撞