00. 从 0 开始理解数据结构

0. 本章先解决什么问题

数据结构解决的不是“怎么刷题”,而是一个更基础的问题:

信息应该怎么放,才能让后续查找、插入、删除、更新、遍历更合适?

同样一批数据,可以有很多放法:

连续放成数组
用指针串成链表
按 key 分到桶里
按大小关系放成树
按优先级放成堆
按关系连成图
压成一串 bit

放法不同,成本就不同。你以后遇到的很多问题,本质上都是数据结构问题:

• 查找太慢。
• 插入和删除太频繁。
• 需要按顺序遍历。
• 需要快速判断是否存在。
• 需要找最小/最大任务。
• 需要表示依赖关系。
• 需要节省内存。
• 需要维护有序索引。

本章先建立数据结构的通用思维框架。

先看选结构的入口:不要先背名字,先把需求里的操作和约束列出来。

这张图怎么读

先从需求里的操作出发,而不是从结构名字出发:如果频繁按下标访问,数组类结构自然占优;如果频繁按 key 查找,哈希结构进入候选;如果要保持有序和范围查询,树、跳表或堆才有意义。图中每条分支都在提醒一件事:数据结构是对操作成本、内存布局、顺序约束和更新代价的组合选择。

1. 数据结构到底是什么

数据结构是数据的组织方式。

它至少包含三件事:

例如一组用户 ID:

没有“万能数据结构”。只有“适合某组操作和约束”的结构。

2. 数据结构的第一性问题:操作是什么

选结构前,先列操作,不要先背名字。

常见操作:

数据结构选型就是在这些操作之间做 trade-off。

手推:操作比例一变,最优结构就会变

假设有 100000 个元素,需求只有两个操作:

insert(x)
contains(x)

方案 A 用无序动态数组:

• insert:追加到尾部,约 1 次写入
• contains:从头扫到尾,平均约 50000 次比较

方案 B 用哈希索引:

• insert:计算哈希、定位桶、处理冲突
• contains:计算哈希、定位桶、少量比较

如果一天里只有 100 次查询、100000 次追加,方案 A 的追加简单、内存连续,可能很舒服。粗略估计:

查询比较量约 100 * 50000 = 5000000
追加成本约 100000 次连续写入

如果一天里有 1000000 次查询、100 次追加,方案 A 会变成灾难:

查询比较量约 1000000 * 50000 = 50000000000

此时即使哈希索引每次有常数开销,也会明显更合适。

再加一个新需求:

range(min, max)

哈希索引又不擅长范围扫描,可能要引入有序结构。这个小推导说明:数据结构没有脱离操作比例的“绝对正确”。需求里最频繁、最贵、最不能慢的操作,决定了主结构。

3. 成本不只是时间复杂度

复杂度很重要,但实际系统还要看:

例如数组和链表:

所以不能只背一句“链表插入 O(1)”。如果你还没定位到插入位置,查找成本仍然可能是 O(n)。

4. 内存布局决定很多真实性能

组成原理告诉我们:CPU 访问连续内存通常更快。

数组:

[a0][a1][a2][a3][a4]

链表:

node1 -> node2 -> node3

数组顺序遍历时,访问 a0 可能把附近元素一起带进 Cache。链表每个节点可能在不同位置,每次跳转都可能 cache miss。

这解释了:

理论复杂度一样,实际性能可能不同。

数据结构不是只存在于数学模型里,它最终落在内存、缓存和指针上。

5. 抽象接口和底层结构要分开

同一个抽象接口,可以用不同底层结构实现。

例如“队列”抽象要求:

尾部加入
头部取出
先进先出

底层可以用:

• 环形数组。
• 链表。
• 两个栈。
• 多段缓冲。

再比如“集合”抽象要求:

插入元素
删除元素
判断是否存在

底层可以用:

• 哈希表。
• 平衡树。
• 位图。
• 布隆过滤器。

学习时要分清:

接口回答“能做什么”。
实现回答“怎么做、成本是多少”。

反例:接口一样,底层语义可能完全不同

“集合”这个接口看起来很简单:插入、删除、判断存在。但底层实现不同,语义和成本会立刻分叉。

如果需求只写“需要一个集合”,还远远不够。你必须继续追问:

是否需要顺序?
是否允许误判?
key 的范围是否有限?
是否要范围查询?
是否在乎单次延迟尖刺?

这就是数据结构学习里最重要的习惯:不要被接口名骗过。接口描述能力,底层结构决定成本、顺序、边界和失败方式。

6. 结构不变量

每种数据结构都有不变量。

不变量是结构必须始终满足的条件。

插入、删除、更新的关键是:

操作完成后,不变量仍然成立。

很多 bug 就来自“不变量被破坏”:

• 链表断链。
• 树旋转后父子关系错。
• 哈希表扩容后 key 找不到。
• 堆删除后堆序没恢复。
• 图边删除了,邻接关系没同步。

7. 数据结构和算法的关系

算法描述步骤,数据结构决定步骤的基础成本。

例如最短路算法需要频繁拿到当前距离最小的节点:

如果用普通数组找最小
-> 每次 O(n)

如果用优先队列
-> 每次接近 O(log n)

再比如字符串匹配:

朴素逐位比较
-> 可能反复回退

利用前缀信息
-> 避免重复比较

算法和数据结构通常一起设计。不要把它们分成两门互不相关的知识。

8. 常见退化和失败场景

数据结构不是永远按平均情况运行。

实用学习必须问:

什么时候它会不好用?

知道失效场景,比只知道优点更重要。

失败指纹:选错结构后系统会怎么报警

数据结构选错时,表面症状常常不像“数据结构问题”。它可能伪装成性能抖动、内存上涨、偶发超时或结果错乱。

排查这类问题时,不要只看“大 O”。更有效的做法是把每个操作的真实路径画出来:

一次查询访问哪些结构?
一次更新要改哪些结构?
哪一步可能触发批量维护?
哪份数据是真源,哪份只是索引?

能回答这些问题,才算真正理解了当前结构。

9. 联系实际:如何面对一个真实需求

假设需求是:

维护一批任务,支持新增任务、取消任务、按优先级取下一个任务、按 id 查询任务状态。

一个结构可能不够。

你可能需要:

• 优先队列:快速取最高优先级任务。
• 映射表:按 id 找任务。
• 状态字段:标记取消或完成。
• 延迟删除:堆里旧任务弹出时再判断是否有效。

这说明真实系统常常是多个数据结构组合,而不是“选一个结构结束”。

分析步骤:

1. 列操作。
2. 标出每个操作频率。
3. 标出是否需要有序、范围、最值、关系。
4. 标出内存和误判约束。
5. 选择一个或多个结构组合。
6. 写清楚不变量和退化场景。

设计卡:从需求反推数据结构

给任何需求选结构前,先填这张表:

练习:同样是“保存一批任务”,分别要求“按提交顺序处理”“随时取优先级最高”“按 ID 快速查找”“按依赖关系执行”。你会发现需求一变,正确结构也会变。

10. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 数据结构到底解决什么问题?
2. 为什么没有万能数据结构?
3. 选结构前为什么要先列操作和频率?
4. 为什么复杂度之外还要看内存布局、缓存、扩容、退化?
5. 抽象接口和底层实现有什么区别?
6. 什么是不变量,为什么它是数据结构正确性的核心?
7. 为什么真实系统常常组合多个数据结构?

后续章节会逐个拆解常见结构:它怎么存、怎么找、怎么改、哪里快、哪里会坏、适合什么实际问题。

延伸阅读

• README · CS_FOUR
• Java刷题API与算法模板
• Java集合关系图