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

说句实话上个月重新翻出当年学数据结构时的笔记我只记住了“链表”“栈”“递归”这几个词真让我写个反转链表的代码愣是盯着屏幕半天没动手。这种感觉太真实了——大学课堂上学的时候觉得都会考试也应付过去了可一旦放下几个月甚至几年脑子里的东西就像没保存过的文档一样怎么找都找不回来。相信很多人跟我一样不是没学过而是学过之后没有一个系统的复盘方式知识很快就被覆盖了。这次我决定认认真真把数据结构从头到尾重新巩固一遍。不是零基础学也不是纯粹刷题而是带着“以前学过、现在模糊”的前提重新构建知识框架。如果你正准备数据结构期末复习或者打算备考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)右边是[p1, 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 常见问题速查表症状可能原因排查思路链表打印时死循环循环链表或next指错画图核对每一步指针层序遍历输出“串层”循环用q.size()实时判断进入循环前先缓存size递归树遍历栈溢出树高度过大/递归过深改迭代栈或层序实现快排遇到基本有序数组变慢固定选基准导致分区极度不均随机选基准或三数取中哈希查找比预期慢冲突太多桶内链表过长检查哈希函数考虑扩容二分查找死循环左右边界更新规则不一致明确是闭区间还是开区间这个表是我复习时自己整理出来的每次遇到问题就加一行。收效很直接因为很多问题其实是同一类根源归纳后能避免重复踩坑。6. 最后再分享点资料、工具和我的复习心得资料这块我是这样搭配的基础概念看王道和教材代码练习靠自己敲。王道数据结构适合考研人群它的“知识点总结”和“小题题库”能帮你快速查漏补缺。李春葆老师的《数据结构教程》C语言版讲解很细代码很适合跨考或基础一般的同学。但不管你选哪本都要记得——教材是工具书不是小说不是从头读到尾就有用的你要带着问题去翻。工具方面我最常用的是Visio画图每次复习一个结构先画它的插入/删除过程画完再写代码。这个习惯让我指针层面的错误少了一半以上。可视化网站Visualgo也推荐可以动态看排序和树的操作过程尤其是堆排序和红黑树。不过看演示替代不了手写我就是走了“看了很久觉得自己会了、一写就废”的弯路才强调这个点。个人心得是复习数据结构最重要的是“输出倒逼输入”你要给自己出题、给自己讲解、写下来给别人看。我这次能把这些内容整理成文本身就是一次高强度回顾。现在你可能发现自己还有不少模糊的地方这很正常别急着焦虑。数据结构这门课有个特点每巩固一遍后面的理解就会快很多。你现在要做的不是“全部搞懂”而是先把最容易考、最常用的内容牢牢稳住让它们变成你脑子里的固定结构。下次再捡起来就不会像第一遍那样吃力了。