先问个问题你在几百页的文档里用 CtrlF 搜索一个关键词为什么能秒出结果因为文档在内存里是按顺序排好的系统知道每一页大概在哪个字节位置顺着下标直接跳过去就行。顺序表干的就是这件事——数据在内存里紧挨着排想要第几个元素用下标一下就能定位。链表呢它更像小时候玩的那种“寻宝纸条”每张纸条上写着下一个线索放在哪里你要找第 100 张纸条就得从第一张一路看过去没法跳。但它的好处是想在中间塞进一张新纸条只要改前一张上面的地址就行不用把后面所有纸条都挪一遍。很多初学者把顺序表和链表当成两个需要背代码的考点实际上它俩是整个数据结构体系的基石也是理解算法复杂度、指针操作、内存布局的第一课。这篇文章会从建立、遍历、插入、删除这些基本功讲起再深入逆序、排序、相交这些进阶玩法最后把 C/C 里那些容易踩坑的细节一次性说清楚。不管你是刚学数据结构的大学生还是准备面试的求职者或者单纯想补基础的开发者应该都能从里面捞到不少干货。1. 顺序表为什么随机访问这么香1.1 底层逻辑连续内存如何换来“到点直达”顺序表本质上就是一个数组或者说一组在物理地址上连续存放的数据。正因为连续它才有了一个其他结构很难替代的能力随机访问。a[i]这条语句在底层做的事情其实是*(a i)也就是用首地址加偏移量直接算出目标地址。整个过程不需要遍历不需要跳转一步到位。这也是为什么“查找第 k 个元素”这种操作在顺序表里是 O(1)。这个特性在刷题和实际工程里都很关键。比如你有一组学号用户随时会问“第 100 个是谁”如果用顺序表直接输出a[100]就完了如果换成链表你得从头节点一路数到第 100 个节点。同样是查询一个瞬间出结果一个和总长度成正比数据量一大差距就是几十万倍的差别。不过有得就有失。顺序表的代价在于插入和删除。想在数组中间塞一个新元素后面的所有元素都得往后挪才能腾出位置想删掉中间一个元素后面的元素又得往前补。这个“挪动”的过程时间复杂度是 O(n)。如果你做的操作里查询多、改动少顺序表就是最佳选择。1.2 建立顺序表静态数组和动态分配两条路建立顺序表最朴素的方式就是声明一个数组。比如题目告诉你最多有十万个元素那直接写int arr[1000005]就行省事、不容易错。但这种方式的问题是“长度写死了”如果数据规模超出预期数组就越界了。所以更灵活的方式是用malloc动态分配int* arr (int*)malloc(sizeof(int) * capacity);动态分配的好处是可以向用户输入的实际规模看齐内存不够了还能用realloc扩容。如果你写 C标准库里的vector已经封装好了扩容逻辑平时直接用vector就行面试追问底层原理的时候再手写一遍动态扩容也不亏。要注意的是建立顺序表的时候习惯上会把“当前有效元素个数”单独记下来写成size之类的变量。因为数组的真实容量可能很大比如 100 万个但真正用到的只有前 100 个遍历的时候一定要用size去限定范围而不是用容量。这个细节初学的时候特别容易弄混一弄混输出的就是一大串未初始化的内存垃圾。1.3 插入与删除移动元素的代价和边界顺序表的核心操作是插入和删除也是考试最喜欢考的算法题思路。先说插入。假设当前有size个元素要在下标pos的位置插入一个值val那么从最后一个元素开始依次往后移动一位直到把pos位置空出来再赋值for (int i size; i pos; i--) { arr[i] arr[i - 1]; } arr[pos] val; size;循环必须从尾部开始倒着走。如果正着来从pos位置开始把后面的元素往后赋值前面被覆盖的值就丢了数组会出现大段重复数据。这是新手必踩的坑我见过很多次。删除则是反过来的方向。要删掉下标pos的元素应该让后面的元素从前往后覆盖前面的for (int i pos; i size - 1; i) { arr[i] arr[i 1]; } size--;边界条件也要特别注意插入前要检查pos是否在合法范围内还要看size是否等于容量满了得先扩容删除前要检查size是否为 0。凡是遇到数组操作先把边界想清楚再写循环能少调半天 bug。1.4 实战洛谷 P3156 为什么是顺序表的主场洛谷的 P3156【深基15.例1】询问学号是个很典型的顺序表应用题。题目大意是先读入 n 个学生的学号然后有 m 次询问每次给一个位置要求输出该位置学生的学号。n和m都能到十万级别。这种“给位置查数据”的场景正是顺序表最擅长的。每个位置对应一个下标直接输出arr[k]就是 O(1)十次二十次查询都是瞬间完成。如果非要用链表模拟每次查询都得从头遍历到第 k 个节点单次 O(k)最坏情况一次查询就是十万次运算整体效率差出好几个量级。代码也非常简单#include stdio.h int main() { int n, m, k; scanf(%d %d, n, m); int a[1000005]; for (int i 1; i n; i) { scanf(%d, a[i]); } while (m--) { scanf(%d, k); printf(%d\n, a[k]); } return 0; }这里数组开得比 n 稍大是为了防越界。下标从 1 开始是我个人的习惯因为题目里的“第 k 个”通常都是 1-based这样不用做k-1的转换写起来反而少出 bug。当然从 0 开始也完全没问题关键是统一别一会儿 0 一会儿 1 把自己绕晕。2. 链表指针操作的核心与习惯2.1 结构体链表的定义与创建链表和顺序表最大的区别是它不要求数据在物理上连续。每个节点独立存在节点之间用指针串联起来。C 语言里定义一个单链表节点很直接typedef struct Node { int data; struct Node* next; } Node;注意struct Node后面一定要带上这个结构体名字本身因为next指针的类型必须靠它才能指回去。很多人刚学的时候写成typedef struct { int data; Node* next; } Node;是编译不过的因为Node这个名字还没定义完就被拿来用了。先给结构体命名再 typedef顺序不能乱。创建节点的时候malloc之后一定要检查返回值。内存不足时malloc会返回NULL如果不判断直接往里写程序秒变段错误。同时新节点创建出来之后next一定要初始化要么指向某个真实存在的节点要么置为NULL。新手最容易漏掉初始化结果一打印就访问到野指针性能再好也白搭。2.2 头插法和尾插法建链的两种姿势建立链表主要有两种方式头插法在链表头部插入新节点和尾插法在链表尾部追加新节点。头插法的代码很紧凑但注意它会逆序输出数据Node* head NULL; for (int i 1; i n; i) { Node* p (Node*)malloc(sizeof(Node)); p-data i; p-next head; head p; }每来一个新节点都塞到头部去。如果输入是 1、2、3最后链表里存的是 3、2、1顺序反了。所以头插法适合快速建链或者你本来就想逆序处理的场景如果想让链表保持输入顺序得用尾插法Node* head NULL; Node* tail NULL; for (int i 1; i n; i) { Node* p (Node*)malloc(sizeof(Node)); p-data i; p-next NULL; if (tail NULL) { head tail p; } else { tail-next p; tail p; } }尾插法的关键是用一个tail指针记住最后一个节点每次新建节点直接挂到tail后面再更新tail这样不用每次都从头遍历找尾巴建链复杂度是 O(n)。这是效率上很重要的优化很多教材不会强调但在链表很长的时候区别非常明显。2.3 插入、删除、遍历的三个基本功链表的插入核心是两步先把新节点的next指向后一个节点再让前一个节点的next指向新节点。顺序绝对不能反必须先接后继再改前驱。如果先改了前驱的next原来的后继就找不到了整条链直接断掉。代码示例// 在 p 节点后面插入值为 val 的新节点 Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next p-next; p-next newNode;删除节点刚好相反要先把待删节点的后继保存下来再让前一个节点绕过它最后free。如果先 free 再取next读到的就是已经释放的内存行为完全不可预知Node* tmp p-next; p-next tmp-next; free(tmp);遍历链表就更基础了核心条件是while (p ! NULL)。每一步先处理p-data然后执行p p-next让指针向后移动。很多新手会忘记最后一步结果就是死循环亲眼见过有人调了半小时都没发现只是少了这一行。2.4 一个容易被忽略的优化哑节点链表操作里有一个非常实用的技巧在头节点之前额外加一个“哑节点”也叫 dummy node。这个节点自己不存有效数据它的next才指向真正的第一个节点。有了哑节点头插、在第一个位置插入、删除第一个节点这些操作就都能统一成“在某个已知节点后面操作”不需要单独写一堆关于头指针是否为空的特判逻辑。比如删除某个位置的节点时如果没有哑节点删除首节点你得单独更新head有了哑节点你只需要找到待删节点的前驱然后执行同一条删除操作。代码会简洁很多也少了很多出 bug 的机会。刷题的时候这个思路尤其香很多链表题加上哑节点后思路一下子清晰了。3. 进阶操作逆序、排序、相交3.1 单链表逆序三指针迭代到底在做什么单链表逆序是面试高频题也是检验链表是否真的理解透彻的试金石。核心思路是三个指针prev指向已逆序部分的头部curr指向当前要处理的节点next暂存curr原本的下一个节点。Node* reverseList(Node* head) { Node* prev NULL; Node* curr head; while (curr ! NULL) { Node* next curr-next; curr-next prev; prev curr; curr next; } return prev; }为什么需要next因为当你执行curr-next prev之后原本指向后继的那条路就被改掉了如果不提前存下来后面curr next这一步根本不知道该往哪走。很多人看代码能看懂但自己写的时候就是想不起来要加next这个临时变量多画几遍链表指针变化的图就能想明白。这个操作的本质是把所有边的方向都调转一遍。prev最后停在新链表的头部所以直接返回prev就行。这个思路还能直接迁移到“判断回文链表”的场景先用快慢指针找到中点把后半段逆序再和前半段一个个比较。3.2 链表排序归并排序为什么比冒泡合适链表排序也是个老话题了。很多初学者第一反应是冒泡排序挨个交换相邻元素的值。这个思路脑子上很简单但真实现起来很别扭因为链表找“前一个节点”比数组麻烦多了值交换倒是容易节点交换的指针操作会让你怀疑人生。链表的天然友好排序算法是归并排序。它不需要随机访问只需要能够“把链表分成两半”和“合并两个有序链表”这两个操作链表都能高效完成。找一个链表的中点用快慢指针非常方便快指针每次走两步慢指针每次走一步快指针走到头慢指针正好在中点。Node* sortList(Node* head) { if (head NULL || head-next NULL) return head; Node* slow head; Node* fast head-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } Node* mid slow-next; slow-next NULL; Node* left sortList(head); Node* right sortList(mid); return merge(left, right); }merge就按合并两个有序链表的经典逻辑写谁的data小谁先挂到结果链表上。这里注意一个细节找中点时fast head-next而不是head这样当链表只有两个节点时slow会停在第一个节点mid指向第二个分两半才不会死循环。这种边界条件就是刷题时最容易卡住人的地方。3.3 链表相交双指针思路与变体“链表相交”问题在 LeetCode、热门题库里经常出现比如“3898 · 链表相交(二)”这类题本质上就是给你两个单链表找它们第一个公共节点。最优雅的解法是双指针两个指针分别从两个链表头出发走到末尾后跳到另一个链表的头继续走最终它们一定会在交点相遇或者同时走到空。为什么能相遇因为两个指针走过的总路程是相同的都等于两个链表的长度之和。一个更直观的说法是把两个链表分别接在对方后面这样两条“新链表”长度一样尾端对齐交点之前的长度也相等所以两个指针会同步到达交点。这招网上一搜一大把但你要是不亲手画一遍图很难真正建立直觉。实在记不住双指针也可以老老实实先算出两个链表的长度差让长的那个先走差值步然后两个指针一起走找到第一个相同节点。这个方法实现起来更直观也很好讲给面试官听。4. C/C 实现时容易踩的坑4.1 运算符优先级p-next 和 (*p).next 的关系很多人写链表代码写着写着遇到一个很奇怪的问题*p.next编译不过或者运行结果完全不对。原因很简单——运算符优先级。在 C/C 里.和-的优先级高于*所以*p.next等价于*(p.next)编译器以为你想先访问p的next成员再对这个指针取值。可问题是p本身是个指针指针怎么直接用.访问成员呢于是编译报错。正确的写法是(*p).next先用括号把*p括起来表示“先取出p指向的那个结构体再访问它的 next 成员”。不过实际代码里很少有人写(*p).next太啰嗦了C 语言专门提供了-这个运算符用于指针访问成员p-next和(*p).next完全等价。遇到表达式混在一起的时候别硬猜优先级逮住编译器报错就是最快的指向。多看几遍 C/C 的运算符优先级顺序表把这些高优先级的家伙刻进脑子里能少踩很多坑。4.2 内存管理分配与释放必须配套链表每一个节点都是通过malloc或new动态分配的用完以后必须记得释放。C 语言对应freeC 对应delete。只分配不释放程序跑得越久内存占用越高最后直接卡死或者被系统杀掉。释放一整条链表的时候也要小心常见错误是“先 free 当前节点再通过它找下一个节点”。释放之后那块内存已经交还给系统再读它那就是访问悬空指针。正确做法是先存好nextvoid freeList(Node* head) { Node* curr head; while (curr ! NULL) { Node* tmp curr-next; free(curr); curr tmp; } }另外free之后把指针置成NULL是个好习惯。释放后指针自己还在原来的地址上一不小心继续用就会出严重问题。把指针置空再操作就会直接段错误反而能暴露出逻辑 bug。4.3 二级指针修改头指针的正确姿势写链表操作函数的时候如果你要修改头指针本身就会遇到一个很经典的问题普通传参无法影响外面的head变量。C 语言是值传递函数内部操作的是head的副本改来改去外面的head纹丝不动。解决办法有两种。第一种是函数返回新头指针调用处重新赋值Node* insertAtHead(Node* head, int val) { Node* p (Node*)malloc(sizeof(Node)); p-data val; p-next head; return p; }第二种是传二级指针函数内部通过指针修改外面的变量void insertAtHead(Node** head, int val) { Node* p (Node*)malloc(sizeof(Node)); p-data val; p-next *head; *head p; }二级指针看似复杂其实原理很简单想在函数里修改一个int就传int*想在函数里修改一个Node*自然就传Node**。想通了这一点再看到链表代码里的head就不会发怵了。5. 顺序表 vs 链表到底怎么选5.1 时间、空间、缓存三张账单选择用顺序表还是链表本质上是在算一笔账你到底需要频繁做什么操作每种操作的成本是多少操作顺序表单链表按下标随机访问O(1)O(n)头部插入O(n)O(1)尾部插入均摊 O(1)O(1)需尾指针任意位置插入O(n)要移动O(n)要找到位置删除任意位置O(n)O(n)要找到前驱内存空间连续可能有空闲浪费每个节点多存一个指针还要按需分配空间上顺序表有预分配容量的浪费链表每个节点多一个指针开销两者各有毛病。还有一个很重要的因素容易被忽视缓存局部性。顺序表数据在内存里紧挨着CPU 加载一块内存时经常会把它附近的数据一起装进缓存所以遍历顺序表的速度通常比遍历链表快很多。链表节点在内存里东一个西一个每次跳转都可能触发一次缓存未命中性能差距在数据量大的时候会非常明显。5.2 刷题和工程里的选择经验刷题的时候我个人的习惯是如果题目只是给一组数据然后各种下标查询无脑选顺序表也就是直接用数组或vector又快又稳如果题目明确要求频繁在头部或中间插入删除节点那就用链表或者用链表的思想去模拟。在真实工程里C 的std::vector和std::list分别对应顺序表和链表。大多数场景下vector是默认选择因为随机访问高效、缓存友好尾部插入也很快。只有当你明确知道需要大量中间插入删除、并且对快速定位不敏感时才值得用list。当然实际项目还要考虑内存碎片、线程安全、迭代器失效等更复杂的问题但在学习阶段先把时间复杂度和缓存这两本账算明白就已经领先很多人了。5.3 Python 视角单链表逆序为什么更直观热词里有人搜“python单链表逆序”这里顺便说一下。Python 没有 C/C 那种显式的指针而是用对象引用所以链表节点通常用类来定义class ListNode: def __init__(self, val0, nextNone): self.val val self.next next逆序代码思路和 C 语言完全一致只是不需要malloc和free换个变量名就能直接用def reverseList(head): prev None curr head while curr: next_node curr.next curr.next prev prev curr curr next_node return prevPython 里写链表更接近“描述算法思想”少了很多内存管理的负担所以很多初学者觉得 Python 版更容易理解。但我的建议是不管用哪种语言都要亲手把 C 语言版写一遍。因为只有手动管理过内存、踩过段错误的坑你才能真正理解“指针”“引用”“生命周期”这些概念到底在讲什么。用 Python 理解思想用 C 练基本功两条腿走路效果最好。6. 常见问题与排查技巧实录6.1 三大典型故障的排查思路学链表最容易碰到的问题就三个段错误、死循环、输出结果乱序。排查顺序每次都是一样的先检查指针是不是 NULL再检查遍历指针有没有往后移动最后检查每个节点的next初始化了没有。段错误八成发生在访问了无效内存要么malloc后没检查返回值要么free后又继续用了要么遍历时访问了空指针的成员。解决方法是加打印在每一步操作前后打印当前节点的地址和值看是哪个节点出了问题。死循环基本是遍历条件写错了。有人写while (p-next ! NULL)而不是while (p ! NULL)结果最后一个节点永远处理不到或者处理完了也停不下来。还有人把p p-next写在条件判断里写完自己都分不清什么情况下会停。输出乱序也不难排查先确认建链方式尾插法保持输入顺序头插法会逆序再看遍历用的指针有没有从头开始有人遍历完一次忘了重置头指针第二遍就从中间开始输出了怎么看怎么诡异。6.2 问题速查表现象可能原因解决方法段错误malloc后没检查NULL分配后立即判断段错误访问空指针的下一个节点遍历前判断指针非空段错误使用已free的内存free后指针置NULL死循环遍历循环里没有p p-next在循环体末尾移动指针死循环链表成环检查插入操作是否误把next指回前面输出顺序反了用了头插法建链改用尾插法或主动逆序输出多出乱码新节点next未初始化创建节点后立即置NULL删除后链断先free再取next先保存后继再free6.3 我自己写链表代码时坚持的习惯最后分享几个我多年写链表代码时坚持的习惯都是用教训换来的。第一每次创建完节点第一件事就是给data和next赋值不要让它带着随机值进入逻辑。第二凡是涉及“修改某个节点的 next 指向”的操作先画一个简单的箭头图明确哪个指针现在指向哪里改完之后应该指向哪里图能画出来代码自然就写出来了。第三写while循环之前先想清楚循环结束的条件是遍历到最后节点此时当前指针为 NULL还是正好停在最后一个节点此时 next 为 NULL这两个条件混用是死循环和漏处理的头号来源。还有一点调试链表代码时别急着上复杂工具用printf打印每一步的节点地址和值比调试器更好用因为看得到整个访问序列问题一眼就看得出来。等逻辑完全跑通之后再把打印删掉也不迟。说实话顺序表和链表这俩东西初学的时候很容易不耐烦觉得又简单又无聊。但我带过不少新人发现一个规律凡是能独立把这两样写利索、能讲清楚每一步为什么这么写的人后来学树、图、哈希表都明显快得多。原因很简单树是链表的扩展图是树的扩展而复杂度分析、指针操作、边界处理这些基本功全都是从这两个最基础的结构里练出来的。如果让我给一个学习顺序建议那就是别在看完文章之后觉得自己会了。打开编辑器从零写一遍顺序表的插入删除再写一遍单链表的头插、尾插、删除、逆序。写的时候把每个变量的状态画在纸上错了就一步一步对着打印输出检查。等你不用查资料也能把代码写出来并且能说清楚每个边界条件为什么这样处理这一关才算真正过去。下一步想进阶可以试试用链表实现一个简单的 LRU 缓存或者用数组实现循环队列再或者去看看跳跃表是怎么通过多层链表让查找变成 O(log n) 的。这些本质上都是在顺序表和链表这两个地基上长出来的地基打牢了上面盖什么楼都不慌。