为什么要学习数据结构：从问题、表示到效率

写程序时，我们表面上在处理变量、对象和函数，实际面对的却总是同一个问题：信息该怎样组织，计算步骤该怎样安排，才能稳定地得到结果？ 数据结构回答前半句，算法回答后半句。二者合在一起，才是一套能够落地的计算方案。

这也是学习数据结构时最容易被忽略的一点。记住数组、链表、栈和树的定义并不难，难的是看到一个新需求时，能先说清数据之间的关系、系统需要支持哪些操作，再判断哪种表示最合适。结构选得不合适，代码即使能运行，也可能在数据增长后迅速变慢，或者因为边界条件太多而难以维护。

本文先搭好这条主线。我们会从“什么是计算问题”出发，逐步理解算法、正确性、效率、抽象数据类型与存储表示之间的关系。读完以后，你应该能回答一个更实用的问题：面对一组数据和一批操作，为什么要选择某种结构，而不是只凭熟悉程度写代码。

学数据结构，真正要学的是什么

数据结构是存储和组织数据的方法，目标是让需要的访问和修改能够以可接受的成本完成。这里有三个关键词：数据、关系和操作。

数据是系统要保存的对象。例如，外卖平台中的订单、导航系统中的路口、编译器中的语法节点，都可以成为数据元素。单独列出元素还不够，我们还要表达元素之间的关系：订单有创建先后，路口由道路相连，语法节点有父子层级。关系不同，适合的组织方式也不同。

操作决定了“可接受”到底意味着什么。同样是一组用户记录，如果业务只需要按编号查询，我们会关注查找；如果还要频繁加入和移除记录，就必须同时考虑插入与删除；如果每次都要取出优先级最高的任务，那么“取最小值或最大值”会成为核心操作。没有一种结构能让所有操作在所有场景中都同样快。

从动态集合看结构的职责

程序里的集合往往会变化。任务会进入等待队列，缓存项会被淘汰，在线用户会登录和退出。我们把这类会增长、缩小或改变的元素集合称为动态集合。

动态集合中的元素通常包含三个部分：

• 键用于识别或比较元素，例如用户编号、任务优先级。
• 附属数据保存业务信息，例如用户名、任务正文。结构可能携带这些信息，却不直接使用它们来组织元素。
• 结构字段由实现维护，例如链表节点的 next 指针、树节点的左右孩子指针。

这种划分很实用。查找结构关心的可能只是键，但找到元素后，业务代码真正需要的是附属数据；结构字段则负责让元素形成某种可遍历、可修改的组织方式。

不要从结构名称开始思考

面对需求时，先问“我该用数组还是链表”，通常问早了。更可靠的顺序是：

1. 系统要保存什么元素？
2. 元素之间有没有顺序、层级或连接关系？
3. 必须支持哪些查询和修改？
4. 哪些操作最频繁，哪些操作允许慢一些？
5. 数据规模、内存和延迟有什么限制？

问题说清以后，结构往往会自然浮现。比如浏览器的后退历史需要“最后进入的页面最先离开”，栈的后进先出规则正好吻合；客服请求需要“等待最久的先处理”，队列的先进先出规则更合适。

从计算问题到可执行算法

算法是一段定义明确的计算过程：它接收输入，执行有限的步骤，最终给出输出。更准确地说，算法是解决某类计算问题的方法，而不是只解决某一个具体输入的临时代码。

以排序为例，我们可以把问题写成一份输入输出契约：

• 输入：一个含有 $n$ 个数的序列 $\langle a_1,a_2,\ldots,a_n\rangle$。
• 输出：输入序列的一个重排 ，满足 。

输入 [31, 41, 59, 26, 41, 58] 只是这个问题的一个实例。一个排序算法必须能处理所有符合约束的实例，包括空序列、重复元素、已经有序的序列和完全逆序的序列。

正确不只是“样例能过”

我们说一个算法正确，意味着它对每个合法输入都会停止，并且输出符合问题要求。这里包含两个条件：

• 会终止：步骤不能无限进行。
• 结果符合契约：输出不仅看起来合理，还要满足事先定义的性质。

排序时只检查“结果是否递增”还不够。算法如果偷偷丢掉一个重复元素，得到的序列仍可能递增，却不是输入的重排。因此，正确性需要同时检查顺序和元素守恒。

实际推理中，可以把循环不变式理解成循环执行期间始终成立的承诺。验证它通常分为三步：循环开始前成立；每轮执行后仍成立；循环结束时，它与终止条件共同推出最终结论。

算法不等于某种编程语言

算法可以用自然语言、伪代码、程序代码甚至硬件电路描述。表达形式可以变化，但过程必须足够精确，使执行者不会对下一步产生歧义。

下面的交互把“问题契约”和“执行步骤”放在一起。输入一组整数后，可以逐步观察插入排序怎样维持“左侧前缀已经有序”这一性质。

数据结构与算法为什么分不开

一个完整的计算过程，既要决定“做哪些步骤”，也要决定“数据放在哪里、怎样找到下一项”。算法负责步骤，数据结构负责表示。两者之间不是简单的工具搭配，而是相互约束。

导航系统可以说明这种关系。现实道路先被表示成图：路口是顶点，道路是边，距离或时间是边的权重。最短路径算法并不直接在真实道路上运行，它处理的是这份图表示。如果表示中缺少道路方向、转弯限制或实时权重，即使计算步骤完全正确，结果也无法满足实际需求。

类似的例子还有很多：

• 搜索服务要先建立便于定位内容的索引，再运行查询过程。
• 任务调度要维护待处理任务及优先级，再反复取出最紧急的任务。
• 编译器要把程序组织成语法树，再按树的层级分析和转换代码。
• 网络路由要把节点与链路表示成图，再计算可达路径或低成本路径。

同一个抽象关系可以有不同表示

线性次序既能放在连续数组里，也能由指针连接成链表。树可以由每个节点的孩子指针表示；完全二叉树也可以放进数组，用下标关系推导父子位置。表示改变后，元素间的抽象关系没有变，但访问路径、修改成本和内存布局会变化。

这解释了为什么“先选算法，最后随便找个容器装数据”经常出问题。算法依赖某些操作，如果底层结构不能高效提供这些操作，整个方案就会被拖慢。

例如，假设算法要重复执行“取出最小元素”。若每次都在线性表中扫描，单次可能检查全部元素；若用能维护最小值位置的优先队列，取出最小元素的路径就完全不同。比较方案时，要把算法调用操作的次数与结构提供操作的成本乘在一起。

接口把配合关系说清楚

我们可以把数据结构看作一组操作的提供者。算法只通过操作与结构交互，例如：

SEARCH(S, k)       // 找到键为 k 的元素；不存在则返回空
INSERT(S, x)       // 把元素 x 加入集合 S
DELETE(S, x)       // 从集合 S 移除已定位的元素 x
MINIMUM(S)         // 返回键最小的元素
SUCCESSOR(S, x)    // 返回比 x 略大的下一个元素

注意 DELETE(S, x) 接收的是已经定位的元素，而不是一个键。若调用者只有键，就要先执行查找。于是“删除一个已知节点”和“按键找到并删除”可能有完全不同的成本。分析复杂度时，必须把前置操作计算进去。

效率决定方案能否扩展

如果计算机速度无限快、内存也没有成本，我们仍然要关心算法是否终止、结果是否正确。但真实系统的时间、空间、通信带宽和能源都是有限资源，所以正确之后还要继续问：输入规模增长时，资源消耗怎样变化？

分析算法，本质上是在预测它需要多少资源。运行时间最常见，但不是唯一指标。内存有限的设备会优先关注空间；分布式系统会关注通信次数和传输量；存储系统还会关注磁盘访问；移动设备可能关心能耗。

增长率往往比硬件常数更有决定性

两个排序过程的工作量可以粗略写成：

常数 $c_1$ 可能比 $c_2$ 小，所以第一种方法在小输入上可能更快。但当 $n$ 持续增大，$n$ 与 $\log_2 n$ 的差距会不断扩大，最终超过常数带来的优势。输入为一百万时， 约为 ，而 本身是一百万。

这不是说常数不重要。缓存命中、语言运行时和编译优化都会影响真实耗时。增长率解决的是另一个问题：当规模跨越几个数量级时，哪种方案更能承受增长。

下面的交互允许你调整输入规模，并比较 $n^2$ 与 $n\log_2 n$ 的估算工作量。两个常数可以不同，这样更容易看到“小规模领先”和“大规模反超”如何同时发生。

分析需要一个明确的成本模型

如果不先约定哪些操作算一步，“这个算法快不快”就没有统一含义。常用的简化模型把加减、比较、赋值、读取和分支等基本操作视为常数时间，并假定指令依次执行。然后把运行时间写成输入规模的函数。

输入规模也要按问题定义。排序常用元素个数 $n$；图算法可能同时使用顶点数 $|V|$ 和边数 $|E|$；处理整数时，数值本身的位数也可能影响成本。把一个任意大的整数运算强行当作常数时间，会得出失真的结论。

简化模型不会呈现缓存、虚拟内存和并行执行的全部细节，却能帮助我们抓住主要增长趋势。进入工程验证阶段，再用基准测试观察常数、内存层次和真实数据分布的影响。

用抽象数据类型分离需求与实现

抽象数据类型可以理解成一份行为契约：它规定保存什么类型的值、允许执行哪些操作、每个操作产生什么结果，却不强制指定数据在内存中怎样摆放。

栈就是典型例子。它规定 push 把元素放到顶部，pop 移除并返回最近放入的元素，整体遵循后进先出。我们可以用数组维护一个顶部下标，也可以用链表把头节点当作栈顶。调用者只要依赖 push、pop 和 isEmpty 的行为，就不需要知道内部表示。

队列则规定先进先出。入队发生在尾部，出队发生在头部。用数组实现时，常把空间看成首尾相接的圆环，让头尾下标越过末端后回到开头；用链表实现时，可以同时维护头指针和尾指针。

行为相同，不代表成本相同

两种实现都能满足同一份契约，但操作成本可能不同。数组栈访问连续内存，额外字段少，却要处理容量；链式栈可以按需增加节点，却为每个节点保存连接信息，并承担分配对象的成本。

抽象让我们先判断“行为对不对”，再判断“实现是否适合环境”。这两层不能混为一谈：

• 接口层关心操作的含义、前置条件和返回结果。
• 实现层关心内存布局、指针更新、扩容方式和具体复杂度。

动态集合的操作菜单

动态集合常见操作可以分成两类：

• 查询操作只返回信息，例如 SEARCH、MINIMUM、MAXIMUM、SUCCESSOR。
• 修改操作会改变集合，例如 INSERT、DELETE。

一个应用通常只需要其中一部分。只要求插入、删除和查找的动态集合可以看作字典；需要插入并反复取出最小元素的结构，更接近最小优先队列。实现时不必为永远不会调用的操作付出复杂度和空间成本。

若键具有全序关系，我们才能自然定义最小值、最大值、前驱和后继。若键只支持相等判断，就不能假设结构可以回答“下一个更大元素是谁”。操作的语义依赖数据本身具有什么性质。

从逻辑关系走到存储表示

逻辑结构描述元素在问题中的关系，存储表示说明这些关系如何落到内存。理解二者的区别，是从“会调用容器”走向“会设计结构”的关键一步。

常见逻辑关系包括：

• 集合关系：元素只共同属于一个集合，没有必然的先后。
• 线性关系：除端点外，每个元素有直接前驱和直接后继。
• 层级关系：元素形成父子关系，一个节点可以带出多个子节点。
• 网状关系：元素之间可以存在多对多连接。

这些关系并不绑定某种内存形式。线性关系可以由连续位置表达，也可以由每个对象保存下一个对象的位置来表达；层级关系可以用指针，也可以在特定条件下用数组下标表达。

连续表示与链接表示

数组把元素放在连续位置。若元素大小固定，知道起始地址和下标，就能直接计算目标位置，因此按下标访问通常是常数时间。代价是中间插入可能需要移动后续元素，固定容量也可能带来扩容问题。

链表把顺序写进节点的连接字段。节点在物理内存中不必相邻，只要 next 能找到后继即可。已知插入位置时，修改少量连接就能加入元素；但访问第 $i$ 个元素通常要从头沿连接逐个前进。

双向链表为每个节点保存前驱和后继，便于向两个方向移动，也能在已知节点时更直接地断开连接。哨兵节点还能把空表、表头和表尾的一些边界情况统一起来，让代码减少特殊分支，不过每条很小的链表都配置哨兵也会增加空间开销。

指针可以由下标模拟

“指针”不一定非要是语言内置的地址类型。若一组对象有相同字段，可以为每个字段建立一个数组。假设使用 key、next 和 prev 三个数组，那么同一个下标 i 在三个数组中的位置共同表示一个对象，next[i] 保存后继对象的下标。

下标 i      key[i]      next[i]      prev[i]
   2           4           3             5

也可以让一个对象占据单个大数组中的一段连续位置，把对象起点当作引用，再通过固定偏移读取不同字段。这揭示了一个很重要的事实：对象和指针是方便理解与操作的抽象，底层仍然可以还原成地址、整数下标和连续存储单元。

树的表示同样取决于操作

二叉树节点通常保存父节点、左孩子和右孩子引用。若节点可以拥有任意数量的孩子，给每个节点预留大量孩子字段会浪费空间。一个常见办法是只保存“最左孩子”和“右侧兄弟”：沿最左孩子进入下一层，沿右侧兄弟遍历同一父节点的其他孩子。这样任意分支数的树也只需要每个节点固定数量的连接字段。

下面的交互用同一组值展示三种表示。你可以切换数组、链表和最左孩子—右侧兄弟树，并点击节点查看“逻辑上的下一个位置”怎样由下标或连接字段确定。

按操作成本选择数据结构

选择结构时，可以把需求整理成一张操作表。表中不只写“要支持什么”，还要写调用频率、允许的最坏延迟、数据规模以及能接受的空间开销。

假设一个集合包含 $n$ 个元素。若用未排序链表保存它，已知位置的头部插入可以是 $O(1)$，按键查找最坏为 $O(n)$；若用平衡搜索树组织有序键，查找、插入、删除和取前驱后继通常都能控制在 $O(\log n)$；若需求只包括字典操作，设计良好的散列表在合适条件下可提供很快的平均操作，但它不天然维护键的有序关系。

这里没有脱离场景的冠军。高频操作不同，答案就可能不同：

• 只按精确键查询，不需要顺序遍历，可以重点考虑字典操作的成本。
• 经常查询区间、最小值或后继，键的顺序就很有价值。
• 数据量很小且实现越简单越好，线性扫描可能已经足够。
• 延迟必须有稳定上界时，不能只看平均性能，还要检查最坏情况。
• 内存紧张时，要计算预留容量、指针和辅助索引的空间。

把整个调用链算进去

设某流程对 $n$ 个元素执行 $n$ 次“按键查找并删除”。如果底层每次查找是 $O(n)$，删除连接本身是 $O(1)$，总成本仍可能达到 $O(n^2)$，因为主要工作发生在查找阶段。

同理，一个结构的单项操作很快，并不保证整个算法快。算法可能重复调用它，也可能在每次调用前后做大量转换。评估时应画出完整路径：输入怎样进入结构，核心操作执行多少次，结果怎样输出。

平均、最坏与摊还成本回答不同问题

最坏成本描述一次操作可能遇到的上界；平均成本依赖输入或随机行为的分布；摊还成本把一串操作的总成本平均到每次操作上。动态数组扩容就是常见例子：某次扩容可能复制许多元素，但并非每次追加都扩容，因此一长串追加操作的平均负担可以很低。

写复杂度时，应说明使用的是哪种口径。若系统处理实时控制、交易或交互请求，偶发的高延迟可能比平均值更重要；若处理离线批任务，总吞吐量可能更值得关注。

用正确性与实验完成闭环

结构选定以后，还需要两类验证：

1. 逻辑验证：每个操作是否保持结构不变式。例如，栈顶下标是否始终指向有效范围，双向链表的前后连接是否互相一致。
2. 工程验证：在代表性规模与数据分布上测量耗时、内存和极端延迟，确认分析中的假设与运行环境相符。

基准测试不能替代理论分析，因为小样本可能看不到增长问题；理论分析也不能替代测量，因为缓存、内存分配和输入分布会改变常数。二者解决不同层面的问题。

建立一套可重复的分析习惯

学完概念后，最有用的成果不是一张结构名称表，而是一套遇到新问题仍能重复使用的分析流程。你可以按下面的顺序检查自己的方案。

写清问题契约

明确合法输入、目标输出和必须满足的约束。把一个具体样例与整个问题区分开。样例帮助理解，契约决定算法究竟要保证什么。

列出核心操作

把查询与修改分开，标出每种操作的频率。若某个操作需要前置步骤，例如按键删除要先定位节点，就把整个调用链列出来。

描述抽象关系

判断元素之间是无序集合、线性次序、层级还是一般连接。若键需要比较，还要说明它是否具有全序关系。关系决定了哪些查询有意义。

选择表示并核算成本

比较候选表示的时间、空间和实现复杂度。不要只写一个孤立的复杂度，要说明输入规模是什么、成本属于最坏还是平均情况，以及结论依赖哪些假设。

证明关键性质，再用实验校准

为修改操作写出结构不变式，检查空结构、单元素、容量边界、重复键等情况。随后用接近真实的数据规模测量性能，验证增长趋势和常数开销。

这套流程会贯穿后续每一种具体结构。数组、链表、栈、队列、树和散列表看起来差异很大，但分析它们时，我们反复问的仍然是同一组问题：数据有什么关系，操作需要什么保证，表示付出什么成本。