数据结构

数据结构是一种组织数据的方式，目的是让你真正在意的那些操作变得容易。想想你在家里怎么收纳东西。写在一张纸条上的购物清单，从上往下读很方便，可要往中间插一项就糟透了。一个按字母顺序摆放瓶子的香料架，让你一把抓到牛至，却很难一直保持有序。一摞盘子让你眨眼间从顶上取走，却永远没法从底下拿。抽象地说，没有哪一种「最好」——每一种都是为了让某些动作变便宜而塑形的，代价是另一些动作变贵。

在计算里也是一样。数组让你瞬间取到第 i 个元素，却在中间插入时很慢。链表把这个取舍反了过来。哈希表让「这东西在不在？」几乎瞬间得到答案，却丢掉了任何次序感。二叉搜索树既保持有序，又仍允许快速查找。数据结构是字节的具体布局，再加上定义在其上的那组操作；它是算法的搭档，因为一个算法的速度，往往完全取决于它所运行其上的结构。

这正是为什么这门学科的两半——算法与数据结构——总是合在一起教。选对结构，常常就是「一眨眼就跑完的代码」与「慢到几乎停摆的代码」之间的分水岭。诀窍在于：先点名你最常做的那些操作，再选一种能让这些操作变便宜（往往是 O(1) 或 O(log n)）、同时让其余操作还能忍受的结构。我们用来比较它们的推理工具，就是渐近分析。