数据结构与算法概览

总结一些数据结构与算法：

常见数据结构

数组

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组的特点：

• 支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
• 插入和删除操作比较低效，时间复杂度为 O(n)。
• 数组的大小固定，需要预先申请空间，如果空间不够，需要重新申请空间，再将原来的数据复制过去，时间复杂度为 O(n)。
• 数组的内存空间是连续的，所以在内存中的地址也是连续的，所以支持随机访问。

链表

链表是一种线性表数据结构，它用一组任意的内存空间，来存储一组具有相同类型的数据。

链表的特点：

• 不支持随机访问，只能从头开始遍历，时间复杂度为 O(n)。
• 插入和删除操作比较高效，时间复杂度为 O(1)。
• 链表的大小不固定，不需要预先申请空间，如果空间不够，需要重新申请空间，再将原来的数据复制过去，时间复杂度为 O(n)。
• 链表的内存空间是任意的，所以在内存中的地址也是任意的，所以不支持随机访问，所以支持动态扩容。

栈

栈是一种特殊的线性表数据结构，它只能在一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底。

栈的特点：

• 先进后出，后进先出。
• 支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
• 插入和删除操作比较高效，时间复杂度为 O(1)。
• 栈的大小固定，需要预先申请空间，如果空间不够，需要重新申请空间，再将原来的数据复制过去，时间复杂度为 O(n)。
• 栈的内存空间是连续的，所以在内存中的地址也是连续的，所以支持随机访问。
• 栈的应用：函数调用栈、表达式求值、括号匹配、浏览器前进后退、编辑器撤销操作。
• 栈的实现：数组实现、链表实现。
• 栈的优化：数组实现的栈，当栈满时，需要扩容，当栈空时，需要缩容，扩容和缩容的时间复杂度为 O(n)，可以使用循环队列来实现，当栈满时，不需要扩容，当栈空时，不需要缩容，时间复杂度为 O(1)。

队列

队列是一种特殊的线性表数据结构，它只能在一端进行插入操作，另一端进行删除操作，这一端称为队尾，另一端称为队头。

队列的特点：

• 先进先出，后进后出。
• 支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
• 插入和删除操作比较高效，时间复杂度为 O(1)。
• 队列的大小固定，需要预先申请空间，如果空间不够，需要重新申请空间，再将原来的数据复制过去，时间复杂度为 O(n)。
• 队列的内存空间是连续的，所以在内存中的地址也是连续的，所以支持随机访问。
• 队列的应用：消息队列、阻塞队列、并发队列。
• 队列的实现：数组实现、链表实现。
• 队列的优化：数组实现的队列，当队列满时，需要扩容，当队列空时，需要缩容，扩容和缩容的时间复杂度为 O(n)，可以使用循环队列来实现，当队列满时，不需要扩容，当队列空时，不需要缩容，时间复杂度为 O(1)。
• 阻塞队列：当队列满时，插入操作会被阻塞，当队列空时，删除操作会被阻塞。
• 并发队列：当队列满时，插入操作会被阻塞，当队列空时，删除操作会被阻塞，支持多线程并发操作。

跳表

跳表是一种特殊的链表数据结构，它通过添加多级索引来提高链表的查询效率。

跳表的特点：

• 支持随机访问，根据下标随机访问的时间复杂度为 O(logn)。
• 插入和删除操作比较高效，时间复杂度为 O(logn)。
• 跳表的大小不固定，不需要预先申请空间，如果空间不够，需要重新申请空间，再将原来的数据复制过去，时间复杂度为 O(n)。
• 跳表的内存空间是任意的，所以在内存中的地址也是任意的，所以不支持随机访问，所以支持动态扩容。
• 跳表的应用：Redis、LevelDB。
• 跳表的实现：链表实现。
• 跳表的优化：跳表的查询效率取决于索引的高度，索引的高度取决于索引的建立策略，索引的建立策略有两种，一种是随机建立索引，一种是按照固定的间隔建立索引，按照固定的间隔建立索引的时间复杂度为 O(logn)，随机建立索引的时间复杂度为 O(n)。

散列表

散列表是一种特殊的线性表数据结构，它通过散列函数将数据映射到散列表中的一个位置，来加快数据的查找效率。

散列表的特点：

• 支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
• 插入和删除操作比较高效，时间复杂度为 O(1)。
• 散列表的大小固定，需要预先申请空间，如果空间不够，需要重新申请空间，再将原来的数据复制过去，时间复杂度为 O(n)。
• 散列表的内存空间是连续的，所以在内存中的地址也是连续的，所以支持随机访问。
• 散列表的应用：Redis、LevelDB。
• 散列表的实现：数组实现。
• 散列表的优化：散列表的查询效率取决于散列函数的设计，散列函数的设计有两种，一种是直接寻址法，一种是拉链法，直接寻址法的时间复杂度为 O(1)，拉链法的时间复杂度为 O(1+k)，k 为链表的长度。
• 散列冲突：当两个数据映射到散列表的同一个位置时，称为散列冲突，散列冲突的解决方法有两种，一种是开放寻址法，一种是链表法，开放寻址法的时间复杂度为 O(1)，链表法的时间复杂度为 O(1+k)，k 为链表的长度。

二叉树

二叉树是一种特殊的树形结构，它的每个节点最多只能有两个子节点。

二叉树的特点：

• 二叉树的高度为 logn。
• 二叉树的遍历方式有三种，分别是前序遍历、中序遍历、后序遍历。
• 二叉树的应用：二叉搜索树、平衡二叉树、红黑树、B+ 树。
• 二叉树的实现：链表实现。
• 二叉树的优化：二叉树的遍历方式有两种，分别是深度优先遍历、广度优先遍历，深度优先遍历的时间复杂度为 O(n)，广度优先遍历的时间复杂度为 O(n)。
• 二叉搜索树：二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树的所有节点的值，小于右子树的所有节点的值，它的中序遍历是有序的。
• 平衡二叉树：平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不超过 1。
• 红黑树：红黑树是一种特殊的二叉搜索树，它的每个节点都有颜色，红色或者黑色，它的每个节点都满足以下条件：
  • 根节点是黑色的。
  • 每个叶子节点都是黑色的。
  • 不能有相邻的两个红色节点。
  • 从任意节点到叶子节点的所有路径都包含相同数目的黑色节点。
  • 红黑树的高度为 logn。
  • 红黑树的应用：Java 中的 TreeMap、TreeSet。
  • 红黑树的实现：链表实现。
  • 红黑树的优化：红黑树的插入和删除操作的时间复杂度为 O(logn)。
• B+ 树：B+ 树是一种特殊的二叉搜索树，它的每个节点都有多个子节点，它的每个节点都满足以下条件：
  • 根节点至少有两个子节点。
  • 每个节点至少有 m/2 个子节点。
  • 每个节点的子节点数目都比它少 1。
  • 所有叶子节点都在同一层。
  • B+ 树的高度为 logn。
  • B+ 树的应用：MySQL、MongoDB。
  • B+ 树的实现：链表实现。
  • B+ 树的优化：B+ 树的插入和删除操作的时间复杂度为 O(logn)。
  • B+ 树的区别：B+ 树的每个节点都存储数据，B 树的每个节点都不存储数据，B+ 树的叶子节点都有指针指向下一个叶子节点，B 树的叶子节点没有指针指向下一个叶子节点。
  • B+ 树的优点：B+ 树的查询效率比 B 树高，因为 B+ 树的内部节点不存储数据，所以 B+ 树的内部节点可以存储更多的子节点，所以 B+ 树的高度比 B 树低，所以 B+ 树的查询效率比 B 树高。

图

图是一种非线性表数据结构，它由顶点和边组成，顶点之间的关系用边表示。

图的特点：

• 图的遍历方式有两种，分别是深度优先遍历、广度优先遍历。
• 图的应用：社交网络、推荐系统。
• 图的实现：邻接矩阵实现、邻接表实现。
• 图的优化：图的遍历方式有两种，分别是深度优先遍历、广度优先遍历，深度优先遍历的时间复杂度为 O(n)，广度优先遍历的时间复杂度为 O(n)。
• 图的分类：无向图、有向图、无权图、有权图、稀疏图、稠密图。
• 无向图：无向图是一种特殊的图，它的边没有方向。
• 有向图：有向图是一种特殊的图，它的边有方向。
• 无权图：无权图是一种特殊的图，它的边没有权重。
• 有权图：有权图是一种特殊的图，它的边有权重。
• 稀疏图：稀疏图是一种特殊的图，它的边的数量接近于顶点的数量。
• 稠密图：稠密图是一种特殊的图，它的边的数量接近于顶点的数量的平方。
• 图的存储方式：邻接矩阵、邻接表、邻接多重表、十字链表、边集数组。

堆

堆是一种特殊的树形数据结构，它的每个节点都有一个值，且每个节点的值都大于等于（或小于等于）其子树中每个节点的值。

堆的特点：

• 堆的高度为 logn。
• 堆的遍历方式有两种，分别是深度优先遍历、广度优先遍历。
• 堆的应用：优先级队列。
• 堆的实现：数组实现。
• 堆的优化：堆的遍历方式有两种，分别是深度优先遍历、广度优先遍历，深度优先遍历的时间复杂度为 O(n)，广度优先遍历的时间复杂度为 O(n)。
• 堆的分类：大顶堆、小顶堆。
  • 大顶堆：大顶堆是一种特殊的堆，它的每个节点的值都大于等于其子树中每个节点的值。
  • 小顶堆：小顶堆是一种特殊的堆，它的每个节点的值都小于等于其子树中每个节点的值。