常见数据结构与算法速查，涵盖线性结构、树形结构、图结构、哈希表、排序算法、最小生成树及复杂度分析

存储介质与访问特性

类型	说明
内存	利用电容和晶体管存储数据，因电容会缓慢漏电，需要持续供电；断电即丢失数据（易失性），但读写速度极快（纳秒级），支持按字节随机访问
固态硬盘 (SSD)	浮栅晶体管存储数据，断电不丢失（非易失性），速度远快于机械硬盘，但存储单元有擦写寿命上限
机械硬盘 (HDD)	磁性盘片存储数据，磁头通过读取磁性读取数据；容量大、单价低，但依赖盘片旋转和磁头移动寻址，速度慢

设计启示：内存适合随机访问（如数组、哈希表）；磁盘按块读写、顺序访问远快于随机访问（如 B+ 树索引、日志结构的存储引擎）。

---

线性结构与有序索引

线性结构中元素之间存在"一对一"的前后关系，是最基础的数据组织方式。

数组

在内存中占用一块连续的空间，按下标顺序存放元素的线性结构。

• 随机访问 O(1)：知道首地址和元素大小后，可通过"首地址 + i × 元素大小"直接算出任意元素的位置，按下标查找速度极快
• 插入 / 删除 O(n)：为了保持内存连续，插入或删除后需要移动其后的所有元素
• 动态数组：空间不足时自动扩容（通常 1.5～2 倍）并整体搬迁，尾部追加均摊 O(1)，如 C++ vector、Java ArrayList、Python list
• 典型应用：读多写少、频繁按索引访问的场景；也是哈希表、堆、图的邻接矩阵等结构的底层实现

链表

内存空间不连续，每个节点存放数据和指向相邻节点的指针，通过指针将节点串联起来。

• 查找 O(n)：无法随机访问，必须从头节点开始沿指针逐个遍历
• 插入 / 删除 O(1)：定位到位置后只需修改相邻节点的指针（前提是已经找到该位置）
• 常见变体：
  • 单向链表：只有指向后继的 next 指针
  • 双向链表：同时有 prev / next 指针，支持反向遍历，Java LinkedList 即基于它实现
  • 循环链表：尾节点指回头节点，适合约瑟夫问题、轮询调度
• 典型应用：频繁增删、长度不确定的场景，如 LRU 缓存、内存管理中的空闲块链表

数组 vs 链表

对比项	数组	链表
随机访问	O(1)	O(n)
头部插入 / 删除	O(n)	O(1)
内存布局	连续，CPU 缓存友好	分散，指针有额外开销
容量	动态数组需扩容搬迁	按需分配，天然弹性

栈

操作受限的线性表，只能在栈顶进行压入 和弹出 操作，遵循后进先出 原则。

• 核心操作：入栈 Push、出栈 Pop、查看栈顶 Peek，均 O(1)
• 用数组（顺序栈）或链表（链式栈）均可实现
• 典型应用：
  • 函数调用栈：保存局部变量、参数和返回地址，递归正是依赖它
  • 括号匹配、表达式求值（中缀转后缀）
  • 浏览器前进后退、编辑器撤销（Ctrl+Z）
  • 深度优先搜索（DFS）的非递归实现

队列

操作受限的线性表，从队尾添加元素、从队头移除元素，遵循先进先出 原则。

• 核心操作：入队 Enqueue、出队 Dequeue，均 O(1)
• 循环队列：用数组实现时把首尾逻辑上相连成环，下标按 (tail + 1) % n 计算，避免反复搬移数据造成的"假溢出"
• 变体：双端队列 Deque（两端都能进出）、优先队列（按优先级出队，底层通常是堆）
• 典型应用：消息队列 / 任务调度、广度优先搜索（BFS）、CPU 就绪队列、生产者-消费者模型

跳表

有序链表的升级版：在底层链表之上，按随机化原则（逐层抽稀）建立多级索引，查找时从最高层逐层"跳跃"缩小范围，实现类似二分的快速查找。

• 查找 / 插入 / 删除平均 O(log n)；插入删除只需修改指针，不像平衡树那样需要旋转
• 空间换时间：索引平均需要额外的 O(n) 空间
• 与红黑树相比：实现简单、范围查询方便、并发场景更容易实现
• 典型应用：Redis 有序集合（ZSet）的核心实现之一、LevelDB / RocksDB 的内存表

---

树形数据结构

树是 n 个节点的有限集合，元素之间存在"一对多"的层次关系。常用术语：根节点、叶子节点、深度 / 高度、度（子节点个数）。

二叉树

每个节点最多只有两个子节点（左子节点和右子节点）。

• 特殊形态：
  • 满二叉树：每层节点都达到最大
  • 完全二叉树：只允许最后一层缺右边的连续节点，可用数组紧凑存储（下标 i 从 0 开始时，左右孩子是 2i+1、2i+2，父节点是 (i-1)/2 向下取整），堆正是利用了这一点
• 四种遍历（均为 O(n)）：
  • 前序（根左右）、中序（左根右）、后序（左右根）：递归实现，深度优先
  • 层序：借助队列逐层访问，即广度优先
• 前序 + 中序（或后序 + 中序）可以唯一重建一棵二叉树

二叉搜索树

在二叉树基础上增加排序规则：任意节点的左子树所有节点 < 根 < 右子树所有节点（左小右大），能显著提高查找效率。

• 查找 / 插入 / 删除平均 O(log n)：每次比较可排除约一半节点，过程类似二分查找
• 中序遍历结果是有序序列
• 退化问题：如果按 1、2、3、4、5 这样的有序数据依次插入，树会退化成一条链表，复杂度退为 O(n)——这正是引入平衡树的原因
• 删除节点：若节点有两个孩子，用中序后继（右子树中最小的节点）替换后再删除

堆

本质是完全二叉树，且满足堆序性质：最大堆（父节点大于等于子节点）与最小堆（父节点小于等于子节点）。

• 通常用数组实现（利用完全二叉树的编号规律），无需指针
• 核心操作：
  • 插入：放到末尾后逐层上浮，O(log n)
  • 取堆顶：取出堆顶后，把末尾元素移到堆顶再逐层下沉，O(log n)
  • 建堆：自底向上逐个下沉，O(n)
• 典型应用：
  • 优先队列：Java PriorityQueue、C++ priority_queue
  • Top-K 问题：取最大的 K 个数维护小顶堆，复杂度 O(n log k)
  • 堆排序：建堆后反复取堆顶，原地 O(n log n)
  • Dijkstra 最短路、定时任务调度

平衡二叉树

为了解决普通二叉搜索树退化成链表的问题，在插入 / 删除后通过旋转（红黑树还有变色）调整保持树的平衡，确保查找复杂度维持在 O(log n)。

• AVL 树：严格平衡，任意节点左右子树高度差不超过 1；查找更快，但插入删除时旋转频繁，适合读多写少
• 红黑树：近似平衡（最长路径不超过最短路径的 2 倍），通过红黑着色规则限制失衡程度，调整代价小，综合性能最好：
  • 规则：节点非红即黑、根节点为黑、红节点的子节点必为黑、任一节点到叶子的每条路径含相同数量的黑节点
  • 典型应用：Java HashMap（链表长度超过 8 转红黑树）、TreeMap，C++ std::map，Linux 内核进程调度

B 树 / B+ 树

多路平衡搜索树：节点可以有多个子节点（成百上千个），因此树非常"矮胖"，适合数据库索引。

• 设计动机：数据库索引存放在磁盘上，按块读取；树越矮，一次查询需要的磁盘 I/O 次数越少。3～4 层的 B+ 树即可索引千万级数据
• B 树：键和数据都存在所有节点中，查找可能在任意一层命中
• B+ 树：数据只存在叶子节点，非叶子节点只存索引键；叶子节点之间用链表串联成有序链表，天然支持范围查询和顺序遍历
• 典型应用：MySQL InnoDB 索引、MongoDB、文件系统（NTFS、ext4）

字典树

专门用于处理字符串的多叉树：每个节点代表一个字符，从根到某节点的路径拼出一个前缀，利用公共前缀节省空间。

• 查找 / 插入 O(k)：k 为字符串长度，与词库总量无关
• 节点中用标记位表示"是否是一个完整单词的结尾"
• 典型应用：搜索框自动补全与输入联想、拼写检查、词频统计、IP 路由最长前缀匹配、敏感词过滤

---

哈希结构

哈希表

通过哈希函数将键 映射到数组的下标，把键值对散列存储，实现平均 O(1) 级别的快速查找。

• 哈希函数：把任意长度的数据通过算法转化为固定长度的哈希值，要求计算快、分布均匀、结果确定
• 哈希冲突：不同键被映射到同一个下标（鸽巢原理决定了无法完全避免），两种主流解决方案：
  • 链地址法（拉链法）：冲突位置挂一条链表，过长时转红黑树，Java HashMap 采用
  • 开放寻址法：冲突后按探测序列（线性 / 二次探测等）寻找下一个空位，Python dict、Redis 采用
• 扩容：负载因子（元素数 / 槽位数）超过阈值时数组扩容并重新哈希所有元素，单次 O(n)，均摊后仍 O(1)
• 典型应用：缓存（Redis）、数据库哈希索引、数据去重，以及语言内置的 Map / Set

---

图、连通性与最小生成树

图的表示与遍历

组成：由顶点和边组成，用于表达"多对多"的关系，边可以带权重。

分类：

• 有向图（边有方向，如微博的关注关系）
• 无向图（边无方向，如微信好友关系）
• 带权重图（边有代价，如地图导航中的距离）

存储方式：

• 邻接矩阵：n × n 的二维数组，查边 O(1)，但空间固定 O(n²)，适合稠密图
• 邻接表：每个顶点挂一个列表存放其邻居，空间 O(n + e)，适合稀疏图

两种遍历（均为 O(n + e)）：

• DFS 深度优先：一条路走到黑再回溯，用栈 / 递归实现，适合找路径、判断连通性
• BFS 广度优先：逐层扩散，用队列实现，可求无权图的最短路径

常见问题与算法：拓扑排序（有向无环图）、最短路径（Dijkstra、Floyd）、最小生成树（Kruskal、Prim）、连通分量（并查集）

并查集

高效处理不相交集合的合并及查询问题，能快速回答"两个元素是否属于同一个集合"（例如判断两个人是否在同一个家族中）。

• 核心操作：
  • Find：找到元素所在集合的代表（根节点）
  • Union：把两个集合合并成一个
• 两大优化（配合使用后单次操作近乎 O(1)）：
  • 路径压缩：查询时把沿途节点直接指向根
  • 按秩 / 按大小合并：总是把矮的树挂到高的树下
• 典型应用：朋友圈合并、无向图环检测、Kruskal 算法判环、动态连通性问题

最小生成树

在带权连通无向图中选出一棵包含所有顶点的树：只有 n − 1 条边、不含环，且所有边的权重之和最小。两个经典算法都基于贪心策略。

算法	复杂度	说明
Kruskal 算法	O(E log E)	按边权重从小到大排序，逐一添加不构成环（用并查集判断）的边，直到选满 n − 1 条；适合稀疏图
Prim 算法	O(E log V)（堆优化）	从任意顶点开始，每次选择与当前树连接的最小权重边，不断向外扩张；适合稠密图

---

排序算法

初级排序算法

时间复杂度 O(n²)，实现简单，适合小规模或基本有序的数据。

算法	稳定性	说明
冒泡排序	稳定	从第一个元素开始，比较相邻的两个元素，大的往后交换，每次循环会把当前最大值"冒泡"到末尾，完成一个元素的正确排序
选择排序	不稳定	每次循环从未排序数据中找出最小（或最大）的数据，与未排序区第一个元素交换，放入已排序末尾
插入排序	稳定	每次循环将一个未排序数据插入到已排序数据中的合适位置，类似整理扑克牌；对基本有序的数据可接近 O(n)

稳定性：排序后相等元素的相对次序保持不变。

高效排序算法

平均时间复杂度 O(n log n)，基于分治思想。

算法	稳定性	说明
归并排序	稳定	不断地将数组一分为二，分别排好序后使用双指针法进行合并；任何情况都是 O(n log n)，但需要 O(n) 的额外空间
快速排序	不稳定	选择基准后将数组一分为二（小的放基准左边、大的放右边），并递归重复这个过程；平均 O(n log n)，最坏情况（已有序且固定取首元素为基准）退化为 O(n²)；原地排序、常数小，实践中通常最快

---

复杂度与性能比较

时间复杂度和空间复杂度描述随数据量 n 增加时，算法的操作时间和内存消耗会如何增长，用大 O 表示法表示，忽略常数系数与低阶项，只保留增长最快的部分。

• 常见量级（从小到大）：
  • O(1) 常数（哈希表查找）→ O(log n) 对数（二分查找、平衡树）→ O(n) 线性（遍历数组）→ O(n log n)（归并、快排平均）→ O(n²) 平方（冒泡、选择、插入）→ O(2ⁿ) 指数 → O(n!) 阶乘（全排列枚举）
• 三种情况：同一算法要区分最好、最坏、平均复杂度；例如快排平均 O(n log n)，取决于基准划分是否均衡
• 均摊复杂度：动态数组尾部追加虽然偶尔触发 O(n) 扩容，但均摊到每次操作是 O(1)
• 空间复杂度：统计额外的辅助空间，如归并排序 O(n)、递归调用栈深度 O(log n)
• 注意：O(n log n) 与 O(n²) 的差距随 n 增大而急剧拉开，n 很大时必须选择低阶算法

常见数据结构操作复杂度速查

数据结构	查找	插入 / 删除	备注
数组	O(1)（按下标）	O(n)	按值查找为 O(n)
链表	O(n)	O(1)（已定位时）	定位本身需 O(n)
栈 / 队列	O(n)	O(1)（受限端操作）	只操作栈顶 / 队头队尾
哈希表	O(1) 平均	O(1) 平均	冲突严重时最坏 O(n)
二叉搜索树	平均 O(log n)	平均 O(log n)	不平衡时最坏退化到 O(n)，平衡后稳定 O(log n)
堆	堆顶 O(1)	O(log n)	取最值 O(1)
跳表	平均 O(log n)	平均 O(log n)	支持高效范围查询