数据为什么需要组织
复习
- 调度：操作系统要挑选下一个进程
- 缓存：要在内存里保留常用数据，并挑选淘汰哪一块
- 路由：路由器要为数据包挑选下一条路径
TL;DR
- 同一批数据，组织方式不同，各种操作的代价也不同
- 数据结构研究的，就是“怎样摆放数据，让常用操作更省力”
- 选择哪种结构，取决于你主要做哪些操作
- 组织数据本身也有代价，没有免费的好处
正文
我们从计算机组成一路走到网络，中间反复遇到“挑选”这两个字：操作系统要挑下一个运行的进程，缓存要挑淘汰哪一块数据，路由器要挑下一条路径。
这些问题的外壳各不相同，内核却很像：给定一批数据，怎样摆放、怎样查找，才能让事情又快又省力？
从这一章开始，我们就来正面回答它。
一个真实的小麻烦
先别急着谈术语，看一个日常场景。
假设你手里有一张写满名字的名单，要找其中某个人在不在。如果名字是随便写的，你只能从头一个一个看过去，运气不好就要看完整张名单。
但如果这张名单事先按姓氏排好了序，你就能翻到中间，比较一下，立刻扔掉一半，再看剩下那一半的中间，再扔一半……找起来快得多。
数据还是那批数据，仅仅因为摆放方式不同，查找的速度就天差地别。 这就是“组织数据”的威力。
常见操作有哪些
我们关心的，通常不只是“查找”一种动作。一个数据集上，常见的操作至少有：
- 查找：某个元素在不在、在哪里
- 插入：加入一个新元素
- 删除：移走一个元素
- 遍历：把元素挨个访问一遍
组织方式的选择，本质上就是在这些操作之间做取舍。按名字排好序的名单查找很快，但你想“插入一个新名字”时，就得知该把它放哪儿、还得挪动后面的位置，反而更麻烦。
几乎不存在一种结构，能让所有操作都最快。 有的结构查得快、改得慢，有的结构改得快、查得慢。选谁，取决于你最常做的是哪件事。
结构本身也有代价
还要记住一点：把数据组织起来，不是免费的。
排序要花时间，额外维护索引要占空间。如果一个程序几乎不怎么查找，只是不停地往末尾追加数据，那费劲去维护一个“有序结构”可能是得不偿失的。
所以，数据结构的学问，从来不是“哪种结构最好”，而是“在这种使用场景下，哪种组织方式最划算”。
说到这里，一个新问题冒了出来：我们一直说“快”“慢”，可到底该怎样衡量？总不能每次都不一样、每次都换台电脑再测一遍吧。下一章，我们先解决“怎样比较”这件事。
思考题 1
为什么“按名字排好序的名单”查找快，但插入一个新名字反而更麻烦？
思考题 2
如果一个程序基本只做“不断追加新数据、很少查找”，还有必要维护一个有序结构吗？
小结
知识点
- 数据的组织方式决定各种操作的代价
- 常见操作：查找、插入、删除、遍历
- 不同结构在不同操作上各有优劣
- 组织数据本身也有时间与空间代价
参考资料
- Wikipedia(zh)：数据结构：数据在计算机中的组织方式
- Wikipedia(zh)：算法：解决问题的清晰步骤序列
思考题答案（仅供参考）
思考题 1
因为有序带来的是“可以快速定位”。查找时能借助顺序不断缩小范围，所以快；但插入时必须先找到正确位置，还要把后面元素依次挪开，才能保持有序，因此更麻烦。有序是一种“用插入成本换查找成本”的取舍。
思考题 2
通常没必要，甚至可能是负担。维护有序结构要在每次插入时付出额外代价，而如果几乎不查找，这份代价换不来收益。此时更简单的结构（比如直接追加）反而更合适。选择结构要看你真正频繁做的是哪种操作。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪