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

### 存储介质与访问特性

| 类型 | 说明 |
|------|------|
| **内存** | 利用电容和晶体管存储数据，因电容会缓慢漏电，需要持续供电；断电即丢失数据（易失性），但读写速度极快（纳秒级），支持按字节随机访问 |
| **固态硬盘 (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) | 支持高效范围查询 |