数据结构

MST-数据结构java实现：https://www.cnblogs.com/yangyquin/p/4921664.html

算法题网址：https://leetcode-cn.com/problemset/all/

头条：https://leetcode-cn.com/explore/featured/card/bytedance/245/data-structure/1049/

newCoder：https://www.nowcoder.com/contestRoom

数据结构分类：

一、列表型

1、数组

开辟一片连续的空间，将元素依次放入其中；

数组的好处：可以进行随机访问，只需要一个下标就可以访问到该元素；但插入和删除会比较耗费时间，插入和删除操作都需要将之后的元素进行整体的移动，腾出空间来进行对应的操作。

2、链表

每一个节点通过 next 值链接起来；查找元素耗费时间O(n)，需要一个计数器，从表头开始顺着 next 依次往后找，数到第 n 个就可以将第 n 个元素取出来；但插入和删除不会耗费时间，插入操作只需要将插入前后的两个集成打断，再将插入的元素连接起来即可；删除操作只要将要删除的元素跳过即可，

3、队列

不支持随机访问，只支持 push 和 pop 操作，push 将元素放进去，pop 将元素拿出来，拿出的顺序是先进先出

4、栈

不支持随机访问，只支持 push 和 pop 操作，push 将元素放进去，pop 将元素拿出来，拿出的顺序是先进后出

二、树型

1、二叉树

每个节点最多有两个孩子节点，分为左孩子节点和右孩子节点；

二叉树要点：

a.二叉树具有唯一的根节点；

b.二叉树中每个节点最多有两个孩子，每个节点最多有一个父亲节点；一个孩子也没有的叫做叶子节点

c.二叉树具有天然的递归结构【每个节点的左子树也是二叉树、每个节点的右子树也是二叉树】

2、搜索树

a.二分搜索树是二叉树

b.二分搜索树的每个节点的值：大于其左子树的所有节点的值且小于其右子树的所有节点的值

c.二分搜索树的每个子树也是二分搜索树

d.存储的元素必须具有可比较性【存储自定义数据类型，必须自定义好数据的比较方式】

3、优先队列

a.普通队列：先进先出，后进后出

b.优先队列：出队顺序和入队顺序无关；和优先级相关

三、图形

1、无向图

每个节点之间没有方向，可以从 a--b ，也可以 b--a ,但每个边有权重

2、有向图

所有的边都是单向的，只能从 a--b,b不能到 a,要让 b 到 a 则必须再加一条边

3、有向无环图

可以描述任务之间的层级关系，

相关算法：深度优先遍历【能够看到图的每个节点】

广度优先遍历【走迷宫，识别联通块】

拓扑排序【有很多先后的依赖关系，先做哪一个】

最短路径/最小生成树