数据结构
→ 返回计算机基础
数据结构是组织和存储数据的方式，直接决定算法的时间与空间效率。选择合适的数据结构是解决问题的第一步。
复杂度速查
| 数据结构 | 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) |
| 栈/队列 | O(n) | O(n) | O(1) | O(1) |
| 哈希表 | — | O(1) 均摊 | O(1) 均摊 | O(1) 均摊 |
| 二叉搜索树（均衡） | O(log n) | O(log n) | O(log n) | O(log n) |
| 堆 | O(1) 极值 | — | O(log n) | O(log n) |
数组（Array）
连续内存存储，支持 O(1) 随机访问。
索引： 0 1 2 3 4
[10] [20] [30] [40] [50]
地址： base base+4 base+8 ...
- 优点：随机访问快，缓存友好（空间局部性）
- 缺点：插入/删除需移动元素；静态数组大小固定
- 动态数组（Java
ArrayList、Pythonlist）：扩容时分配 2 倍空间，均摊 O(1) 追加
链表（Linked List）
节点通过指针连接，不要求连续内存：
单向链表：[data|next] → [data|next] → [data|null]
双向链表：null ← [prev|data|next] ↔ [prev|data|next] → null
- 优点：已知节点位置时插入/删除 O(1)，无需预分配大小
- 缺点：随机访问 O(n)，额外指针开销，缓存不友好
栈（Stack）
LIFO（后进先出），只在栈顶操作：
push(x) → 压栈 pop() → 弹栈 peek() → 查看栈顶
应用：函数调用栈、括号匹配、表达式求值、DFS、浏览器后退。
队列（Queue）
FIFO（先进先出），队尾入队，队头出队：
| 变种 | 说明 |
|---|---|
| 双端队列（Deque） | 两端均可入队/出队 |
| 优先队列 | 按优先级出队，通常用堆实现 |
| 循环队列 | 数组实现，避免假溢出 |
应用：BFS、任务调度、消息队列、滑动窗口。
哈希表（Hash Table）
通过哈希函数将键映射到数组索引，实现 O(1) 均摊查找：
key → hash(key) % capacity → 数组槽位 → value
哈希冲突解决：
| 方法 | 说明 |
|---|---|
| 链式法（Chaining） | 每个槽位存链表，冲突元素追加到链表 |
| 开放寻址（Open Addressing） | 冲突时探测其他槽位（线性/二次/双散列） |
负载因子 = 元素数 / 数组容量，超过阈值（通常 0.75）触发扩容重哈希。
树（Tree）
二叉搜索树（BST）
左子树所有节点 < 根 < 右子树所有节点，中序遍历得到有序序列。有序插入会退化为链表，查找退化到 O(n)，需平衡。
平衡 BST
| 类型 | 说明 | 特点 |
|---|---|---|
| AVL 树 | 严格平衡（左右子树高度差 ≤ 1） | 查找快，旋转多 |
| 红黑树 | 近似平衡（黑高相等） | 插入/删除旋转少，Java TreeMap 使用 |
| B/B+ 树 | 多路平衡，减少磁盘 IO | 数据库索引（MySQL InnoDB） |
堆（Heap）
完全二叉树，用数组存储（节点 i 的左子为 2i+1，右子为 2i+2）：
- 最大堆：父节点 ≥ 子节点，堆顶为最大值
- 最小堆：父节点 ≤ 子节点，堆顶为最小值
应用：堆排序、优先队列、Top-K 问题、Dijkstra 算法。
图（Graph）
由顶点（Vertex）和边（Edge）组成，表示实体间关系。
存储方式：
| 方式 | 适用 | 空间 |
|---|---|---|
| 邻接矩阵 | 稠密图、快速判断两点是否相邻 | O(V²) |
| 邻接表 | 稀疏图、遍历邻居 | O(V+E) |
遍历：
- BFS：借助队列，适合最短路径（无权图）
- DFS：借助栈/递归，适合连通性、拓扑排序
跳表（Skip List）
在有序链表上建立多层索引，实现 O(log n) 查找：
Level 3: 1 ─────────────────── 9
Level 2: 1 ──────── 5 ──────── 9
Level 1: 1 ── 3 ── 5 ── 7 ── 9
Redis 的有序集合（ZSet）底层使用跳表实现。