数据结构复习：链表、数组、栈、队列、哈希表、堆、二叉树
时间复杂度
链表
在链表中，数据的添加和删除都较为方便，访问比较耗时间
每个数字都有一个“指针”，指向下一个数据内存地址。
数据无需存储在连续空间
访问某个数据：从第一个开始依次往下顺续访问
查找所需时间：O(n)；增删所需时间：O(1);
循环链表；双向链表
数组
数组中，访问数据十分简单，而添加和删除数据比较耗工夫
查找所需时间：O(1)；增删所需时间：O(n);
栈
只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。
往栈中添加数据的操作叫作“入栈”（push）。出栈同理
像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为 Last In First Out，简称 LIFO。
*深度优先搜索算法
队列
队列中添加和删除数据的操作分别是在两端进行的
像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为 First In First Out，简称 FIFO。
*广度优先搜索算法
哈希表
哈希表存储的是由键（key）和值（value）组成的数据。
我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。
链地址法：在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。
堆
堆是一种图的树形结构，被用于实现“优先队列”
优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。
一个结点最多有两个子结点
排列顺序：从上到下，从左到右
子结点必定大于父结点
取出最小值时间：O(1)
由于取出数据后需要将最后的数据移到最顶端，，那么重构树的时间复杂度便为O(logn)
添加数据：O(logn)
*狄克斯特拉算法
二叉查找树
二叉搜索树、二叉排列数
两个性质：
1、每个结点的值均大于其左子数上任意一个结点的值，如9大于其左子树上的3和8；15大于左子树上的所有数字。
2、每个结点的值均小于其右子树上任意一个结点的值，如15小于其右子树上的23、17和28。
结论：
1、二叉查找树的最大结点要从顶端开始，往其右下的末端寻找，此处为3。
2、二叉查找树的最大结点要从顶端开始，往其右下的末端寻找，此处为28。
添加数据：从顶端结点开始，依次向下比较，与结点中的值进行比较，小于它则往 左移，大于它则往右移。
删除数据：若该数：没有子结点，直接删掉即可；有一个子结点，删掉目标结点，将子结点的数移到被删除结点的位置上即可；有两个子结点，删掉目标结点，在被删除结点的左子树中寻找最大结点，移到被删除的位置（被删结点的右子树中寻找最小结点，并替换也可以）。如果有更多结点，则需递归执行前面的操作。
二分查找算法思想的树形结构体现
数据比较的次数取决于数的高度。结点数为n，树的形状又较为均衡，时间复杂度为O(logn)，若树的形状朝单侧纵向延伸，时间复杂度变为O(n)。
平衡二叉查找树：这种数据结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率。
数取决于数的高度。结点数为n，树的形状又较为均衡，时间复杂度为O(logn)，若树的形状朝单侧纵向延伸，时间复杂度变为O(n)。
参考书籍：我的第一本算法书 (石田保辉 宮崎修一)
