数据结构核心全解析：链表、栈、队列、KMP、并查集、堆与哈希表

1. 范围确定与整体认知为什么这一讲是“地基中的地基”说实话数据结构这个东西学起来不像看小说那样有快感它更像是在给你的编程能力打地基。你以后写任何像样的项目处理任何像样的数据都逃不开这些基础结构。单链表、双链表、栈、队列、单调栈、单调队列、KMP、Trie、并查集、堆、哈希表这十一块内容放在一起正好覆盖了算法题和实际工程里最常用的“零件”。这一讲适合谁三类人一是正在准备考研或者软考的同学这些考点几乎必考二是准备校招面试的程序员手撕链表、手写快排、KMP next数组推导属于高频考点三是想系统补一遍算法基础、刷题总卡壳的人很多时候卡壳的根本原因是底层结构没吃透不是题目本身难。我先给你一个整体认知以上内容可以划分成三大块。第一块是线性结构包括单链表、双链表、栈、队列它们是其他结构的基础逻辑最简单但操作细节最容易出错。第二块是优化型结构包括单调栈、单调队列、KMP它们不是新结构而是在原有结构上增加“单调性”或者“匹配规则”来提升效率解决的是特定场景下的性能瓶颈。第三块是复杂结构与映射包括Trie、并查集、堆、哈希表它们各自解决一类特定的数据组织问题。所以学习顺序也建议按这个来别跳着学。先把线性结构写熟练再做单调栈和KMP最后上复杂结构。每一步你都手写一遍、调试一遍比看十遍书都管用。2. 线性结构链表、栈、队列的底层逻辑与代码细节2.1 单链表面试手撕的重灾区单链表的概念很简单每个节点存一个值和一个next指针指向下一个节点。但为什么很多同学一上手就写错因为动态分配内存的方式在处理大量插入删除时会频繁调用 new/delete效率低而且很容易出现空指针问题。在竞赛和面试场景里更常见的做法是用数组模拟链表也就是静态链表。核心是两个数组一个 e[] 存节点的值一个 ne[] 存下一个节点的下标再用 idx 表示当前创建到哪个位置了head 存头节点的下标。头插法的代码模板大概是这样的// 数组模拟单链表 int head, e[N], ne[N], idx; void init() { head -1; idx 0; } void add_to_head(int x) { e[idx] x; ne[idx] head; head idx; } void add(int k, int x) { e[idx] x; ne[idx] ne[k]; ne[k] idx; } void remove(int k) { ne[k] ne[ne[k]]; }这里的核心思维是用下标代替指针ne[k] 指向下一个节点的下标。为什么这么做第一数组是连续内存访问快、缓存友好第二避免了动态分配的开销第三调试的时候可以直接打印数组非常直观。注意如果用动态节点的方式写删除一个节点时记得把被删除的节点空间释放掉否则会产生内存泄漏。不过笔试手撕代码时一般不会严格去看这个关键是把指针操作写对。静态链表虽然不用释放内存但也要小心 idx 越界数组开小了直接导致问题不可预知。单链表的典型应用场景是 LRU 缓存淘汰算法、邻接表存图、哈希表拉链法的冲突链等。邻接表存图可能大家最熟悉它是把每个顶点的出边连成一条单链表在遍历图的时候非常高效。2.2 双链表在插入删除上“左右逢源”双链表和单链表的区别在于每个节点多了一个 pre 指针指向前面一个节点。好处很明显有了前驱指针双向遍历很方便删除一个节点时不需要从头找到它的前驱直接就能操作。代价是每个节点多了一个指针字段内存开销更大。数组模拟双链表的模板int e[N], l[N], r[N], idx; void init() { r[0] 1; l[1] 0; idx 2; } void insert(int k, int x) { e[idx] x; l[idx] k; r[idx] r[k]; l[r[k]] idx; r[k] idx; idx; } void remove(int k) { r[l[k]] r[k]; l[r[k]] l[k]; }这里我把第0个节点当head第1个节点当tail初始时 head 的右边是 tailtail 的左边是 head。insert 函数表示在节点 k 的右边插入一个新节点 x如果想要在左边插入直接调用 insert(l[k], x) 就行。双链表的经典应用是 LRU 缓存配合哈希表可以做到 O(1) 的查找和更新这属于高频面试题了。除此之外操作系统内核里的进程管理、编辑器里的撤销操作类似文本序列的修改记录也常常用双链表来维护顺序。写双链表时最容易出错的点是插入和删除操作中指针更新的顺序。很多人写 insert 时先改了 r[k]再想用 r[k] 就发现已经不是原来的右节点了。我的建议是动手写之前先在纸上把四个指针画出来标好更新顺序再上代码基本一次就能写对。2.3 栈与队列后进先出与先进先出栈和队列是最简单的结构但也是最容易被低估的。栈的典型特征是 LIFO队列的典型特征是 FIFO。它们可以纯逻辑上理解栈像一摞盘子只能从顶端取队列像买票的队伍先来的先服务到。单纯看代码栈的实现就一个数组加一个 top 指针int stk[N], top; void push(int x) { stk[top] x; } void pop() { top--; } int front() { // 栈顶元素 return stk[top]; }队列用两个指针 head 和 tail入队时 tail 后移出队时 head 后移。循环队列还要考虑下标回绕的问题。模板int q[N], hh, tt -1; void push(int x) { q[tt] x; } void pop() { hh; } int front() { return q[hh]; }栈和队列本身简单但它们衍生出的问题一点也不简单。栈的应用包括括号匹配、表达式求值、函数调用栈、深度优先搜索队列的应用包括广度优先搜索、树的层序遍历、消息队列、任务调度。我强烈建议你动手实现一个用双栈实现队列的题以及用队列实现栈的题。这两个题非常经典考的是对两种结构特点的掌握。双栈实现队列的思路是入队时压入输入栈出队时如果输出栈为空就把输入栈所有元素倒到输出栈再从输出栈弹。这个过程中元素的“两次翻转”恰好把顺序纠正了很妙。表达式求值这块逆波兰表达式的计算是栈的典型应用。比如 “3 4 5 *”遇到数字就进栈遇到运算符就弹出两个数字、计算结果再入栈。这个流程写起来并不难难在把中缀表达式转成后缀表达式。这里简单提一句中缀转后缀时遇到数字直接输出遇到运算符要比较栈顶运算符的优先级优先级高才进栈否则先弹出栈顶再比较这个过程小细节比较多。3. 单调栈与单调队列在结构上做手脚提升效率3.1 单调栈每个元素只入栈一次单调栈是普通栈的进阶版。普通栈只保证后进先出单调栈额外保证栈中元素按某种顺序单调单调递增或单调递减。这个单调性的价值在于它能高效地找到“左边第一个比当前元素小/大”的位置。经典问题给定一个数组求每个元素右边第一个比它大的元素。暴力做法是两重循环 O(n^2)数据量一大就超时。用单调栈可以做到 O(n)因为每个元素最多入栈一次、出栈一次。维护一个从栈底到栈顶递减的栈遍历数组时如果当前元素比栈顶元素大说明当前元素是栈顶元素右边第一个比它大的元素于是弹出栈顶并记录答案如果当前元素比栈顶元素小或相等直接入栈for (int i 0; i n; i) { while (stk.size() a[i] a[stk.top()]) { ans[stk.top()] a[i]; stk.pop(); } stk.push(i); }这里我压入的是下标而不是值因为最后要定位到具体是哪个位置的答案。想出这个套路的人确实聪明它其实是用单调性淘汰掉一堆永远不可能成为答案的元素本质上是剪枝思想。单调栈能解决的问题远不止这一个。柱状图中最大的矩形、接雨水、每日温度、股票价格跨度、去除重复字母等都是它的变种。我建议把这些题集中刷一遍总结出规律凡是求“某个元素左右两边第一个比它大/小”的优先考虑单调栈。3.2 单调队列滑动窗口的最值问题单调队列和单调栈很像但它多了一个“出队”的操作而且是队头和队尾都可以操作通常用双端队列deque来实现。它的经典应用是滑动窗口最大值。题目给一个数组和一个大小为 k 的窗口窗口每次向右滑动一格求每个窗口内的最大值。暴力做是 O(nk)数据量大直接完蛋。单调队列的优化思路是维护一个从队头到队尾递减的队列队头永远是当前窗口的最大值下标。每次滑动时先检查队头元素是否已经滑出窗口如果滑出就出队然后从队尾弹出所有比当前元素小的元素再把当前元素下标入队。dequeint dq; for (int i 0; i n; i) { // 移除滑出窗口的元素 if (!dq.empty() dq.front() i - k 1) dq.pop_front(); // 保持队列递减 while (!dq.empty() a[i] a[dq.back()]) dq.pop_back(); dq.push_back(i); // i k-1 时开始记录答案 if (i k - 1) ans[i - k 1] a[dq.front()]; }每次入队都会从队尾弹出一些元素这些元素被称为“无用元素”。为什么无用因为它们在当前窗口内既比新元素值小又比新元素更早出窗口所以它们永远不可能成为最大值。这个“无用元素”的判断是整个算法的灵魂理解了这个单调队列就不再是魔板。单调队列除了滑动窗口还用于求窗口内的最小值把单调性反过来维护、求窗口内的平均值变化趋势等。记住一句话单调队列解决的问题特征是“滑动窗口 最值”其他情况基本用不上。4. 字符串与集合KMP、Trie、并查集的实现思路4.1 KMP算法next数组是核心中的核心KMP 解决的是字符串匹配问题在主串中查找模式串出现的位置。暴力匹配的时间复杂度是 O(n*m)KMP 降低到 O(nm)。它的核心思想是当匹配失败时不是让模式串从头再来而是借助 next 数组跳到一个合理的位置继续匹配。next 数组的定义next[i] 表示模式串前 i 个字符的最长相等前后缀长度。这个定义很多同学背下来了但理解不了为什么要这样。用生活化的话说你现在匹配到了模式串的第 i 个位置失败了前面 i-1 个字符是匹配上的这 i-1 个字符的后缀可能等于模式串的前缀所以模式串可以跳过这段重复的比较直接把前缀对准后缀的位置继续。以下是标准实现// 计算 next 数组对模式串求最长相等前后缀 int nxt[N]; void get_next(string p) { int n p.size(); nxt[0] 0; for (int i 1, j 0; i n; i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; if (p[i] p[j]) j; nxt[i] j; } } // KMP 匹配 void kmp(string s, string p) { int n s.size(), m p.size(); get_next(p); for (int i 0, j 0; i n; i) { while (j 0 s[i] ! p[j]) j nxt[j - 1]; if (s[i] p[j]) j; if (j m) { cout i - m 1 endl; // 匹配起始位置 j nxt[j - 1]; } } }这里有个易错点next 的推导里 while 循环中的回退条件。为什么是j nxt[j-1]而不是j--因为我们要利用已经算好的信息不需要暴力回退。nxt[j-1]表示模式串前 j-1 个字符的最长相等前后缀长度跳到那里就相当于把模式串的前缀对齐到当前后缀上直接避免了重复比较。关于“KMP 算不算动态规划”这个大家的争议我个人的理解是next 数组的计算过程利用了“已计算结果来推导下一个结果”这种“利用子问题结果避免重复计算”的思想确实跟 DP 是一致的但 KMP 通常不被归为动态规划它更常被归到“字符串匹配算法”或“自动机”那一类。考场上你不需要纠结这个分类会算 next 数组、会写匹配过程就够了。4.2 Trie树字符串集的多叉树Trie 树又叫字典树、前缀树。它的结构是把字符串集合中的每个字符作为一个节点从根节点到某个节点的路径就对应一个前缀。这种结构非常适合做“字符串前缀匹配”、“单词查找”、“词频统计”等问题。比如要插入单词 cat、car、dogTrie 的结构是根节点有三个孩子 c, dc 下面有两个孩子 a再下面有 t 和 rd 下面有 o再下面有 g。每个节点标记一个 count 或者 end 标志表示有多少个单词以当前字符结尾这样就能统计词频。int son[N][26], cnt[N], idx; void insert(string str) { int p 0; for (char c : str) { int u c - a; if (!son[p][u]) son[p][u] idx; p son[p][u]; } cnt[p]; } int query(string str) { int p 0; for (char c : str) { int u c - a; if (!son[p][u]) return 0; p son[p][u]; } return cnt[p]; }在这里 son[p][u] 其实是一个二维数组第一维是节点编号第二维是 26 个字母对应的子节点编号。为什么要开 26 列因为每个节点最多有 26 个孩子。如果字符集更大比如包含大小写和数字就要相应调整列数或者用 map 来存储孩子节点但那种做法的常数很大实际做题时一般用数组模拟。Trie 能解决的问题包括单词自动补全、拼写检查、文本词频统计、最长公共前缀、异或最大值等。异或最大值问题很有名给一组数求两个数异或结果最大值做法是把所有数按二进制从高位到低位插入 Trie再对每个数在 Trie 上贪心找尽可能不同的位每次选择相反的位走找不到就转回相同的位复杂度是 O(n*bits)比特位数一般是 31 或 63。4.3 并查集路径压缩与按秩合并并查集大概是我见过实现最短但功能极强的数据结构。它只解决一类问题动态地维护若干个集合支持合并两个集合、查询两个元素是否在同一个集合。实现上就是一个数组 fa[]fa[x] 表示 x 的父节点。查询时不断向上找父节点直到根节点合并时把一棵树的根节点接到另一棵树的根节点下面。如果不做任何优化这种做法最坏情况会退化成一条链查询复杂度变成 O(n)。所以两个优化必不可少路径压缩和按秩合并。路径压缩是在查询过程中把路径上所有节点的父节点直接指向根节点这样下次查询就是 O(1)。按秩合并是永远把小树接到大树下面树高保持在 log 级别。int fa[N]; void init(int n) { for (int i 1; i n; i) fa[i] i; } int find(int x) { if (fa[x] ! x) fa[x] find(fa[x]); // 路径压缩 return fa[x]; } void union(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) fa[fx] fy; // 简单合并 }如果在上面再加一个 rank 数组记录树的高度按秩合并int fa[N], rank[N]; void union(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; if (rank[fx] rank[fy]) fa[fx] fy; else if (rank[fx] rank[fy]) fa[fy] fx; else { fa[fx] fy; rank[fy]; } }并查集的应用极广判断图中两个节点是否连通、最小生成树 Kruskal 算法、亲戚关系判断、朋友圈问题、岛屿数量问题、动态连通性问题等。还有带权并查集可以维护集合中元素之间的相对关系比如“种类并查集”用来处理食物链问题那个问题中每个元素有三种状态A吃B、B吃C、C吃A用一个偏移向量来维护代码写起来比普通并查集长一些但思路完全相同。写并查集最容易犯的错是合并时忘调用 find、或者直接把 fa[x] y 而没找根。记住合并的对象是根节点不是叶子节点。5. 堆与哈希表高频使用的“工具型”结构5.1 堆优先队列的底层实现堆是一种特殊的完全二叉树分为大根堆和小根堆。大根堆保证每个父节点都比它的子节点大所以根节点是最大值插入和删除的复杂度都是 O(log n)而查询最值只需要 O(1)。很多语言里直接提供优先队列priority_queue底层就是堆。手写堆的代码核心就是 down 操作和 up 操作。down 操作用来把一个大值往下调整比如删除根节点后用最后一个节点补上来再从这个根节点向下调整up 操作用来把一个小值往上调整比如插入一个新值后一路和父节点比较交换。int h[N], sz; void down(int u) { int t u; if (u * 2 sz h[u * 2] h[t]) t u * 2; if (u * 2 1 sz h[u * 2 1] h[t]) t u * 2 1; if (t ! u) { swap(h[u], h[t]); down(t); } } void up(int u) { while (u / 2 h[u] h[u / 2]) { swap(h[u], h[u / 2]); u / 2; } } void push(int x) { h[sz] x; up(sz); } void pop() { h[1] h[sz--]; down(1); }堆的应用场景TopK 问题用一个小根堆维护最大的 K 个数、每次从数据流中找中位数用两个堆一个大根堆存前半段一个小根堆存后半段、Dijkstra 算法的优先队列优化、任务调度中按优先级处理任务等。让我说一个常用技巧STL 的 priority_queue 默认是大根堆如果你想要小根堆可以直接用priority_queueint, vectorint, greaterint。如果你要按自定义方式比较直接传一个比较器。实际比赛中大多数情况用 std 的 priority_queue 就够了但如果你需要维护堆中某个元素的修改、删除等操作STL 的堆做不到此时手写堆配合下标索引数组就能解决。5.2 哈希表从键到值的映射哈希表是一种极其常用的数据结构它能在平均 O(1) 时间内完成查找、插入、删除。它的原理很简单通过一个哈希函数把键映射到数组下标然后把值存在数组对应位置。哈希表的关键问题有两个哈希冲突怎么处理以及哈希函数怎么设计。处理冲突最常用的两种方法是拉链法和开放寻址法。拉链法是每个数组下标挂一个单链表或者使用头插法存冲突的元素开放寻址法是如果当前位置被占了就按某种探测顺序找下一个空位。竞赛里常用拉链法模拟哈希表因为实现简单、调试方便int h[N], e[N], ne[N], idx; void insert(int x) { int k (x % N N) % N; // 处理负数取模 e[idx] x; ne[idx] h[k]; h[k] idx; } bool find(int x) { int k (x % N N) % N; for (int i h[k]; i ! -1; i ne[i]) { if (e[i] x) return true; } return false; }注意负数取模的问题C 里负数取模可能得到负数所以要加一个模数再取模保证下标非负。N 一般取比较大的质数比如 100003这样可以减少冲突。为什么选质数因为如果哈希表的长度是合数容易在一些特殊数据下变得不均匀。哈希表在工程和算法中的应用太多了统计词频、缓存系统、去重、数据库索引底层哈希索引、两个数组的交集、最接近的三数之和等。Java 里的 HashMapPython 里的 dictC 的 unordered_map底层都是哈希表。标准库里的 unordered_map 是竞赛和工程最常用的哈希容器。但注意它的遍历顺序是不确定的如果你需要按插入顺序或者键的顺序访问就得用 map红黑树或者额外维护一份顺序信息。6. 常见问题排查与避坑心法6.1 边界条件与数组越界学这章内容时我见过最多的问题不是算法不懂而是数组越界和边界判断出错。比如数组模拟链表时idx 可能超出数组范围单调队列里忘记判断队头是否滑出窗口KMP 求 next 时j 的回退条件写成j--而不是j nxt[j-1]。这些都是细节问题但每个都能让你调试到怀疑人生。我的建议是每道题的代码完成后拿小数据手动走一遍特别是空数组、单元素数组、全部相同的元素、全部逆序等极端情况。比如滑动窗口的 k 等于 1 或等于数组长度时单调队列应该依然正确KMP 匹配时如果模式串长度大于主串应该返回空结果而不是越界访问。调试的时候用 cout 打印中间状态也是一种好方法。比如写链表时把整个链表的节点值从 head 打印一遍检查删除操作后链表的顺序是否符合预期写单调栈时打印栈内元素的下标观察弹出和压入的逻辑。不要觉得打印很 low很多时候它比断点调试更快。6.2 时间复杂度的敏锐度这些数据结构的存在价值和它们的复杂度是绑定的。我强烈建议你在学每种结构时一边写代码一边默念它的复杂度单链表头插O(1)任意位置插入需要 O(n) 找到位置栈的入栈出栈O(1)队列的入队出队平均 O(1)单调栈每个元素入栈出栈各一次总体 O(n)单调队列每个元素入队出队各一次总体 O(n)KMP匹配过程 O(nm)求 next O(m)Trie插入和查询时间复杂度 O(字符串长度)并查集路径压缩 按秩合并后基本可以认为是常数级别的摊还复杂度堆插入和删除 O(log n)哈希表平均 O(1)最坏 O(n)这些复杂度要像记九九乘法表一样记熟。刷题的时候读完题目第一反应不是“用什么算法”而是“数据范围多大什么复杂度能过”。比如 n 在 10^5 量级时O(n^2) 很可能超时这时候你就要想 O(n log n) 的堆或者 O(n) 的单调方法而不是上来无脑暴力。6.3 编码习惯与细节规范再强调几个编码习惯。第一变量命名要清晰在算法题里虽然不影响正确性但对你自己调试有好处。y 总AcWing 创始人闫学灿的代码风格就是一个典型head、idx、ne、e、cnt 这些名字非常短但看多了就形成了一套清晰的“暗号”。第二注意初始化。数组模拟结构时head 初始化为 -1idx 初始化为 0并查集的 fa 数组要 init 成每个元素指向自己。这些初始化漏了输出结果就会出现匪夷所思的错误。第三循环里注意指针的更新逻辑。单链表删除节点时不管是用新的 head 还是用第 k 个节点后删都要先保存一下 next 的值再做指针修改。调试的另一大法宝是对拍。写一个暴力解法再写一个优化解法用随机数据跑几千组比较两者的输出。这个技巧在竞赛圈非常常用平时练习时错过一次就会长记性。对拍代码并不复杂写一个数据生成器生成随机数组然后分别跑暴力程序和优化程序用 diff 比较输出。7. 本文总结与个人体会我的最大体会是这些数据结构的学习只看书是远远不够的。你必须在限定时间内把代码写出来写出来的过程中才能真正理解那些“为什么”。比如为什么要用静态数组模拟链表因为频繁调用 new 会拖慢速度。为什么并查集要路径压缩因为不压缩会退化。为什么 KMP 的 next 数组用前缀函数来定义因为匹配失败后段字符串已经匹配上了模式串可以平移前缀的位置来继续比较。所以别怕手敲代码更别怕报错。每写完一个结构试着给自己出几个小题目验证它的正确性。过几天再回头写一遍看自己还能不能独立写出来。遗忘是人的正常规律但只要写过的代码留在肌肉记忆里再次拾起来会非常快。最后再分享一个小方法把这章内容做成一份“默写清单”先把模板背下来再重新推导一遍。比如今天默写一遍单链表和双链表明天默写一遍单调栈和队列后天默写一遍并查集和 KMP连续一周你的基本功就稳固了。等到面试或考试前再快速过一遍清单你会发现自己已经不需要翻书了。祝你一路打怪升级顺利数据结构这块硬骨头一旦啃下来后面写算法题和工程代码都会顺畅很多。