数据结构是算法的基石，如果没有扎实的数据结构基础，想要把算法学好甚至融会贯通是非常困难的，而优秀的算法又往往取决于你采用哪种数据结构。接下来介绍一些常用的数据结构。
一、数组
优点
- 构建数组十分简单
- 能让我们在O(1)的时间复杂度里根据数组的下标查询某个元素
缺点
- 需要分配一段连续的空间
- 查询某个元素需要遍历整个数组，耗费O(n)的时间复杂度
- 删除或者添加某个元素的时候，同样耗费O(n)时间
二、链表
分类
单链表
- 链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起
双链表
- 与单链表不同，双链表的每个节点都含有两个引用字段
优点
- 灵活的分配内存空间
- 能在O(1)时间内删除或者添加元素
缺点
- 无法通过下表读取元素，每次都要从链表头开始一个个读取
- 查询n个元素需要O（n）时间
解题技巧
利用快慢指针（有时需用到三个指针）
- 链表的翻转
- 寻找倒数第K个元素
- 寻找链表中间位置的元素
- 判断链表是否有环
构建一个虚假的链表头
- 一般用在要返回新的链表的题目中
LeetCode例题
- K个一组翻转链表
三、栈
特点
- 后进先出（LIFO）
实现
- 利用一个单链表来实现栈的数据结构。而且，因为我们都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在 O(1) 的时间内完成。
应用场景
- 在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。
LeetCode例题
- 20 有效的括号
- 739 每日温度
四、队列
特点
- 先进先出 FIFO
实现
- 可以借助双链表来实现队列。双链表的头指针允许在队头查看和删除数据，而双链表的尾指针允许我们在队尾查看和添加数据。
应用场景
- 当处理有序、数量在持续变化的数据时。算法题中广度优先遍历BFS是运用队列最多的地方
五、双端队列
特点
- 双端队列和普通队列最大的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。
实现
- 利用一个双链表实现双端队列
应用场景
- 双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间
LeetCode例题
- 239 滑动窗口最大值
六、树
常见形状
- 普通二叉树
- 平衡二叉树
- 完全二叉树
- 二叉搜索树
- 四叉树（Quadtree）
- 多叉树（N-ary Tree）
- 红黑树（Red-Black Tree）
- 自平衡二叉搜索树（AVL Tree）
遍历方式
前序遍历（Preorder Traversal）
- 先根、再左、再右
- 应用场景：运用最多的场合包括在树里进行搜索以及创建一棵新的树。
中序遍历（Inorder Traversal）
- 先左、再根、再右
- 应用场景：最常见的是二叉搜索树，由于二叉搜索树的性质就是左孩子小于根节点，根节点小于右孩子，对二叉搜索树进行中序遍历的时候，被访问到的节点大小是按顺序进行的。
后序遍历（Postorder Traversal）
- 先左、再右、再根
- 应用场景：在对某个节点进行分析的时候，需要来自左子树和右子树的信息。收集信息的操作是从树的底部不断地往上进行，好比你在修剪一棵树的叶子，修剪的方法是从外面不断地往根部将叶子一片片地修剪掉。
LeetCode例题
- 230 二叉搜索树中第K小的元素
- 250 统计同值子树
以下为一些比较高级的数据结构。
七、优先队列
与普通队列的区别
- 保证每次取出的元素是队列中优先级最高的
- 优先级别可自定义
最常用的场景
- 从杂乱无章的数据中按照一定的顺序或者优先级进行数据筛选
本质
- 本质是一个二叉堆的结构，利用一个数组结构来实现完全二叉树
特性
- 数据里的第一个元素拥有最高的优先级
基本操作
- 向上筛选
- 向下筛选
LeetCode例题
- 347 前K个高频元素
八、图
基本知识
- 阶、度
- 树、森林、环
- 有向图、无向图、完全有向图、完全无向图
- 连通图、连通分量
- 图的存储和表达方式：邻接矩阵、邻接链表
相关算法
图的遍历
- 深度优先
- 广度优先
环的检测
- 有向图
- 无向图
拓扑排序
最短路径算法
Dijkstra
- Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法
Bellman-Ford
- 求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达。但算法可以进行若干种优化，提高了效率。
Floyd Warshall
- Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
连通性相关算法
Kosaraju
- 是线性时间的算法来找到一个有向图的强连通分量
Tarjan
- 一个关于 图的联通性的神奇算法。基于DFS（迪法师）算法，深度优先搜索一张有向图
求解孤岛的数量
- 判断是否为树
图的着色、旅行商问题
LeetCode例题
- 785 判断二分图
九、前缀树（字典树）
性质
每个节点至少包含两个基本属性
- children
- isEnd
前缀树的根节点是空的
- 除了根节点，其他所有节点有可能是单词的结尾，叶子节点一定都是单词的结尾
基本操作
创建
- 遍历一遍输入的字符串，对每个字符串的字符进行遍历
- 从前缀树的根节点开始，将每个字符加入到节点的children字符集当中
- 如果字符集已经包含了这个字符，则跳过
- 如果当前字符是字符串的最后一个，则把当前节点的isEnd标记为真
搜索
- 从前缀树的根节点触发，逐个匹配输入的前缀字符，如果遇到了就继续往下一层搜索，如果没遇到，就立即返回
优点
- 每隔节点还能保存额外信息，比如可以记录拥有相同前缀的所有字符串。因此，当用户输入某个前缀时，就能在O(1)的时间内给出对应的推荐字符串。
LeetCode例题
- 212 单词搜索II
十、线段树
定义
- 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
基本结构
- 线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b]。长度为1的线段称为元线段。非元线段都有两个子结点，左结点代表的线段为[a,(a + b) / 2]，右结点代表的线段为[((a + b) / 2）+1,b]。
LeetCode例题
- 315 计算右侧小于当前元素的个数
十一、树状数组
特点
- 利用数组来表示多叉树
- 树状数组的第一个元素是空节点
- 如果节点tree[y]是tree[x]的父节点，那么需要满足条件：y = x - (x & (-x))
LeetCode例题
- 308 求一个动态变化的二维矩阵里，任意子矩阵里的树的总和