数据结构——数组、链表、树与图

数据结构是组织数据的方式，让查找、插入、删除和遍历等常见任务更容易完成。想理解数组、链表、树和图，最快的方法是先问两个问题：数据是什么形状的？哪种操作需要足够“便宜”？

如果数据是一个序列，数组通常是起点。如果每个元素主要指向下一个元素，链表可能更合适。如果数据有层级，就用树。如果元素可以向多个方向连接，就用图。

这里有一条最简洁但有用的规则：

• 数组：最适合按索引访问的有序数据。
• 链表：最适合链式的局部连接。
• 树：最适合层级结构。
• 图：最适合网络关系。

数组、链表、树和图到底是做什么的

数组按固定顺序存储元素，并允许你直接引用某个位置，比如“第 $7$ 个元素”。在常见的连续存储实现中，这种直接按索引访问通常是 $O(1)$。

链表把元素存成节点，每个节点指向另一个节点。你可以从一个节点走到下一个节点，但要到达第 $n$ 个元素，通常必须先经过前面的节点，所以按位置访问一般是 $O(n)$。

树按层级存储数据。每个节点都可以有子节点，因此这种结构天然适合表示嵌套关系，比如文件夹里还有文件夹。查找和更新的代价取决于树的类型，以及它是否保持平衡。

图存储节点和边。与树不同，一个节点可以以任意方式连接到许多其他节点，而且允许出现环。因此，图是表示道路、社交网络和依赖关系图的自然模型。

快速比较：每种数据结构适合什么场景

Structure	Best mental model	Usually good at	Common limitation
Array	A numbered row of items	Direct access by index	Middle insertions and deletions often require shifting items
Linked list	A chain of nodes	Inserting or removing near a known node	Random access is slow
Tree	A branching hierarchy	Representing levels and parent-child relationships	Behavior depends heavily on tree type
Graph	A network of connections	Reachability, paths, and relationships	Algorithms are often more complex

示例：在一个校园应用中选择数据结构

假设你正在开发一个校园应用，其中有课程表页面、课程目录和步行地图。选择数据结构最简单的方法，就是让每个功能去匹配它的数据形状。

课程表页面中的工作日标签天然适合用数组：

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

这里的关键功能是按位置直接访问。“给我显示第 $3$ 个标签”是有意义的，而且顺序很重要。

课程目录天然适合用树：

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

每一层都包含下一层。这就是层级结构，所以树是最清晰的模型。

建筑物之间的步行路线天然适合用图。一个建筑可以连接到多个其他建筑，路径也可能绕回原处。如果你想找出从图书馆到实验室的最短路线，你解决的是图问题，而不是树问题。

链表则适合同一个应用中更窄的一部分：最近访问页面组成的链，如果主要操作是一次向前或向后移动一步。在这种情况下，每个页面主要需要与附近页面建立链接，而不是快速访问第 $20$ 个页面。

这里的结论是，“最好”取决于任务本身。一个产品可以同时使用多种数据结构，因为数据的不同部分可能有不同的关系。

如何快速区分它们

很多学生一开始把这些当作术语来背。这会让主题显得很抽象，但实际问题更简单。

问自己：什么操作应该足够便宜？

如果你希望“跳到位置 $i$”很便宜，数组就很强。如果你希望“沿着下一个连接继续走”很便宜，链式结构会有帮助。如果你希望“沿层级向下移动”，树就合适。如果你希望“判断两个东西是否连通”，图就合适。

学习数据结构时的常见错误

以为某一种结构总是最快

不存在放之四海而皆准的赢家。“快”取决于你最常做什么操作，也取决于具体实现。

认为树天然就高效

有些树确实支持非常高效的查找，但这取决于树的类型，以及是否满足平衡等结构条件。形状很差的树，性能可能比平衡树差很多。

仅仅因为“插入便宜”就选择链表

一旦你已经拿到正确的节点，插入确实可能很便宜。但找到那个节点本身仍然可能花时间。

当数据其实是图时却硬用树

如果一个元素可以有多个父节点、交叉链接或环，把数据强行塞进树里会掩盖真实结构，也会让后续操作变得别扭。

把抽象结构和编程语言里的具体特性混为一谈

编程语言中的 “array”“list”“map” 或 “tree” 可能带有具体实现选择，这会影响内存使用和速度。抽象概念和具体容器有关联，但并不完全相同。

数组、链表、树和图分别用在什么地方

数组用于有序集合、表格、缓冲区，以及任何位置很重要的场景。

链表出现在一些更专门的实现中，在这些场景里，局部指针更新比随机访问更重要。

树用于层级数据，比如文件系统、文档结构、表达式树，以及许多搜索索引。

图用于路线、依赖分析、网络建模、推荐链接，以及各种连接关系问题。

如何选择合适的数据结构

先问两个问题：

1. 数据是什么关系：序列、层级，还是网络？
2. 最重要的操作是什么：索引、局部更新、层级遍历，还是路径查找？

这两个答案通常就能很快缩小选择范围。

如果你还是不确定，可以先在纸上画一个很小的数据示意图。很多时候，图形会比代码更早暴露出真正的结构。

自己试一试

选三个熟悉的例子，比如播放列表、文件夹系统和地铁线路图。判断它们主要是序列、层级还是网络，然后选择能让主要操作更容易的数据结构。如果你还想找一个案例来测试自己，GPAI Solver 可以生成类似的分类练习。