数据结构
前言
程序 = 数据结构 + 算法。 前面我们学了 CPU 如何执行指令、操作系统如何管理资源。但程序要处理的核心对象是数据——用户信息、商品列表、社交关系……这些数据怎么在内存里组织，直接决定了程序的快慢。你可能遇到过这样的困惑：为什么有些程序处理几万条数据很快，有些处理几百条就卡住了？答案往往就在于数据结构的选择。
这篇文章会带你学什么？
学完这章后，你将获得：
- 直觉判断力：看到一个需求，脑子里自动浮现该用什么数据结构
- 性能分析视角：能判断性能瓶颈是数据结构选错了，还是算法效率低
- 权衡思维：理解"空间换时间"与"时间换空间"，知道没有完美的数据结构
- 代码阅读能力：看到 HashMap、Stack、Queue 这些词不再陌生
- 后续学习基础：为数据库索引、缓存系统、搜索引擎等技术打下基础
| 章节 | 内容 | 核心概念 |
|---|---|---|
| 第 1 章 | 全景图 | 四大类数据结构、分类标准 |
| 第 2 章 | 线性结构 | 数组、链表、栈、队列 |
| 第 3 章 | 哈希表 | 哈希函数、冲突处理、O(1) 查找 |
| 第 4 章 | 树形结构 | 二叉树、文件系统树、DOM 树 |
| 第 5 章 | 图结构 | 有向图、无向图、遍历算法 |
| 第 6 章 | 性能对比 | 时间复杂度、空间复杂度 |
| 第 7 章 | 选型指南 | 场景分析、决策流程 |
1. 全景图：数据结构是什么？
想象你要整理一堆书：
- 堆在地上：找书要一本本翻——这就是最原始的存储
- 按编号放书架：直接去对应位置拿——这就是数组
- 按类别分柜子：先确定柜子再找书——这就是哈希表
- 按书名排序放多层架：每次排除一半——这就是树
不同的整理方式，找书的效率天差地别。数据结构就是数据的"整理方式"——它决定了数据怎么存、怎么找、怎么改。
所有数据结构可以归为四大类：
| 类型 | 数据关系 | 典型代表 | 生活类比 |
|---|---|---|---|
| 线性结构 | 一对一，排成一排 | 数组、链表、栈、队列 | 火车车厢、排队队伍 |
| 哈希结构 | 键→值映射 | 哈希表、字典、集合 | 图书馆索引卡片 |
| 树形结构 | 一对多，层级关系 | 二叉树、B树、堆 | 家族族谱、文件夹 |
| 图结构 | 多对多，网状关系 | 有向图、无向图 | 地铁线路图、社交网络 |
为什么要学这么多种？
因为没有万能的数据结构。每种结构都是在"查找速度"、"插入速度"、"内存占用"之间做权衡。就像你不会用书包装家具，也不会用卡车送一封信——选对工具，事半功倍。
2. 线性结构：最基础的组织方式
线性结构是最直觉的数据组织方式——数据一个接一个排列，就像火车车厢。但"怎么连接"和"从哪端操作"的不同，产生了四种变体，各有各的绝活。
| 数据结构 | 访问 | 插入 | 删除 | 特点 |
|---|---|---|---|---|
| 📊 数组 | O(1) 快 | O(n) 慢 | O(n) 慢 | 大小固定 |
| 🔗 链表 | O(n) 慢 | O(1) 快 | O(1) 快 | 大小可变 |
| 🥞 栈 | O(n) | O(1) 快 | O(1) 快 | 一端操作 |
| 🚶 队列 | O(n) | O(1) 快 | O(1) 快 | 两端操作 |
2.1 数组 vs 链表：两种截然不同的存储方式
数组和链表是最基础的两种线性结构，它们的核心区别在于内存布局：
| 对比维度 | 数组 | 链表 |
|---|---|---|
| 内存布局 | 连续的一整块 | 散落在各处，用指针串起来 |
| 访问第 n 个 | 直接算地址，O(1) | 从头一个个找，O(n) |
| 中间插入 | 后面的都要挪，O(n) | 改两个指针就行，O(1) |
| 大小 | 创建时就固定了 | 随时可以增长 |
| 生活类比 | 一排编号储物柜 | 寻宝游戏的线索链 |
什么时候用数组？什么时候用链表？
- 数据量已知、频繁按位置访问 → 数组（比如学生成绩表、像素矩阵）
- 数据量未知、频繁插入删除 → 链表（比如播放列表、撤销历史）
- 不确定？ → 先用数组。大多数场景下，数组的缓存友好性带来的性能优势更大
2.2 栈和队列：加了"规矩"的线性结构
栈和队列本质上就是数组或链表，只是限制了操作方式。看起来功能变少了，但正是这种限制让它们有了明确的用途：
| 结构 | 规则 | 操作 | 类比 | 你写的代码里在哪？ |
|---|---|---|---|---|
| 栈 | 后进先出 (LIFO) | push / pop | 一摞盘子 | 函数调用栈、浏览器后退、Ctrl+Z 撤销 |
| 队列 | 先进先出 (FIFO) | enqueue / dequeue | 排队买票 | 任务调度、消息队列、打印队列 |
为什么"限制"反而是好事？
想象一个只有"放盘子"和"拿盘子"两个操作的栈——你永远不会拿错顺序。限制带来确定性，确定性带来可靠性。 函数调用栈就是靠"后进先出"保证最后调用的函数最先返回，如果允许随意访问中间的函数，程序就乱套了。
3. 哈希表：最快的查找
线性结构的查找都不够快——数组要遍历 O(n)，即使排好序用二分查找也要 O(log n)。有没有一种结构能做到 O(1) 直接找到？有，就是哈希表。
3.1 哈希表的核心思想
哈希表的原理其实很简单：
- 你给一个键（比如 "apple"）
- 哈希函数把键算成一个数字（比如
hash("apple") = 3） - 直接去数组的第 3 个位置找——不用遍历，一步到位
这就像图书馆的索引系统：你不用在一排排书架上找，查索引卡片就能直接定位到书的位置。
3.2 哈希冲突：两个键撞车了怎么办？
两个不同的键可能算出同一个索引——这叫哈希冲突。就像两本书的索引号相同，都指向同一个位置。
| 解决方法 | 原理 | 类比 |
|---|---|---|
| 链地址法 | 同一位置用链表存多个值 | 同一个柜子里放多本书 |
| 开放寻址法 | 冲突了就往后找空位 | 柜子满了就放隔壁柜子 |
3.3 哈希表的性能
| 操作 | 平均情况 | 最坏情况（全部冲突） |
|---|---|---|
| 查找 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
什么时候会退化？
当所有键都映射到同一个索引时，哈希表退化为链表，所有操作变成 O(n)。避免方法：选择好的哈希函数 + 动态扩容（负载因子超过阈值时扩容）。
哈希表在你的代码里无处不在
- JavaScript 的
{}对象和Map→ 哈希表 - Python 的
dict→ 哈希表 - Java 的
HashMap→ 哈希表 - 数据库的索引 → 底层也用哈希
你每次写 user["name"] 或 map.get("key")，背后都是哈希表在工作。
4. 树形结构：层级关系的表达
哈希表查找快，但数据是无序的。如果你需要既能快速查找，又能保持数据有序，就需要树形结构了。
树的核心特征：每个节点可以有多个"孩子"，但只有一个"父亲"（根节点除外）。这种一对多的层级关系，在现实中随处可见。
4.1 二叉搜索树：有序的树
二叉搜索树有一个简单但强大的规则：左小右大。
- 左子树的所有值 < 根节点
- 右子树的所有值 > 根节点
查找时，每次比较都能排除一半节点，时间复杂度 O(log n)。就像猜数字游戏——"比 50 大还是小？""大。""比 75 大还是小？"——每次排除一半。
4.2 平衡树：防止退化
二叉搜索树有个问题：如果数据按顺序插入（1, 2, 3, 4, 5），树会退化成一条链，查找变回 O(n)。平衡树通过自动调整结构来避免这个问题：
| 类型 | 平衡策略 | 特点 | 典型应用 |
|---|---|---|---|
| AVL 树 | 严格平衡（高度差 ≤ 1） | 查找最快，插入删除稍慢 | 需要频繁查找的场景 |
| 红黑树 | 近似平衡 | 综合性能好 | Java TreeMap、Linux 内核 |
| B 树 | 多路平衡，一个节点存多个值 | 减少磁盘 I/O | 数据库索引 |
树在你的代码里在哪？
- 文件系统：文件夹嵌套就是树结构
- HTML DOM：
<html>→<body>→<div>→<p>就是一棵树 - 数据库索引：B+ 树让百万级数据的查找只需要 3-4 次磁盘读取
- JSON/XML：嵌套的数据格式本质上就是树
5. 图结构：复杂关系的网络
树只能表示"一对多"的层级关系。但现实中很多关系是"多对多"的——你的朋友也有朋友，城市之间有多条路可以走。这种任意节点之间都可能有连接的结构，就是图。
5.1 图的三种形态
| 类型 | 特点 | 类比 | 典型应用 |
|---|---|---|---|
| 无向图 | 边没有方向，A→B 等于 B→A | 微信好友（互相的） | 社交网络、通信网络 |
| 有向图 | 边有方向，A→B 不等于 B→A | 微博关注（单向的） | 网页链接、依赖关系 |
| 带权图 | 边有权重（距离、费用等） | 城市间的公路（有里程数） | 地图导航、最短路径 |
5.2 图的遍历
图的遍历比线性结构复杂，因为可能有环（A→B→C→A），需要记录"已访问"的节点：
| 遍历方式 | 策略 | 类比 | 适用场景 |
|---|---|---|---|
| BFS（广度优先） | 先访问所有邻居，再访问邻居的邻居 | 水波纹扩散 | 最短路径、层级遍历 |
| DFS（深度优先） | 一条路走到底，走不通再回头 | 走迷宫 | 路径搜索、连通性判断 |
图在现实中的应用
- 地图导航：城市是节点，道路是边，导航就是在图上找最短路径
- 社交网络：用户是节点，关注/好友是边，"你可能认识的人"就是图算法推荐的
- 包管理器：npm/pip 的依赖关系就是有向图，
npm install就是在做图的拓扑排序
6. 性能对比：一张表看清所有数据结构
学了这么多数据结构，它们的性能到底差多少？下面这个交互式对比能帮你建立直觉：
| 操作 | 数组 | 链表 | 哈希表 | 树 |
|---|---|---|---|---|
| 访问 | 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) |
核心性能对比表：
| 数据结构 | 访问 | 查找 | 插入 | 删除 | 空间 |
|---|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 栈/队列 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 哈希表 | — | O(1) | O(1) | O(1) | O(n) |
| 二叉搜索树 | — | O(log n) | O(log n) | O(log n) | O(n) |
| 图 | — | O(V+E) | O(1) | O(E) | O(V+E) |
怎么读这张表？
- O(1)：不管数据量多大，操作时间恒定——最快
- O(log n)：数据量翻倍，时间只多一步——很快
- O(n)：数据量翻倍，时间也翻倍——一般
- O(V+E)：取决于节点数和边数——图的特殊表示
注意：这些都是平均情况。最坏情况下，哈希表会退化到 O(n)，二叉搜索树也会退化到 O(n)。
7. 选型指南：该用哪种数据结构？
学了这么多数据结构，面对实际需求时该怎么选？关键是从需求出发，问自己几个问题：
- 最频繁的操作是什么？ 查找？插入？删除？遍历？
- 数据之间有什么关系？ 一对一？一对多？多对多？
- 数据量有多大？ 几十条和几百万条的最优选择可能完全不同
- 需要有序吗？ 是否需要按某种顺序遍历数据
| 场景需求 | 推荐数据结构 | 时间复杂度 |
|---|---|---|
| 随机访问 | 数组 | O(1) |
| 快速查找 | 哈希表 | O(1) |
| 有序查找 | 二叉搜索树 | O(log n) |
| 频繁插入删除 | 链表 | O(1) |
| 撤销操作 | 栈 | O(1) |
| 任务调度 | 队列 | O(1) |
快速决策流程：
| 你的需求 | 推荐结构 | 原因 |
|---|---|---|
| 按位置快速访问 | 数组 | O(1) 随机访问 |
| 频繁在中间插入删除 | 链表 | O(1) 插入删除，不用移动元素 |
| 后进先出（撤销、递归） | 栈 | LIFO 语义天然匹配 |
| 先进先出（任务队列） | 队列 | FIFO 语义天然匹配 |
| 按键快速查找 | 哈希表 | O(1) 平均查找 |
| 有序数据 + 快速查找 | 二叉搜索树 | O(log n) 查找且保持有序 |
| 复杂多对多关系 | 图 | 能表达任意节点间的连接 |
实际开发中的经验法则
- 80% 的场景用数组和哈希表就够了
- 需要有序时考虑树
- 关系复杂时考虑图
- 不确定？ 先用最简单的，遇到性能问题再换。过早优化是万恶之源
总结
数据结构是程序的骨架。数组像一排编号储物柜，按位置取东西最快；链表像寻宝线索链，插入删除最灵活；哈希表像图书馆索引，按名字找东西最快；树像家族族谱，表达层级关系且保持有序；图像地铁线路图，表达任意复杂的网状关系。没有最好的数据结构，只有最合适的——关键是理解每种结构的优势和代价，根据实际需求做出权衡。
延伸阅读
| 主题 | 推荐资源 |
|---|---|
| 数据结构可视化 | VisuAlgo - 动画演示各种数据结构和算法 |
| 算法与数据结构 | 《算法图解》- Aditya Bhargava，图文并茂适合入门 |
| 深入理解 | 《数据结构与算法分析》- Mark Allen Weiss |
| 刷题练习 | LeetCode - 按数据结构分类练习 |
下一步
现在你已经掌握了数据结构的核心知识。接下来可以继续学习：