数据结构
🎯 核心问题
如何高效地组织和存储数据？ 你可能遇到过这样的困惑：为什么有些程序处理几万条数据很快，有些处理几百条就卡住了？答案往往在于数据结构的选择。本章带你理解常见数据结构的特点和适用场景。
0. 全景图：数据结构是什么？
想象你要整理一堆书：
- 堆在地上：找书要一本本翻（链表）
- 按编号放书架：直接去对应位置拿（数组）
- 按类别分柜子：先找柜子再找书（哈希表）
- 按书名排序：二分查找，每次排除一半（树）
不同的整理方式，找书的效率天差地别。数据结构就是数据的"整理方式"。
| 操作 | 数组 | 链表 | 哈希表 | 树 |
|---|---|---|---|---|
| 访问 | O(1) | O(n) | O(1) | O(log n) |
| 查找 | O(n) | O(n) | O(1) | O(log n) |
| 插入 | O(n) | O(1) | O(1) | O(log n) |
| 删除 | O(n) | O(1) | O(1) | O(log n) |
常见数据结构分类：
| 类型 | 特点 | 典型代表 | 适用场景 |
|---|---|---|---|
| 线性结构 | 数据排成一排 | 数组、链表、栈、队列 | 顺序处理、历史记录 |
| 哈希结构 | 键值对映射 | 哈希表 | 快速查找、缓存 |
| 树形结构 | 层次关系 | 二叉树、B树 | 排序、搜索、文件系统 |
| 图结构 | 网状关系 | 有向图、无向图 | 社交网络、路径规划 |
📊 逐行解读这张表
线性结构：最简单的数据组织方式，数据一个接一个排列。数组适合随机访问，链表适合频繁插入删除。
哈希结构：用"键"直接找到"值"，查找速度最快。但需要处理"冲突"问题（两个键映射到同一位置）。
树形结构：有层次关系的数据。二叉搜索树适合排序和搜索，B树适合磁盘存储（数据库索引）。
图结构：最复杂的结构，表示任意的关系网络。社交网络、地图导航都用图来建模。
1. 线性结构：最基础的组织方式
1.1 数组：连续存储
💡 数组的特点
数组是一块连续的内存空间，每个元素大小相同。
优点：
- 随机访问快：
arr[100]直接计算地址，O(1) - 缓存友好：连续存储，CPU 缓存命中率高
缺点：
- 插入删除慢：需要移动后面所有元素，O(n)
- 大小固定：需要预先分配空间
生活类比：一排编号的储物柜，每个柜子大小相同。找第 10 号柜子直接去，但要在中间插入一个柜子，后面的都要往后挪。
1.2 链表：节点相连
💡 链表的特点
链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
优点：
- 插入删除快：只需修改指针，O(1)
- 大小灵活：可以动态增长
缺点：
- 访问慢：要从头开始遍历，O(n)
- 额外空间：每个节点需要存储指针
生活类比：寻宝游戏，每个线索指向下一个地点。要找第 10 个线索，必须从第 1 个开始一步步找。
1.3 栈和队列：受限的线性结构
| 结构 | 规则 | 操作 | 类比 | 应用 |
|---|---|---|---|---|
| 栈 | 后进先出 (LIFO) | push/pop | 一摞盘子 | 函数调用、撤销操作 |
| 队列 | 先进先出 (FIFO) | enqueue/dequeue | 排队买票 | 任务调度、消息队列 |
💡 为什么要有"受限"的结构？
栈和队列看起来比数组、链表功能少，但正是这种"限制"让它们有明确的用途：
- 栈：函数调用时，最后调用的函数最先返回
- 队列：任务调度时，先来的任务先处理
限制带来简洁，简洁带来高效。
2. 哈希表：最快的查找
2.1 哈希表原理
💡 哈希表如何工作？
哈希表通过"哈希函数"把键映射到数组索引。
工作流程：
- 输入键（如 "apple"）
- 哈希函数计算：
hash("apple") = 3 - 直接去数组索引 3 的位置找
冲突处理：
- 两个不同的键可能映射到同一索引
- 解决方法：链地址法（同一位置用链表存储多个值）
生活类比：图书馆按书名首字母分柜子。"Apple" 开头的书都放 A 柜，"Banana" 开头的放 B 柜。找书时先确定柜子，再在柜子里找。
2.2 哈希表的时间复杂度
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
⚠️ 什么时候会退化？
当所有键都映射到同一个索引时，哈希表退化为链表，所有操作变成 O(n)。
避免方法：
- 选择好的哈希函数
- 动态扩容（负载因子超过阈值时扩容）
3. 树：层次结构
3.1 二叉搜索树
💡 二叉搜索树的规则
二叉搜索树是一种特殊的二叉树：
- 左子树的所有值 < 根节点
- 右子树的所有值 > 根节点
查找过程：
- 从根节点开始
- 如果目标值 < 当前值，往左走
- 如果目标值 > 当前值，往右走
- 每次比较排除一半节点
时间复杂度：O(log n)，但最坏情况（变成链表）是 O(n)
3.2 平衡树
为了防止二叉搜索树退化，引入了平衡树：
| 类型 | 平衡方式 | 特点 |
|---|---|---|
| AVL 树 | 严格平衡（高度差 ≤ 1） | 查找最快，插入删除稍慢 |
| 红黑树 | 近似平衡 | 综合性能好，应用最广 |
| B 树 | 多路平衡 | 适合磁盘存储，数据库索引 |
4. 如何选择数据结构？
| 需求 | 推荐结构 | 原因 |
|---|---|---|
| 快速随机访问 | 数组 | O(1) 索引访问 |
| 频繁插入删除 | 链表 | O(1) 插入删除 |
| 快速查找 | 哈希表 | O(1) 平均查找 |
| 有序数据 | 平衡树 | O(log n) 查找，保持有序 |
| 最近使用 | 栈 | LIFO 特性 |
| 任务排队 | 队列 | FIFO 特性 |
💡 选择数据结构的心法
没有最好的数据结构，只有最合适的数据结构。
选择时要考虑：
- 主要操作是什么？ 查找？插入？删除？
- 数据量多大？ 小数据量差别不大，大数据量要慎重
- 数据有序吗？ 有序数据可以用二分查找
- 内存限制？ 某些结构需要额外空间
5. 总结：数据结构是程序的基础
让我们用一个比喻总结各种数据结构：
| 结构 | 比喻 | 核心特点 |
|---|---|---|
| 数组 | 编号储物柜 | 访问快，插入慢 |
| 链表 | 寻宝线索 | 插入快，访问慢 |
| 栈 | 一摞盘子 | 后进先出 |
| 队列 | 排队队伍 | 先进先出 |
| 哈希表 | 分类柜子 | 查找最快 |
| 树 | 家族族谱 | 层次结构 |
💡 核心启示
数据结构决定了程序的效率上限。
- 选对数据结构，问题迎刃而解
- 选错数据结构，再好的算法也无济于事
理解数据结构，就是理解"如何高效地组织数据"。这是每个程序员的基本功。
延伸阅读
- 数据结构实现：自己动手实现各种数据结构，加深理解
- 高级数据结构：学习跳表、布隆过滤器、并查集等
- 数据库索引：了解 B+ 树在数据库中的应用
- 缓存设计：学习 LRU 缓存如何结合哈希表和链表