数据结构复习路线：从链表到二叉树，动手实践是关键

说句实话，上个月重新翻出当年学数据结构时的笔记，我只记住了“链表”“栈”“递归”这几个词，真让我写个反转链表的代码，愣是盯着屏幕半天没动手。这种感觉太真实了——大学课堂上学的时候觉得都会，考试也应付过去了，可一旦放下几个月甚至几年，脑子里的东西就像没保存过的文档一样，怎么找都找不回来。相信很多人跟我一样：不是没学过，而是学过之后没有一个系统的复盘方式，知识很快就被覆盖了。

这次我决定认认真真把数据结构从头到尾重新巩固一遍。不是零基础学，也不是纯粹刷题，而是带着“以前学过、现在模糊”的前提，重新构建知识框架。如果你正准备数据结构期末复习，或者打算备考408考研，再或者工作中写代码总觉得缺了点什么，这篇文章就是按我的复习过程整理出来的完整路线：从线性结构讲到树和图，从原理讲到能直接跑的代码，最后还有我踩过的坑和排查经验。我不会讲一个“看起来完美”的学习过程，反而会告诉你哪些地方最容易返工、哪些知识点最容易自欺欺人。

1. 为什么“学过但忘了”是常态：先聊聊复习这件事

1.1 遗忘的规律决定了复习策略

以前我一直以为“忘了”是因为自己学得不够扎实，后来才意识到这是大脑的正常机制。艾宾浩斯遗忘曲线说的很清楚：新学的东西如果不经过周期性回顾，一周后能记住的往往不到三成。数据结构这门课的特别之处在于，它不像数学公式那样能靠推导链串起来，而是一堆结构定义、算法流程、边界条件高度复杂的内容。比如单链表删除节点，如果只是看了一遍代码，不亲手推指针，一个月后你一定会“记得有个特判处理头节点的部分”，但那个特判条件写的什么，全忘了。

所以复习的第一步，不是重新逐章看教材，而是先正视遗忘这件事。我给自己的要求是：不追求第一次就全记住，只追求每一次复习都在“回忆→卡住→翻书→动手→再回忆”这个循环里走一遍。每次卡住的地方就是真正需要补的地方，而不是教材里的每一段。

1.2 我的复习总路线：三轮推进而不是一轮苦读

第一轮是“框架唤醒”，核心目标是回忆起每个数据结构是干什么的、解决什么问题。这一轮不用纠结代码细节，用画图的方式快速过一遍单链表、栈、队列、二叉树、哈希表、图这些常见结构。第二轮是“代码复现”，每个核心结构都要自己动手写一遍基本操作，包括建表、插入、删除、遍历、查找。第三轮是“实战与错题整理”，用少量经典题目和往年期末题来检验自己是不是真的掌握了。

这三轮看起来简单，但很多人复习失败恰恰是因为跳过了第二轮直接去刷题。你想想，连链表反转的循环条件都写不利索，做题时不得不在草稿纸上反复推，效率低不说，信心也容易被磨掉。你要是已经工作，时间碎片化，我建议把三轮拆到三个星期里，每周只做一件主线任务；如果时间紧迫，比如离期末就一周，那至少也要保证“每块结构都写一遍核心代码”，这是底线。

1.3 复习过程中我坚持的三条原则

第一，能用图说清楚的，绝不用文字硬背。数据结构的本质就是数据元素之间的关系，画图就是把这些关系可视化。一个双向链表的指针关系，文字写出来又长又绕，画出来一目了然。第二，每个操作都必须追问“为什么”。比如栈为什么能解决括号匹配问题，因为它的后进先出特性天然对应嵌套结构。不弄懂这层逻辑，代码只能靠死记，换个场景就废。第三，一定要动手运行代码。只看书、只看视频，本质上还是被动接受。我会在下面第4部分给你一些可以直接跑起来练手的代码，最好把它们敲进环境里，哪怕运行报错也是一种学习，因为报错能暴露你没注意到的细节。

2. 线性结构：最需要重建的直觉

2.1 数组和动态数组：从内存视角重新看

很多人以为数组没什么好复习的，但它其实是理解后面一切结构的基础。数组在内存里是一块连续的空间，这意味着它有两个特性：一是访问第i个元素的时间是常数，直接通过起始地址加偏移量找到它，这叫随机访问；二是在中间插入或删除元素特别费劲，因为后续所有元素都要整体移动。

我建议你复习数组的时候，可以顺手看一下动态数组（比如C++的vector、Java的ArrayList）的实现逻辑。它们会在容量不够时申请一块更大的内存，把旧元素复制过去再释放旧空间。这里有个很经典的“均摊复杂度”概念，很多人第一次学的时候没注意：虽然扩容这一单个操作是O(n)，但连续插入n个元素的总代价是O(n)，平均下来每次插入还是O(1)。理解了这个，以后分析很多容器的性能都不会慌。

复习数组可以做一个小练习：写一个函数，能将数组的奇数移到偶数前面，要求时间复杂度O(n)。这个题的边界条件不多，但很锻炼双指针的思路。我当年第一次做这个题的时候，写了一堆乱七八糟的判断，后来才反应过来这其实就是“保持相对顺序”和“不保持相对顺序”两种题型的区别，得分开讨论。

2.2 链表：画图胜过背书

如果你问我数据结构里最值得花时间复习的线性结构是哪个，我一定会说是链表。原因很简单：它的指针操作最能暴露你对“引用”和“内存”的理解程度。单链表至少要有这三个经典操作练手——头插法创建链表、给定节点前插入新节点、反转链表。头插法相对来说最直观，但很多人会犯“新节点没连到链表上就移动了指针”的错。我印象里最经典的“翻车”是：想把q插入到p后面，结果先写了p->next = q，再把q->next指向原来的后继，这个时候原来的后继已经丢了。

链表的知识点里，单链表、双向链表、循环链表要对比着复习。它们的接口看起来都差不多，但处理边界条件的差异很大。比如双向链表删除节点最方便，因为可以得到prev；循环链表的判断结束条件是“回到头节点”而不是“遇到NULL”。这部分我强烈建议你在纸上画图，把“断链”和“接链”的顺序标出来。你可以想象成一群人手拉手站成一排，现在要让一个人插队进中间，你得先让前面的人松开手去拉他，他再拉后面的人，顺序反了队伍就断了。

链表常见的面试题还有“快慢指针找中间节点”“判断链表是否有环”。快慢指针的思路很优雅：一个走两步，一个走一步，如果有环，它们总会相遇。我当时为了说服自己，专门写过一段测试代码，用慢指针走一步、快指针走两步跑了几个循环，确认相遇了才放心。如果你也觉得直觉不够，建议也这么干。

2.3 栈和队列：别把“线性结构”局限在字面理解

栈和队列虽然都是线性结构，但它们的核心是“受限操作”，或者说对操作顺序做了严格限定。栈是后进先出，只允许在栈顶入栈、出栈；队列是先进先出，只允许在队尾入队、队首出队。这个限制不是缺点，反而让它们在某些问题上成为最合适的工具。

栈最大的应用场景是处理嵌套结构：函数调用栈、括号匹配、表达式求值、深度优先搜索的隐式调用。复习的时候你可以自己实现一个“括号匹配”栈题，只要三种括号：圆括号、方括号、花括号。如果读完整个字符串栈是空的，说明全部匹配；如果遇到右括号时栈顶不是对应的左括号，说明不匹配。这个代码写起来不到20行，但特别能检验你有没有真正掌握“栈顶”的含义。

队列则更多用于“按顺序处理”的场景，比如任务调度、树的层序遍历、广度优先搜索。而双端队列是中间态，两端都能进出，所以它更适合做滑动窗口这类问题：窗口滑动时，右侧进元素、左侧出元素，双端队列可以同时维护窗口的最大值索引。我第一次用双端队列做这个题的时候，觉得它就是“带索引的淘汰机制”，写多了才发现它是一个很自然的思考工具。

你复习栈和队列时，最好能自己问一个问题：为什么很多教科书都把“用栈实现队列”“用队列实现栈”作为必会题？因为这两个题目强迫你理解两种结构的本质差异。用两个栈实现队列的思路是：入队直接压入栈A，出队时若栈B为空，就把栈A元素全部弹到栈B再弹出栈顶。这样元素顺序被“倒”了两次，负负得正，就变成先进先出了。

2.4 双端队列：看起来冷门，但值得单独跑一遍

“双端队列”这个词常出现在数据结构pdf或实验报告里，很多人觉得它就是个可有可无的进阶内容，其实它是理解“受限操作”边界的一个好切入口。它的名字听起来复杂，但定义就是“两端都可以插入和删除”的队列，是栈和队列的一个泛化。

为什么要刻意提它？因为你会发现，当两端都能操作时，很多以前需要绕弯的算法会变简单。比如回文判断，从两端取字符比较本身就是双端队列的思路；再比如刚才说的滑动窗口最大值，java里ArrayDeque就是双端队列的标准实现。复习时千万不要只看定义，建议自己写一个基于数组的双端队列，并处理好队空、队满判断。这里有一个容易犯的细节：循环队列里，tail指针通常指向下一个可写位置，而不是最后一个元素，忘记这一点会导致容量判断差一位。

3. 树形结构与图：从“背代码”到“懂思想”

3.1 二叉树基础与遍历：递归是钥匙，层序是例外

树这一章是很多人的分水岭。二叉树的定义本身很简单：每个节点最多有两个子节点。但它的遍历方式——前序、中序、后序、层序——会让你第一次真正体会到“递归”的力量。递归看多了容易麻木，我的建议是：不要把递归理解成“函数自己调用自己”这种玄学，而是理解为“把一个节点的问题，交给它的左右子树去解决”。前序遍历就是“先处理当前节点，再递归处理左子树，再递归处理右子树”，这句话能复述出来比背下来代码更重要。

层序遍历则是一个经典的队列应用。它的思路是：根节点先入队，然后不断从队列里取出节点并把它左右孩子入队。这个“按层”的顺序，天然满足队列的特点。我可以很确定地说，如果你能不看书独立写出层序遍历，那么广度优先搜索的基础你就已经掌握了大半。

树这里还有一个常见考点：已知前序和中序遍历，如何还原二叉树。它的原理是中序遍历中，根节点把左右子树分成两半，而前序遍历的第一个元素就是根。递归地切分，树就出来了。很多同学在这道题上卡半天，是因为没有意识到“前序+中序”组合能唯一确定一棵二叉树，而后序+中序也一样。

3.2 二叉搜索树：最有“二分感”的树

二叉搜索树说穿了就一句话：左子树上所有节点的值都小于根节点，右子树上所有节点的值都大于根节点。听起来很简单，但它带来一个特别重要的推论：中序遍历一颗二叉搜索树，得到的结果是递增序列。复习到这个点时，建议你亲手写一个判定函数，判断一颗二叉树是不是合法的二叉搜索树，而不要用“只比较当前节点和左右孩子”的简单写法，因为那样会漏掉“整个左子树都要小于根”的条件。

BST的问题集中在插入、删除、查找。查找就是不断跟当前节点比大小走两边；插入就是找到空位放进去；删除稍复杂，要分三种情况：叶子节点直接删、只有一个孩子就“托孤”、有两个孩子就找中序后继来顶替。我当时最喜欢考自己“两种孩子”的删除，因为这里最容易把指针搞乱。

为什么强调BST的“平衡”问题？因为最坏情况下它会退化成一条链，查找复杂度从O(log n)掉到O(n)。所以后来才会有AVL树、红黑树这些“自平衡”的变种。如果你不是考研深入方向，理解“为什么要平衡”就够了，代码实现不用强求，那是408里稍偏后的内容，复习重心应该放在普通BST的操作上。

3.3 图：邻接表和邻接矩阵怎么选

图是我个人觉得最“不像数据结构”的章节，因为它更接近算法。图的存储方式只有两种主流选择：邻接矩阵和邻接表。邻接矩阵直观、判断两点之间有没有边是O(1)，但空间是O(V²)；邻接表只存储实际存在的边，遍历某个节点的邻接点很高效，但判断两点是否有边需要扫描链表。怎么选，完全看场景：稠密图用矩阵，稀疏图用邻接表。你如果正在做“地铁换乘最少次数”这类问题，邻居节点少的图用邻接表更自然。

图的遍历有两个主角：深度优先搜索和广度优先搜索。DFS我一般习惯用递归写，注意记录visited数组防止死循环；BFS用队列，层序二叉树的队列经验在这里直接复用。比较有意思的是，如果你用DFS走迷宫，走出来的路径不一定最短，但如果你用BFS并记录每层步数，第一次到达终点时的路径就是最短的。这个差异可以成为复习时的“顿悟点”，我在复习图上花了不多的时间，因为核心操作就那么几个，关键是理解搜索产生的“树”和原图的关系。

3.4 查找与排序：把复杂度的账算清楚

查找和排序是数据结构各章节里最容易考“知识点归纳”的部分，因为它有很多算法要对比。查找这边，顺序查找、二分查找、哈希查找是三个层次：二分查找要求有序序列且能随机访问；哈希查找则是用哈希函数把关键码映射到槽位，如果冲突就用开放定址法或链地址法解决。哈希表我建议你亲手实现一个最简单的链地址法版本，就是每个桶里挂一个链表，插入时计算哈希值找到桶，然后查这个桶里的链表。

排序算法是必考，因为它比的是“稳定性”和“复杂度”。这里说的稳定性不是某个算法快不快，而是当两个元素值相同，排序后它们的相对顺序会不会改变。像冒泡、插入、归并都是稳定排序；选择、快排、堆排通常是不稳定的。我复习的时候做了一张表，列了每一种排序的最好、平均、最坏时间复杂度和空间复杂度，然后反复默写。

你可能会问，复习排序有什么用？除了应付考试，它更让你体会“不同场景选不同算法”的思路：数据量小，插入排序就能打天下；数据量大到内存放不下，就要考虑归并；基本有序的序列，插入排序的效率比快排还要好。这不是算法竞赛才会干的事，实际的业务系统里经常要处理这类问题。

4. 实操：几个十分钟就能写完的复习代码

4.1 单链表的反转：迭代与递归，你必须掌握两种写法

链表的反转是数据结构里最经典的“手写题”。我建议你先把迭代写法写到肌肉记忆：定义三个指针prev、cur、next，每一步都先把cur的下一个节点保存好，再把cur的next指向prev，然后整体后移。边界条件是cur为NULL时，此时prev正好是新的头节点。我第一次写的时候总是在“保存下一个节点”这一步丢节点，后来强迫自己在每一轮都先写next = cur->next，再动指针指向，这个习惯帮我省了不少调试时间。

struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL, *cur = head, *next = NULL; while (cur) { next = cur->next; // 先保存下一个节点 cur->next = prev; // 反转指针 prev = cur; // prev 前进 cur = next; // cur 前进 } return prev; }

递归版本更短但更难想清楚：它的思路是“先把后面的链表反转好，再把当前节点的下一个节点的next指向当前节点”，最后返回新头。很多讲解只说代码，不说为什么，其实关键在“递归返回之后，当前节点前面的部分怎么接上”。我用一个长链表跑过之后才确认：递归返回的newHead就是原链表最后一个节点，这是整个反转后的头部，而每一层递归只负责把自己这一环接上。

4.2 二叉树层序遍历：队列的经典应用场景

层序遍历代码是面试高频考点。它最核心的一点是：在每一层开始前先记录队列长度size，然后只处理size个节点，这样就能保证这一层的节点不会和下一层混在一起。很多人第一次写层序遍历时不知道区分每一层，结果输出是平的，看不出“层”的概念。

void levelOrder(struct TreeNode* root) { if (!root) return; struct TreeNode* queue[1000]; int front = 0, rear = 0; queue[rear++] = root; while (front < rear) { int size = rear - front; // 当前层节点数 for (int i = 0; i < size; ++i) { struct TreeNode* node = queue[front++]; printf("%d ", node->val); if (node->left) queue[rear++] = node->left; if (node->right) queue[rear++] = node->right; } printf("\n"); } }

注意这个代码用的是数组模拟队列，front和rear是下标，因此rear - front就是队列中的元素数量。如果你用的是C++的queue，就得在每一层用size = q.size()记录下来，不能直接用q.size()控制循环，因为循环过程中有新元素入队，大小会变。这是我复习时自己踩过的一个细节。

4.3 手写快排和归并排序，练到形成条件反射

排序算法里我建议重点手写两个：快排和归并。快排的核心是“分区”，选一个基准值，把比它小的放左边，比它大的放右边，然后递归处理左右两半。写快排时最需要注意的是递归的区间别写错：如果用的是“左闭右开”的区间写法，那递归调用时左边的区间是[l, p)，右边是[p+1, r)，一定要跟你的函数定义保持一致。

void quickSort(int arr[], int l, int r) { // 左闭右开 [l, r) if (l + 1 >= r) return; int pivot = arr[l + rand() % (r - l)]; // 随机选基准，避免最坏情况 int i = l, j = r - 1; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { swap(arr[i], arr[j]); i++; j--; } } quickSort(arr, l, j + 1); // 注意：此时 j 是右半部分的最后一个位置 quickSort(arr, i, r); }

写完后可以自己测一个有点重复值的数组，比如[3,5,2,3,8,1]。你会发现经典快排如果不加处理，重复值会造成某一边特别长，这就是它退化的潜在原因。

归并排序则是另一个思路：先不断拆成两半，拆到只剩一个元素，然后两两归并。归并的过程需要额外数组暂存，所以空间复杂度是O(n)。它的优点是稳定且时间复杂度稳定在O(n log n)。我在复习时专门对比了快排和归并：快排整体更快一点，但排序结果不稳定且可能有极端情况；归并稳定但需要额外空间。这正好呼应了前面排序章节说的“场景决定选型”。

5. 常见问题与排查技巧实录

5.1 C语言复习时的高频事故：野指针和初始化

如果你用的是C语言版的数据结构教材，那么复习过程中最折磨人的往往是内存问题。指针没初始化、释放了还在用、访问越界，这三大事故几乎人人都碰到。链表类的代码里，最常见的错误是创建新节点时忘了分配内存，或者用malloc分配了但没把next置空。你在调试时往往发现程序有时正常有时崩，这种“玄学”状态基本都是野指针。

我的排查习惯很简单：每次操作指针前先确认这个指针指向哪里、是否有效。打印调试时，把指针地址和关键字段打出来，比断点还好用。比如反转链表过程中，在每次循环结尾打印cur和prev的值，你马上就能看出指针是不是“走过了头”。

5.2 “代码写对了但复杂度算错了”是普遍问题

很多人在复习时对时间复杂度只有一个模糊感觉：知道快排是O(n log n)，但具体到某个算法，为什么是O(n log n)，推导过程是什么，却说不上来。这会在面试或期末简答题里非常吃亏。比如堆排序，建堆是O(n)，每个元素出堆调整是O(log n)，所以整体是O(n log n)。如果你把建堆也算成O(n log n)，算出来对但思路是错的。

建议你把每种算法的复杂度推导过程都写一遍。比如归并排序的递推式T(n) = 2T(n/2) + O(n)，展开后每一层都是O(n)，共log n层，所以总复杂度O(n log n)。这一行推导比死记结论有用得多。同样，空间复杂度也别忽略——快排的递归栈深度最好情况是O(log n)，最坏是O(n)，它不是O(1)的。

5.3 笔试和实验报告中的常见丢分点

我在复习时特意看了一眼以前写过的一些实验报告，发现当时为了凑字数写了很多“流程图”和概念，本质上没有体现自己的思考。其实实验报告最该写清楚的是：你测试了哪些边界条件，遇到了什么bug，是怎么解决的。如果你现在还做实验报告类作业，请一定保留“测试用例”这一节，老师很看重这个。

笔试里还有一类常见的“伪考点”是排序稳定性判断。我之前老是把选择排序的稳定性记反，后来用一个人群排队场景来记：稳定排序相当于值相同的人保持原来的前后顺序，不稳定排序则可能让同为80分的人互换位置。插入、冒泡、归并这类“相邻比较/相邻插入”的算法天然稳定；选择排序会跨距离把最小值换到前面，就容易被破坏顺序，因此不稳定。这样记下来之后，我基本不会错了。

5.4 常见问题速查表

这个表是我复习时自己整理出来的，每次遇到问题就加一行。收效很直接，因为很多问题其实是同一类根源，归纳后能避免重复踩坑。

6. 最后再分享点：资料、工具和我的复习心得

资料这块我是这样搭配的：基础概念看王道和教材，代码练习靠自己敲。王道数据结构适合考研人群，它的“知识点总结”和“小题题库”能帮你快速查漏补缺。李春葆老师的《数据结构教程》（C语言版）讲解很细，代码很适合跨考或基础一般的同学。但不管你选哪本，都要记得——教材是工具书，不是小说，不是从头读到尾就有用的，你要带着问题去翻。

工具方面我最常用的是Visio画图：每次复习一个结构，先画它的插入/删除过程，画完再写代码。这个习惯让我指针层面的错误少了一半以上。可视化网站Visualgo也推荐，可以动态看排序和树的操作过程，尤其是堆排序和红黑树。不过看演示替代不了手写，我就是走了“看了很久觉得自己会了、一写就废”的弯路，才强调这个点。

个人心得是，复习数据结构最重要的是“输出倒逼输入”：你要给自己出题、给自己讲解、写下来给别人看。我这次能把这些内容整理成文，本身就是一次高强度回顾。现在你可能发现自己还有不少模糊的地方，这很正常，别急着焦虑。数据结构这门课有个特点，每巩固一遍，后面的理解就会快很多。你现在要做的不是“全部搞懂”，而是先把最容易考、最常用的内容牢牢稳住，让它们变成你脑子里的固定结构。下次再捡起来，就不会像第一遍那样吃力了。