东西放在哪里，决定了一切
想象两个厨房。第一个里，每一种香料都按字母顺序立在贴了标签的架子上。第二个里，所有香料一股脑倒进一个大抽屉。两边*装的*是同样的香料——可在一个厨房里拿孜然只需瞄一眼，在另一个里却得烦躁地翻找。香料就是你的数据。架子还是抽屉的这个选择，就是你的[[data-structure|数据结构]]：你安排信息、以便处理它的方式。
这是上一篇的搭档观念。算法是那些步骤；数据结构则是这些步骤运行时，*数据所栖身的形状*。而形状关系重大：一本按姓名排序的电话簿能让你几秒钟找到一个人，可如果你手上只有*号码*、想反查姓名，那同一本按姓名排序的簿子就几乎没用了。不存在唯一最好的结构——只有最适合你最常问的那些问题的结构。
承诺与机器（抽象数据类型与实现）
这里藏着一个有用的区分。一边是*承诺*：「你可以加入一项、移除一项，还能问一共有多少项。」这份操作清单连同它们的含义——只字不提内部是怎么搭的——就叫[[abstract-data-type|抽象数据类型]]（ADT）。另一边是*机器*：内存里真正兑现这份承诺的螺丝与齿轮。那就是实现。
想象一台自动售货机。承诺很简单：按下编号、投币、零食掉出来。它*怎么*做到的——螺旋货道、传感器、一个小马达——都藏在玻璃后面，而你并不在乎，只要零食出来就行。ADT 就是机器的正面；实现就是玻璃后面的一切。同一个承诺（一份「东西的清单」）可以由很不一样的机器来兑现（一个数组，或一串链起来的小盒子），各有各的代价。
你最先遇到的三种：数组、列表、映射
今天你不必把它们全学会——只是先看一眼，好让这些名字日后显得熟悉。[[dsa-array|数组]]是一排编号为 0、1、2…… 的格子；直接跳到第 5 格，值就*在那里*，瞬间到手。列表是一串链起来的项，容易增长和重排，但你得一节一节地走过去。映射（也叫字典）存的是*键 → 值*的成对关系，就像一个单词连着它的释义，于是你按名字、而非按位置去查找。
array: [ A | B | C | D | E ] jump to index 3 -> D (instant)
0 1 2 3 4
list: A -> B -> C -> D -> E walk from A to reach D (4 steps)
map: "cat" -> 9 look up by the key "cat", not a number
"dog" -> 4
"fox" -> 7这几种之后都会各有一篇导读。眼下要带走的，是道理而非细节：你选的结构，决定了哪些操作便宜、哪些操作昂贵。选得好，就完成了写出快程序的一半——而要*度量*便宜与昂贵，我们需要下一篇所讲的那套语言。