计算机本来没有算法
先有编码，后有数据结构，然后有可算法

基础数据结构

数组

java 内置 顺序存储
数组的缺点，要先定义长度，但很多时候长度是不一定的，定多了浪费，定少了用不了
优点，可以通过索引直接访问任意元素

堆栈 stack

先进后出，只对栈顶元素操作
堆中存放对象
栈中存放基本类型
下拉栈：数组实现，map中的数据超过负载因子，发生的resize方法 ，新增或者删除元素都可能发生resize

list

对数组进行扩展，引入长度len ，并内置增删改查，相比于数组无需指定大小，当新增时超过原数组大小后，扩容一倍
删除时只需要修改len的位置即可

链表

递归数据结构，应用指向另一个链表对象或者null，链式存储 链表核心属性 head , node ,next ,value

//遍历链表
for (node x = first; x!=null;x=x.next){
  
}

删除技巧：将下一个节点拷贝到当前节点，删除下一个节点
为什么使用链表(优点)：
可以处理任何数据
所需空间和集合大小成正比
操作时间和集合大小无关

缺点:只能通过遍历取值

所以链表实现的下拉栈不用新增修改实现resize方法

队列 queue

先进先出，在尾列新增，在首列删除

背包 Bag

背包的特点，只能放入，遍历，不能删除。

基于链表的扩展

当我们根据数据hash%链表的长度 计算数据的存放位置时，由于数据越来越多，就会出现余数重复或者hash值一样的数据
注：（事实上，更好的取链表位置的方法是当链表长度为2^n时：（链表长度-1）&hash可以快速得到在链表中的位置，比起除法取余数，计算机更擅长做&, | , << ,>>等运算）
为了解决以上问题，可以采用2个方法解决
1.如果数据上hash重复，就把它向后再移动一位，直到出现空链表，这样做的好处是节省空间，缺点是没法一次根据hash快速定位
2.当链表不为空时，基于该链表追加一个新的链表也就是拉链法，将冲突的数据往新链表中追加
但再使用这种准备解决时，也有了新的问题，数据频繁冲突；

数据频繁冲突的原因有2种：
1.hash算法不好，计算出的值容易重复，除了改进hash算法，也可以使用rehash即对hash值再次hash的方法使数据均匀分布
2.数据量太大，而链表太短，这种情况考虑链表扩容即可，但是具体什么时候扩容，每次扩容多少呢？
我们可以参考java中hashmap的桶，hashmap的桶默认长度是16，负载因子是 0.75
当数据量 > 16x0.75 时 开始扩容，扩容大小为16<<1 即16*2=32
当然具体问题具体分析，我们可以适当的调整负载因子的大小，使它更契合业务，当负载因子变小时，数据更容易扩容，同样的，数据发生碰撞的概率也越小，适合查找多而增删少的情况，因为数据扩容会花费较多时间，反之~~

树

如果代码中的基本常量是一个点，链表是一条线，那么树就是一个面；

二叉树

起因：遍历一个链表查找数据太慢
改进：链表排序，二分查找

普通二叉树

将链表的第一个值做根节点，比第一个小的在左边，大的在右边，以此类推
存在问题，当链表是有序时。树会变成一条链表

平衡二叉树

当左右节点失去平衡时，数据发生旋转来达到左右平衡，提高查询效率
树左旋：根节点变左子节点，原右子节点变为根节点，原右子节点的左子节点变为先左子节点的右子节点，原右子节点的右子节点变为现右子节点
右旋相反
存在问题：旋转耗费时间，数据量太大时，每次增加节点都有可能会发生大规范的翻转

红黑树

在二叉树上添加颜色，根节点为黑色，每个节点下方必须是相反的颜色，null为红色，最终节点必须都是红色
由于颜色的存在，平衡二叉树无法发生大规模的翻转，减少额外时间损耗，缺点，查询效率略低于平衡二叉树
翻转比平衡二叉树多一步变色

多叉树（b树）

采用分段查找来降低树的查询深度，主要用于优化机械硬盘查询

b+树

在根节点只存储分段索引而不存具体数据，直到尾节点存储具体值
所有的尾节点链表都相互连接
优点：优化存储，优化查询（查询过的数据，下次查询在附近）

图

图是一个具有顶点与连线（边）的集合，根据连线有无方向可分为有向图与无向图
更适合描述关系的数据结构

存储结构

邻接矩阵

用一个集合表示顶点，另一个二维数组来表示边；

邻接表

用一个对象集合表示顶点，每个对象用单链表的形式表示下一个连接顶点，如果有权重，在边对象上新增权重属性

图中的算法

1.最小生成树
2.最短寻路算法
3.AOE拓扑排序