13 - 遇到问题该选哪种数据结构
最后一章，我们不学新东西，而是把前面所有数据结构收进一张「决策地图」。这一章的目标很实在：下次遇到一个实际问题，你脑子里能立刻浮现出「这该用哪个」。 这正是第 01 章说的「选型思维」，也是这整篇教程的落点。
先回到那个核心问题
选数据结构，永远从这一句开始问：
「我最频繁做的是什么操作？我最怕哪个操作慢？」
想清楚这个，答案基本就出来了。下面这张表，就是按「你想干什么」来倒查该用什么。
按需求查结构（决策速查表）
| 你想干的事 | 首选结构 | 为什么 |
|---|---|---|
| 按位置/下标快速读取，数据量稳定 | 数组 | 按下标 O(1) 一步到位 |
| 频繁在中间插入/删除 | 链表 | 改指针即可，不用挪动大批数据 |
| 根据唯一标识（键）秒查对应值 | 哈希表 | O(1) 查找，最快 |
| 判断某个东西”见过没” / 去重 | 哈希表 | 存进去，查在不在，都是 O(1) |
| 统计次数 / 建立映射关系 | 哈希表 | 键→值天然契合 |
| 最近做的要最先撤销 / 处理嵌套 | 栈 | 后进先出 |
| 按到达顺序公平处理任务 | 队列 | 先进先出 |
| 反复取出”当前最大/最小” | 堆 | 取最值 O(1)，插入 O(log n) |
| 要有序，还要范围查询/找最值 | 平衡树 | O(log n) 且天然有序 |
| 海量数据存硬盘、做索引 | B+ 树 | 矮胖多叉，少读硬盘 |
| 表达层级/归属关系 | 树 | 天生的层级模型 |
| 表达”谁和谁有关系”的网状结构 | 图 | 顶点+边，最灵活 |
| 找最短路径/最少步数 | 图 + BFS | 一圈圈扩，先到即最短 |
| 探索所有可能/连通性/依赖顺序 | 图 + DFS | 一条路走到黑再回头 |
几个「一句话触发词」
面试或实战中，听到这些词，脑子里该立刻蹦出对应结构：
- 听到「秒查、去重、缓存、键值、统计次数」→ 哈希表
- 听到「撤销、括号匹配、函数调用、后开先关」→ 栈
- 听到「排队、按顺序、缓冲、先来先服务」→ 队列
- 听到「Top K、优先级、每次取最值、定时任务」→ 堆
- 听到「有序、范围查询、数据库索引」→ 平衡树 / B+ 树
- 听到「层级、目录、组织架构、DOM」→ 树
- 听到「关系、网络、路径、好友推荐、导航、依赖」→ 图
别忘了它们之间是有联系的
这篇教程一路走来，你应该感受到：这些数据结构不是孤立的，而是层层递进、互相支撑的：
- 数组和链表是最底层的两块砖，栈、队列、哈希表、树都建立在它们之上。
- 栈和队列看似简单，却是**图遍历（DFS/BFS）**的引擎。
- 二叉搜索树为了不长歪进化出平衡树，为了适配硬盘进化出 B+ 树。
- 堆填了优先级队列的坑。
- 树放宽限制（允许环、多连接）就成了图。
- 而「缓存 / 分层 / 局部性」这些思想，又和你在组成原理、操作系统篇学的一脉相承。
记住：数据结构的世界，是一张互相关联的网，不是一堆孤立的名词。理解了「谁为解决谁的问题而生」，你就不用死记，而是能推导出来。
最后给你的建议
- 别急着刷题。先把这 13 章的「每种结构擅长什么、代价是什么」真正想透，遇到问题能选对工具，比会背 100 道题的模板更有用。
- 动手时用现成的。实际写代码时，哈希表用语言自带的字典、有序结构用自带的 TreeMap/set，你几乎不用自己从零实现——理解原理是为了会选、会判断性能，而不是重复造轮子。
- 等你真要刷题时，回头再看这篇，你会发现每道题的第一步——「这题该用什么数据结构」——已经难不倒你了。
恭喜你学完了
回顾这一路：
- 开篇：数据结构是组织数据的方式，选型看操作（01）；大 O 衡量快慢（02）。
- 线性结构：数组 vs 链表（03）、栈（04）、队列（05）、哈希表（06）。
- 树形结构：树（07）、二叉搜索树（08）、平衡树与 B+ 树（09）、堆（10）。
- 图结构：图（11）、存储与遍历 BFS/DFS（12）。
如果你还没看过 计算机操作系统原理 和 计算机组成原理，推荐一并看完——三篇合起来，你的计算机基础认知地图就完整了。
回到 README 目录 ｜ 回到 总目录