刚上大学学数据结构：那些结构到底在解决什么

开学两周，C 和数据结构这两门课一起压过来，我有点懵。

C 还好，至少看得见代码在干嘛。数据结构第一节课就甩出一堆名词：线性表、栈、队列、链表、树、图……老师讲得很快，我抄了一黑板，回宿舍翻笔记，发现自己一个都没真懂。背是背下来了，但完全不知道这些东西为什么要存在。

这篇就是我自己重新捋一遍的笔记。不追求严谨，主要是想把”它在解决什么问题”这件事想清楚——对我来说，这比记定义重要多了。

先说我想通的那件事

我卡了好几天，最后是被一句很糙的话点醒的：

数据结构，说白了就是”你用什么东西去装数据”。

装法不一样，你取数据、加数据、删数据的快慢就完全不一样。所有这些名词，其实都在回答同一个问题——这堆数据，怎么放才好用。

想通这个之后，再看那些结构就顺多了。下面按我自己理解的顺序记。

数组：最朴素的那个

数组是我最早会的，因为 C 一上来就教它。一排格子，挨着放，靠下标取：

int a[5] = {3, 1, 4, 1, 5};
int x = a[2];  // 直接拿到第 3 个，4

它的好处特别直接：知道下标就能立刻拿到值，不用从头找。原因是它在内存里是连续的一整块，a[2] 的地址就是开头地址加两个 int 的偏移，一步到位。

但它也有让我别扭的地方：

大小一开始就定死了，想再多塞一个进不去；
想在中间插一个数，后面所有的都得往后挪一格，删也一样。

链表：第一次真正用上指针

链表是我第一次觉得”指针原来有用”的地方。

在这之前我对指针的印象就是”会段错误的那个东西”。直到老师说链表的节点是一个个 malloc 出来的、靠指针串起来的，我才突然有点感觉：

struct Node {
    int val;
    struct Node *next;  // 指向下一个节点
};

每个节点除了存自己的值，还存了一个”下一个在哪”的地址。它们在内存里根本不用挨着，全靠 next 这根线连起来：

flowchart LR
    H(["head"]) --> A["3 · next"]
    A --> B["1 · next"]
    B --> C["4 · next"]
    C --> N["NULL"]

画出来就很直观——一根 next 把零散的节点串成一条线，最后指向 NULL 表示到头了。

这样一来，数组那两个毛病就解决了：

想加一个节点，malloc 一个挂上去就行，不用预先定大小；
想在中间插，只要改两个指针的指向，不用挪动一堆数据。

代价是：它没法按下标直接跳。想拿第 5 个，只能从头顺着 next 一个个走过去。

我自己是这么记数组和链表的区别的：

结构	按位置取第 k 个	中间插入 / 删除
数组	快，一步到位	慢，要挪动后面全部
链表	慢，得从头走	快，改指针就行

它俩几乎是反过来的。选哪个，就看你这堆数据主要是拿来读，还是经常改。

栈和队列：其实是”加了规矩的线性表”

一开始我觉得栈和队列是两个新东西，后来发现它们更像是”被限制了用法的数组/链表”。

栈只准从一头进、从同一头出，后进的先出来（LIFO）。我脑子里的画面是一摞盘子，最后放上去的最先被拿走。

队列是一头进、另一头出，先进的先出来（FIFO），就是食堂排队。

画出来，两者的”出入口”差别一眼就能看出来——栈只有顶端一个口，队列两头各一个：

flowchart TB
    top(["顶端：push / pop 都在这头"]) --> s3["3 ← 最后进，最先出"]
    s3 --> s2["2"]
    s2 --> s1["1 ← 最先进，最后出"]

flowchart LR
    inq(["入队 →"]) --> q1["1"]
    q1 --> q2["2"]
    q2 --> q3["3"]
    q3 --> outq(["→ 出队"])

这两个限制听起来很别扭——好端端的为什么要自废武功？后来我发现，恰恰是这个”规矩”让它们好用。最让我有”原来如此”感觉的是函数调用：

void a() { b(); }
void b() { c(); }
void c() { /* ... */ }

a 调 b、b 调 c，等 c 结束要先回到 b，再回到 a——后调用的先返回，这不就是栈吗？原来”调用栈”这个词不是比喻，它真的是一个栈。那一刻我觉得这门课突然和我写的 C 代码连上了。

哈希表：拿空间换时间

哈希表（散列表）是当时让我觉得最神奇的一个。

前面说了，想在数组里找一个值，最坏得从头扫到尾。哈希表的想法很”作弊”：与其去找，不如一开始就算好它该放哪。

拿钥匙（key）过一个哈希函数，算出一个下标，直接把值丢到那个位置。下次要找，再算一遍同样的下标，一步就拿到。等于把”查找”变成了”计算”。

代价是它要占一块更大的空间来摊开放，而且两个 key 可能算出同一个下标（冲突），还得想办法处理。但”用多一点内存，换查得飞快”这个交易，在很多场景里太划算了。

后来我发现”拿空间换时间”是写程序里反复出现的一种思路，哈希表只是我第一次见到它这么明目张胆。

树：从”一条线”到”分叉”

前面那些，数据基本都是排成一条线的。树是我第一次接触有层级的结构：一个根，往下分叉，每个节点带几个孩子。

最常打交道的是二叉树——每个节点最多两个孩子。而二叉搜索树让我印象很深：它有个规矩，左孩子比自己小、右孩子比自己大。

flowchart TD
    A["8"] --> B["3"]
    A --> C["10"]
    B --> D["1"]
    B --> E["6"]
    C --> F["14"]

这个规矩有什么用？找一个数的时候，拿它跟当前节点比一下：小了往左、大了往右，每走一步就甩掉一半不用看的节点。这跟我们查字典翻中间、再决定往前还是往后翻是一个道理——比一个个翻快太多了。

我当时的笔记上写了一句话给自己：树之所以快，是因为它让你每一步都能”排除掉一大半”。

图：当数据之间是”关系”

树还算规整，到了图我又有点晕。图就是一堆点（顶点），点和点之间用线（边）连起来，没那么多规矩——可以到处连，可以成环。

后来我用身边的例子才接受它：

同学之间谁认识谁，是图；
地图上城市之间的路，是图；
网页之间互相的链接，也是图。

凡是数据之间的关系不是”一条线”或”一棵树”那么整齐，而是网状的、互相牵扯的，图就派上用场了。它具体怎么遍历、怎么算最短路，课上还没讲到，我先记着它”是用来描述关系的”，剩下的之后再补。

回头一看：链表和树其实都是图

写到这我突然反应过来一件事——前面那些结构，好几个其实可以用图来表示。

链表就是一张图：每个节点只往外连一条边（指向 next），连成一条线；
树也是图：一张连通、无环、有方向的图，只不过每个节点的”孩子”是受限的；
所以图是最一般的那个，链表和树都可以看成它的特例。

但有意思的是，数组就归不进去。因为图描述的是”谁和谁有关系”，而数组描述的是”数据在内存里怎么挨着放”——它根本没有”关系边”这回事，硬要说也只是下标恰好相邻。

把它们摆在一起看

捋完一轮，我试着用一句话概括每个结构在擅长什么：

结构	一句话理解	最擅长
数组	挨着放的一排格子	按下标快速取
链表	指针串起来的节点	频繁增删
栈	只从一头进出	后进先出（如调用栈）
队列	一头进一头出	先进先出（如排队）
哈希表	算好位置再放	极快地查找
树	分层、分叉	每步排除一大半
图	点和边	描述网状关系

列出来之后我才看清楚：它们没有谁比谁高级，只是各自擅长不一样的事。挑哪个，永远取决于你这堆数据接下来主要要干嘛——多查就上哈希，多改就用链表，有层级关系就用树。

写在最后

开学这两周，我从”被一黑板名词吓到”，到现在大概能说出每个结构是为了解决什么问题，已经踏实多了。

很多东西其实还很浅：树的平衡、图的遍历、各种结构的时间复杂度怎么严格算，我都还没真正啃下来。这篇也肯定有理解不到位的地方，等学深了再回来改。

但有一个感觉我想先记下来：数据结构不是用来背的，是用来选的。课本把它们一个个列出来，是给你一套工具；真正重要的是遇到问题时，知道该从工具箱里拿哪个。

先记到这。等我把 C 的指针玩得更熟一点，应该能把这些结构自己都写一遍——到时候再写一篇。