数据结构
链表
- 链表在内存中是乱序排放的，下一个元素中存放上一个元素的指针
- 所以在链表中要查询某个元素，需要从第一个元素开始遍历，时间复杂度为 O(n)
- 链表中插入一个元素比较简单，将上一个元素的指针指向它，它的指针再指向下一个元素即可，时间复杂度 O(1)
- 删除同理，把上一个元素的指针直接指向它指向的元素即可，时间复杂度 O(1)
- 删除元素的内存空间不需要特意回收，以后如果需要用到这块空间，直接用新数据覆盖即可
- 把链表的首尾相连就会变成一个环形。称为：循环链表或环形链表
- 把链表每个节点的指针设为2个，分别指向上一个节点和下一个节点，这就是双向链表
数组
- 数组在内存中是连续排放的，每个元素开辟相同的内存
- 所以数组的查询很方便，根据下标能快速计算出指针的位置，时间复杂度 O(1)
- 数组中插入一个元素比较麻烦，需要将该位置后面的元素依次往后移动，时间复杂度 O(n)
- 删除同理，需要将后面的元素依次往前移动，时间复杂度 O(n)
- 追加到最后、删除最后一个元素、修改某个元素，时间复杂度 O(1)
栈
- 栈像一个箱子，先入后出，后入先出 (LAST IN FIRST OUT)
- 栈的入栈和出栈时间复杂度都是 O(1)
队列
- 队列像一个漏的箱子，先入先出，后入后出 (FIRST IN FIRST OUT)
- 队列入栈和出栈时间复杂度都是 O(1)
- 系统开发中常用的消息队列就是用队列实现的
哈希表
- 哈希表是一种 key => value形式的数据结构，PHP中的数组就是通过哈希表实现的
- 一个哈希表的好坏取决于它的哈希函数和合理哈希表长度设计（决定了哈希冲突的概率）
- 哈希冲突后，可以使用拉链法(链地址法)或开放地址法等方法解决冲突
- 哈希表的获取和设置的时间复杂度都是 O(1)，当发生冲突时，退化到 O(n) n为链表的长度
堆
常用语言都封装了高效的堆结构（比如：斐波那契堆），大部分操作都是O(1)的 heap)
这里以小顶二叉堆举例（类似用模来举例hash函数一样）
- 堆是一种特殊的二叉树结构，可以用来实现优先队列
- 堆中每个节点最多有2个子节点，并且子节点必须大于父节点
- 所以顶部节点肯定是最小的节点
- 堆的节点顺序是逐行从上到下，从左到右
往堆中添加数据，时间复杂度 O(logn)
- 一般添加到最后一行靠左的位置，没位置的话就再起一行
- 然后根据子节点大于父节点的原则依次向上交换
往堆中取数据，时间复杂度 O(logn)
- 一般只取顶部节点，时间复杂度 O(1)，但是取完之后需要重新调整结构，所以时间复杂度会上升到 O(logn)
- 取完顶部节点后，将最后一行最右边的节点替换到顶部节点
- 然后依次跟子节点中的较小节点进行交换，直到满足子节点大于父节点
二叉查找树
又叫二叉搜索树或二叉排序树
- 每个节点均大于其左子树上任意一个节点，所以最小节点从顶端开始往其左下的末端寻找
- 每个节点均小于其右子树上任意一个节点，反之最大节点从顶端开始往其右下的末端寻找
- 添加节点，从顶端开始依次比较大小，小的往左下交换，大的往右下交换
- 查找节点，从顶端开始依次比较大小，比当前节点小，往左下查找。比当前节点大，往右下查找。等于当前节点，查询结束
- 删除节点
- 如果没有子节点，直接删除即可
- 如果只有一个子节点，删除节点后，将子节点移上来即可
- 如果有两个以上子节点，从左子树中寻找最大子节点（左子树的最右子节点）或者从右子树中寻找最小子节点（右子树的最左子节点）移上来即可
有很多基于二叉查找树的扩展数据结构
- 如：平衡二叉查找树，让其始终保持均衡形态，以提高查找效率
- 我们可以把子节点扩展为 n 个，n为预先设定的常数，像这种子节点可以自由设定并且形状均衡的树叫作B树
图
由顶点（节点）和连接每对顶点的线组成的图形就叫作图
- 如果给每条线增加一个权重值，就叫作加权图
- 如果给每条线增加一个方向箭头，就叫作有向图（有向图也可以加上权重值）
- 社交关系、地跌线路、计算机网络等都可以用个图来表示
使用图结构，可以计算两个节点之间的最小权重和（最短距离、最小网络耗时、最低公交票价等）
广度优先搜索
- 从离顶点最近的点开始依次横向搜索，直到找到相应的节点，或者走到终点
- 从A到H的可能路径（见下图），A->B->C->D->E->F->G->H。（A->B或C或D是随机的）
- 可以利用队列的先进先出来完成候选节点的选择
深度优先搜索
- 从离顶点最近的点开始依次纵向搜索，直到找到相应的节点，或者走到终点
- 从A到H的可能路径（见下图），A->B->E->F->C->G->H。 A->B或C或D是随机的）
- 可以利用栈的后进先出来完成候选节点的选择
graph TD
A((A))-->B((B))
A((A))-->C((C))
A((A))-->D((D))
B((B))-->E((E))
B((B))-->F((F))
C((C))-->G((G))
C((C))-->H((H))
D((D))-->I((I))
D((D))-->J((J))
贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径
- 计算最短路径时，边的权重代表的通常都是时间、距离或者路费等，因此基本都是非负数，不过，即便权重为负，贝尔曼-福特算法也可以正常运行
- 但是，如果在一个闭环中边的权重总和是负数，那么只要不断遍历这个闭环，路径的权重就能不断减小，也就是说根本不存在最短路径
- 遇到这种对顶点进行N次更新操作后仍能继续更新的情况，就可以直接认定它"不存在最短路径"
迪杰斯特拉（Dijkstra，也可以翻译为狄克斯特拉）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径
- 比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，迪杰斯特拉算法多了一步选择顶点的操作，这使得它在求最短路径上更为高效
- 但是如果图中含有负数权重，迪杰斯特拉算法可能会无法得出正确答案，这一点和贝尔曼-福特算法有所不同
总的来说，就是不存在负数权重时，更适合使用效率较高的迪杰斯特拉算法，而存在负数权重时，即便较为耗时，也应该使用可以得到正确答案的贝尔曼-福特算法
A*（A-Star）算法也是一种在图中求解最短路径问题的算法，由迪杰斯特拉算法发展而来。迪杰斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径
也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A*就会预先估算一个值，并利用这个值来省去一些无用的计算