数据结构入门：从数组到图
数据结构是算法的根基。选对数据结构，问题就解决了一半。
一、为什么要学数据结构？
程序 = 数据结构 + 算法
—— 图灵奖得主 Niklaus Wirth
数据结构决定了数据的组织方式，进而影响操作的效率。
例如：
- 频繁查找 → 哈希表（O(1)）
- 频繁插入 → 链表（O(1)）
- 排序查询 → 树（O(log n)）
二、八大基础数据结构
1. 数组（Array）
连续内存，下标访问 O(1)。
┌──┬──┬──┬──┬──┐
│10│20│30│40│50│
└──┴──┴──┴──┴──┘
0 1 2 3 4- ✅ 随机访问快
- ❌ 插入删除慢（要移动元素）
- ❌ 大小固定
2. 链表（Linked List）
非连续内存，指针连接。
单链表：
┌──┬─┐ ┌──┬─┐ ┌──┬──┐
│10│ ┼──► │20│ ┼──► │30│ ∅ │
└──┴─┘ └──┴─┘ └──┴──┘
双链表：
┌──┬──┐ ┌──┬──┐ ┌──┬──┐
◄─┤10│ ┼──► ◄─┤20│ ┼──► ◄─┤30│ ∅
└──┴──┘ └──┴──┘ └──┴──┘- ✅ 插入删除快
- ✅ 大小动态
- ❌ 不能随机访问
经典题：反转链表、检测环、合并有序链表
3. 栈（Stack）
后进先出（LIFO）。
push ← ┌───┐
│ 3 │ ← top
├───┤
│ 2 │
├───┤
│ 1 │
└───┘
pop ←应用：
- 函数调用栈
- 括号匹配
- 表达式求值
- 浏览器前进后退
4. 队列（Queue）
先进先出（FIFO）。
enqueue → ┌─┬─┬─┬─┬─┐ → dequeue
│1│2│3│4│5│
└─┴─┴─┴─┴─┘
tail head变种：
- 双端队列：两端都可进出
- 优先队列：按优先级出队（堆实现）
- 循环队列：固定大小，环形复用
应用：BFS、任务调度、消息队列
5. 树（Tree）
层次结构，n 个节点的有限集。
二叉树：
1
/ \
2 3
/ \ \
4 5 6特殊二叉树：
- 满二叉树：所有层都满
- 完全二叉树：除最后一层，都满且靠左
- 二叉搜索树（BST）：左 < 根 < 右
- 平衡二叉树（AVL）：左右高度差 ≤ 1
- 红黑树：近似平衡，操作 O(log n)
遍历方式：
- 前序：根 → 左 → 右
- 中序：左 → 根 → 右（BST 得到升序）
- 后序：左 → 右 → 根
- 层序：逐层（BFS）
6. 图（Graph）
由顶点和边组成的结构。
无向图：
A ─── B
│ │
C ─── D ─── E
有向图：
A ──► B
▲ │
│ ▼
C ◄── D存储方式：
- 邻接矩阵：二维数组，O(V²)
- 邻接表：链表数组，O(V+E)
遍历：
- DFS（深度优先）：递归或栈
- BFS（广度优先）：队列
应用：社交网络、地图导航、依赖管理
7. 哈希表（Hash Table）
通过哈希函数把 key 映射到下标，平均 O(1) 查找。
hash("小宇宙") = 5
┌─┬─┬─┬─┬─┬─────────┐
│ │ │ │ │ │ 小宇宙 │
└─┴─┴─┴─┴─┴─────────┘
0 1 2 3 4 5冲突解决：
- 开放寻址：找下一个空位
- 链地址：每个桶存链表
应用：缓存、字典、去重
8. 堆（Heap）
完全二叉树，分为大顶堆和小顶堆。
大顶堆：
9
/ \
8 7
/ \ / \
3 5 2 6- 父节点 ≥（或 ≤）子节点
- 插入/删除：O(log n)
- 取最值：O(1)
应用：优先队列、Top K、堆排序、定时器
三、复杂度对比
| 数据结构 | 查找 | 插入 | 删除 | 空间 |
| ---- | ---- | ---- | ---- | ---- |
| 数组 | O(n) | O(n) | O(n) | O(n) |
| 有序数组 | O(log n) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) | O(n) |
| 哈希表 | O(1) | O(1) | O(1) | O(n) |
| BST（平衡） | O(log n) | O(log n) | O(log n) | O(n) |
| 堆 | O(n) | O(log n) | O(log n) | O(n) |
四、如何选型？
灵魂三问：
- 主要操作是什么？ 查找 / 插入 / 删除 / 范围查询
- 数据规模多大？ 内存 / 磁盘
- 是否需要有序？ 是 → 树；否 → 哈希
常见场景对应：
| 场景 | 推荐 |
| ---- | ---- |
| 缓存 | 哈希表 |
| 排行榜 | 堆 / 跳表 |
| 撤销操作 | 栈 |
| 任务调度 | 队列 |
| 关系网络 | 图 |
| 文件系统 | 树（B+ 树） |
五、LeetCode 经典题
数组/链表
- 两数之和
- 反转链表
- 环形链表
- 合并有序数组
栈/队列
- 有效的括号
- 用栈实现队列
- 滑动窗口最大值
树
- 二叉树的最大深度
- 验证 BST
- 二叉树的层序遍历
图
- 岛屿数量
- 课程表
- 网络延迟时间
六、小结
| 数据结构 | 核心 | 应用 |
| ---- | ---- | ---- |
| 数组 | 连续 | 随机访问 |
| 链表 | 指针 | 频繁增删 |
| 栈 | LIFO | 调用栈、回溯 |
| 队列 | FIFO | BFS、调度 |
| 树 | 层次 | 索引、文件系统 |
| 图 | 关系 | 网络、依赖 |
| 哈希表 | 映射 | 缓存、字典 |
| 堆 | 最值 | Top K、排序 |
小宇宙寄语：数据结构是程序员的基本功，刷 LeetCode 不是目的，理解每种结构的思想才是关键。