写这篇东西之前先说说我自己的经历。当年学 C 语言的时候我一度觉得链表是个“永远绕不过去但又永远学不明白”的东西。数组用得好好的偏偏要搞个结构体还要在里面塞一个指向自己的指针然后在堆上 malloc 一块内存手动串成一串珠子。我那时候想不明白这不是脱裤子放屁吗直到后来我做了一个课设需要在循环里不断往一个动态增长的列表里插入数据数组那种“要么提前给够空间、要么每次扩容都搬一次家”的写法彻底把我折磨疯了我才意识到链表的价值。这篇就好好把链表的增删改查讲透。目标读者是正在学 C 语言、刚接触结构体和指针、准备数据结构课程设计、或者准备计算机二级、刷翁恺老师习题的同学。我会用“说人话”的方式把底层逻辑、代码实现、边界条件、还有我踩过的坑全部摊开讲。学完你不仅能看懂还能自己手写出来。1. 为什么数组不够用链表才更贴近真实世界的存储1.1 数组的三个死穴长度固定、插入拖家带口、内存碎片浪费先别急着写代码我们得先搞清楚链表到底解决了什么问题。数组不是你想象的“一劳永逸”的存储方案它有三个很要命的毛病。第一个毛病长度固定。在 C 语言里声明数组要么写死在代码里int arr[100]要么用变长数组老编译器还不一定支持要么自己 malloc 一片连续内存。问题在于你根本不知道程序运行的时候到底会有多少个数据。学生管理系统今天录入 30 个学生明天来了 300 个你的数组开多大开大了浪费开小了溢出。第二个毛病插入和删除的代价太高。数组是连续内存这意味着你要在一个有序数组中插入一个新元素得把这个位置及后面的所有元素全部往后挪一位。删除同理后面所有元素往前挪。如果你在数组头部插入元素整个数组的元素都要搬家时间复杂度 O(n)。数据量小还好数据量大了这个搬迁成本非常可观。第三个毛病内存碎片问题。如果你频繁地 malloc 一块新数组、把旧数组内容拷过去、再 free 旧数组堆上就会产生大量内存碎片。对于长期运行的程序这会导致内存利用率下降甚至分配失败。1.2 链表的本质每个节点都是“数据 线索”像一场寻宝游戏链表的思路完全不同。它不要求数据在内存中连续存放每个数据项都是一个独立的节点节点和节点之间靠指针“串”起来。每个节点里数据域存真正的数据指针域存“下一个节点在哪里”。这就像是玩寻宝游戏你手里有一张纸条上面写着“金币在第 7 个房间的保险柜里下一个纸条在 12 号房间”。你跑到 12 号房间找到下一张纸条上面又写着“下一个线索在 8 号房间”。你顺着线索一间一间跑直到最后一张纸条写着“线索到此结束”。链表增加和删除节点只需要调整相邻节点的指针指向不需要移动任何数据。这就是它跟数组最本质的区别。你插入一个新节点只需要“通知”前一个节点你的下家换人了以前是 B现在是新来的 XX 的下家才是 B。整条链上其他节点一概不用动这是数组完全做不到的。动图很多教程里有但光看图容易“眼睛会了手不会”。真正的理解发生在你亲手操作指针变量的时候。2. 先认识结构体一个节点就是一块最小积木2.1 定义节点的两种风格typedef 大法 vs 裸写 struct链表的节点是一个结构体里面至少包含两部分数据域和指针域。最经典的定义长这样struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 };这里有个小细节很多人第一遍会忽略struct Node里面有一个struct Node *next这是一个指向自身类型的指针。听起来有点绕——我举个不恰当但很形象的例子你手里有一张照片照片上是一个人举着一张照片照片里那个人又举着一张照片无限套娃。指针域就干这个事指向下一个同类型的节点。实际写代码的时候我更推荐用 typedef 起个别名不然每次定义一个指针变量都要写struct Node *p很烦typedef struct Node { int data; struct Node *next; } Node;这样后面直接用Node *p就可以了。在 C 语言里typedef struct Node { ... } Node;中struct Node是结构体标签第二个Node是类型别名。注意在结构体声明内部因为类型别名还没定义完所以next字段必须写成struct Node *next不能直接写Node *next否则编译会报错。这个坑我也踩过当时编译报unknown type name Node排查了半天。2.2 堆内存分配三件套malloc、检查 NULL、free 闭环链表的好处是可以随时动态分配节点但你得记住每个节点都是你从堆上“借”来的。C 语言没有垃圾回收借了要还。分配节点用malloc。但很多人刚学的时候只写这样Node *p (Node *)malloc(sizeof(Node));然后呢然后直接p-data 10; p-next NULL;。如果是刷题这种写法没问题但是在真实工程里如果堆内存已经耗尽malloc 会返回 NULL你在 NULL 指针上写数据程序直接崩溃。正确写法是Node *createNode(int data) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data data; newNode-next NULL; return newNode; }这个createNode函数你会在后面的所有增删改查操作中反复用到。把“分配内存 初始化”封装成一个函数是链表代码整洁的重要习惯。2.3 只建一个节点的小实验先跑通再谈链我们来做个最小实验只创建一个节点把它打印出来再释放掉#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; int main() { Node *head (Node *)malloc(sizeof(Node)); if (head NULL) return 1; head-data 42; head-next NULL; printf(节点数据: %d\n, head-data); printf(节点地址: %p\n, (void *)head); free(head); return 0; }这段代码你跑一遍体会一下“节点是内存里的一个真实对象”这种感觉。你打印出来的那个地址就是你向操作系统申请的一块堆内存。链表的所有操作本质上都是在这个地址空间上改来改去。这个基础感觉有了后面就好学很多。3. 增加节点头插、尾插、中间插三种姿势一次讲透插入是整个链表操作里最核心、也最容易出错的部分。很多人学链表学不明白就是栽在插入上。其实插入分三种情况每种情况的指针操作逻辑都不太一样我们逐个拆开讲。3.1 核心难点每插入一个节点就是告诉上一家“你的下家换人了”先理解这句话链表插入的本质就是一句话让前驱节点的 next 指向新节点让新节点的 next 指向原来的后继节点。就这么简单。关键是谁是谁的前驱、谁是谁的后继以及操作的顺序。为什么顺序重要我举个例子。假如你要在 A 和 B 之间插入一个新节点 X链表原来长这样A - B - NULL目标长这样A - X - B - NULL直觉做法是A-next X; X-next B;先改 A 的 next 指向 X再设置 X 的 next 指向 B。这个顺序有问题吗有。如果你先执行A-next X;那么 A 到 B 之间的链就断了B 节点从此“流浪”了你还找得到 B 吗找不到了因为整个链里没有任何一个指针还指向 B。这时候你再执行X-next B;但 B 已经丢了。正确顺序是先让新节点 X 指向它的后继 BX-next B;再把 A 的 next 改成指向 XA-next X;。这样 B 一直没丢。简单记新人先认清自己的下一家老人才放心把新家地址给你。3.2 头插法新节点上位头指针换人头插法就是每次把新节点插到链表头部。这个操作最简单但有个容易遗漏的细节。Node *insertAtHead(Node *head, int data) { Node *newNode createNode(data); newNode-next head; // 新节点指向原来的头节点 head newNode; // 头指针指向新节点 return head; // 返回新的头指针 }注意这两行代码的顺序不能反。如果先执行head newNode;那原来的头节点就被“抛弃”了你再也找不到它整条链断了后面的节点全部丢失。还有一个细节C 语言函数参数是值传递你在函数内部修改 head 参数并不会影响调用者的 head。所以这个函数必须把新的 head 返回出去调用时这样写head insertAtHead(head, 100);如果你忘了接收返回值新节点插不进去链表原地不动。这是新手最常见的问题之一。3.3 尾插法要踩到最后一个节点真正的 O(n) 体现在这里尾插法插到链表末尾。关键操作从头开始遍历一直走到最后一个节点p-next NULL的那个节点然后让它的 next 指向新节点。Node *insertAtTail(Node *head, int data) { Node *newNode createNode(data); if (head NULL) { return newNode; // 空链表新节点就是头节点 } Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; return head; }这里有个很重要的边界条件空链表要单独处理。如果 head 本身是 NULL你直接对 head 遍历p 就是 NULLp-next直接崩溃。所以要么特判要么用“带头节点”后面会讲来规避。尾插的时间复杂度是 O(n)因为每次都要从头遍历到尾部。如果你频繁尾插更高效的做法是维护一个 tail 指针每次尾插直接 O(1)但删除节点时需要处理 tail 指针增加了复杂度。新手阶段建议先老老实实遍历理解了再优化。3.4 中间插必须先绑新节点的后继再改前驱的下一个中间插入是指插入到某个特定位置比如“在第 k 个节点后面插入”。这个操作相对复杂因为你要先找到前驱节点。先写一个“在指定节点后面插入”的代码void insertAfter(Node *prev, int data) { if (prev NULL) return; Node *newNode createNode(data); newNode-next prev-next; // 先让新节点指向 prev 原来的后继 prev-next newNode; // 再让 prev 指向新节点 }如果是“在第 k 个位置插入”需要先遍历到第 k-1 个节点Node *insertAtPos(Node *head, int data, int pos) { if (pos 0) return insertAtHead(head, data); Node *p head; for (int i 1; i pos - 1 p ! NULL; i) { p p-next; } if (p NULL) { printf(位置无效\n); return head; } Node *newNode createNode(data); newNode-next p-next; p-next newNode; return head; }理解这段代码的关键是循环结束后p 指向的是第 pos-1 个节点也就是新节点的前驱。如果 p 为 NULL说明链表的长度不够位置越界。3.5 建议你加一个“哑节点”带头节点真的会省很多事学了一段时间链表之后你会发现每次都要特判空链表、特判头插、特判头删烦不烦烦。工程上的主流做法是引入头节点哑节点。这个节点本身不存数据它的 next 指向真正的第一个数据节点。这样一来空链表不再是没有节点而是只有一个哑节点head-next NULL。好处是巨大的头插、尾插、中间插都不需要特判“空链表”这个情况。删除操作也不需要特判“删除的是头节点”。链表的“起点”永远是 head不会因为你插删而改变。代价是浪费一个节点的内存。但这点代价完全值得。Node head; // 栈上分配哑节点不需要 malloc head.next NULL; // 所有的插入都从 head.next 开始处理当你后面总结回顾的时候会发现带头节点的写法代码更短、逻辑更统一非常推荐在课设里使用。3.6 完整可运行示例头插 尾插 遍历打印下面给一个可以直接跑起来的完整代码包含头插法和尾插法#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int data) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) exit(1); newNode-data data; newNode-next NULL; return newNode; } Node *insertAtHead(Node *head, int data) { Node *newNode createNode(data); newNode-next head; return newNode; } Node *insertAtTail(Node *head, int data) { Node *newNode createNode(data); if (head NULL) return newNode; Node *p head; while (p-next ! NULL) p p-next; p-next newNode; return head; } void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); } int main() { Node *head NULL; head insertAtHead(head, 10); head insertAtHead(head, 20); head insertAtTail(head, 30); printList(head); // 输出: 20 - 10 - 30 - NULL return 0; }跑一遍打印出来的顺序正好符合预期头插法导致 20 在 10 前面尾插法把 30 放在最后。4. 删除节点释放内存的顺序就是重点4.1 删除的本质断链 释放顺序不能反删除节点同样有两件事断链和释放内存。这两步的顺序非常关键。先说正确逻辑以删除“值为 data 的第一个节点”为例。你要删除的目标节点是cur它的前驱是prev。正确的操作让前驱的 next 直接指向目标节点的后继prev-next cur-next;释放目标节点free(cur);很多人会把顺序搞反先free(cur)再操作prev-next这就出大问题了。free(cur)意思是“这块内存我不用了还给系统”虽然 cur 这个指针变量还在但它指向的内存已经不属于你了再去读它的内容就是“野指针访问”程序行为未定义可能崩溃可能输出垃圾值可能正常——但绝对不推荐依赖这种随机行为。正确姿势是先断链再 free。断链的本质是“把它从链上摘下来”摘下来之后它就是一个孤零零的节点这时候再 free 是安全的。4.2 三种位置的删除边界条件最容易翻车删除操作的边界条件比插入更多挨个说删除头节点。头节点没有前驱所以直接让头指针指向第二个节点然后释放原头节点。这里要特别注意赋值和释放的顺序Node *deleteHead(Node *head) { if (head NULL) return NULL; Node *temp head; // 先保存要释放的节点地址 head head-next; // 头指针后移 free(temp); // 再释放原来头节点 return head; }删除中间节点。需要同时保存前驱节点和目标节点。遍历的时候用一个prev指针记录p的前一个这是链表遍历的常用套路Node *deleteByValue(Node *head, int data) { if (head NULL) return head; // 先检查头节点是不是目标 if (head-data data) { Node *temp head; head head-next; free(temp); return head; } // 遍历找目标节点 Node *prev head; Node *cur head-next; while (cur ! NULL cur-data ! data) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; // 断链 free(cur); // 释放 } return head; }删除最后一个节点。实际上不需要单独写一套逻辑因为在上面这个代码里删除最后一个节点时cur-next NULLprev-next cur-next就是把 prev 的 next 设置为 NULL链自然就断了处理好。这就是链表的好处。4.3 经典野指针问题free 之后怎么办这是很多初学者最迷惑的地方。有人问free(cur)之后要不要加一句cur NULL;我的看法是如果没有其他地方还保留着 cur 的副本就不需要。cur这个变量马上就会消失函数结束你把它置 NULL 意义不大。但是如果cur是被保存到了全局变量、或者被保存在其他结构体里那就要注意避免通过旧指针再次访问这块内存。真正容易出问题的是“释放节点之后但野指针还留在链表里”。比如你在删除时搞错了顺序free(cur)之后才让prev-next cur-next这一步读的是已经被释放的内存。为了安全我的习惯是先断链再释放立刻把局部 cur 置 NULL。如果你用的 IDE 有内存检测工具跑一遍就会发现这类错误。4.4 整体释放链表删除所有节点的正确姿势除了删除单个节点有时候你要把整条链表都释放掉。很多人会写这样的代码void destroyList(Node *head) { Node *p head; while (p ! NULL) { free(p); // 错误示例 p p-next; // p-next 已经是非法访问了 } }这个问题够经典了吧。free(p)之后p 指向的内存已经被释放再去读p-next属于典型的 use-after-free。正确做法是先保存下一个节点的地址再释放当前节点void destroyList(Node *head) { Node *p head; while (p ! NULL) { Node *next p-next; // 先把后继存下来 free(p); p next; } }这个 bug 我在实际写代码时亲眼见过不止一次。你只要记住“释放之前先留好下一位同志的地址”这一句话就不会犯这个错误。5. 查找与修改遍历是万能钥匙5.1 遍历的模板临时指针往前走头指针永远不动说增删改查前面我们把“增”和“删”讲了接下来是“改”和“查”。别看名字是两个操作它们的共同核心是遍历从头到尾走一遍链表在每个节点上做判断、做修改。遍历的模板代码长这样Node *p head; while (p ! NULL) { // 处理当前节点 p p p-next; }这个模板有个非常关键的纪律永远不要动 head 指针。很多新手遍历的时候会图省事直接用head head-next来走链表结果走完之后头指针没了链表也没了。正确做法是用一个临时指针 p 来遍历head 始终保持不变。这也是下一步所有查找和修改操作的基础。5.2 按值查找与修改学生成绩链表实战我们做一个贴近实际的例子链表里存学生的成绩信息要求查找到学号等于某个值的节点修改它的成绩。结构体稍微扩展一下typedef struct Student { int id; // 学号 int score; // 成绩 struct Student *next; } Student;查找函数Student *findById(Student *head, int targetId) { Student *p head; while (p ! NULL) { if (p-id targetId) { return p; // 找到直接返回节点指针 } p p-next; } return NULL; // 没找到 }有了查找函数修改就变得很简单void updateScore(Student *head, int targetId, int newScore) { Student *target findById(head, targetId); if (target ! NULL) { target-score newScore; } else { printf(未找到学号为 %d 的学生\n, targetId); } }看起来非常简单对吧这里我想提醒一个很多人没意识到的点findById返回的是一个指针这个指针指向链表里的真实节点所以通过它修改成员就直接改到了链表里的数据。这正是“通过指针修改结构体”的威力。如果这里返回的不是指针而是结构体副本那就白忙活了。5.3 按位置修改改第几个节点别把遍历写成死循环有时候我们要按“位置”来找节点比如“修改第 n 个节点的数据”。这里很容易犯一个边界错误我写出来你看看Node *getByIndex(Node *head, int index) { if (index 0) return NULL; Node *p head; int count 0; while (p ! NULL count index) { p p-next; count; } return p; // 可能就是 NULL }循环条件count index所以如果 index 等于 0一次循环都不走直接返回头节点如果 index 超出链表长度p 变成 NULL 退出循环返回 NULL。这是标准的“偏移 index 步”的写法不容易死循环。但如果你把条件写反了比如while (p-next ! NULL)然后 p 从头走到尾到了最后一个节点 p-next 是 NULL循环退出你会漏掉最后一个节点。这种 off-by-one 错误在链表中非常常见做题的时候特别容易栽。5.4 查找的变种倒数第 n 个节点、快慢指针初体验查找不只是找值、找位置链表中还有一类经典问题比如“找到倒数第 n 个节点”。这个用笨办法是两次遍历第一次算出链表长度第二次再走到 len-n 的位置。但更优雅的做法是快慢指针Node *findFromEnd(Node *head, int n) { Node *fast head; Node *slow head; // 快指针先走 n 步 for (int i 0; i n; i) { if (fast NULL) return NULL; // n 超出链表长度 fast fast-next; } // 快慢指针一起走快指针到末尾时慢指针就是倒数第 n 个 while (fast ! NULL) { fast fast-next; slow slow-next; } return slow; }快指针先走 n 步然后快慢指针同步向前当快指针走到 NULL 时慢指针正好在倒数第 n 个节点。这个思路第一次接触会觉得有点绕但理解了你会觉得非常巧妙。这类题做得多了你会慢慢建立起“操作链表就是操作指针”的感觉。同样的思路还可以用来找链表的中间节点快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。这就是“快慢指针”家族链表面试题里的常客。6. 手写链表最常见的五个 bug以及我建议的调试方法6.1 头插/尾插时忘记更新头指针这个是我见过的第一大 bug尤其刚学链表的人几乎都犯过。头插法里面函数内部改了 head 参数但没把新 head 返回出去调用者手里的 head 还是旧值插入就像石子扔进了水里啥也没发生。解决办法有两个一是返回新 head函数式写法就像我前面写的代码那样。二是用二级指针Node **head函数内部直接*head newNode。两个方案都可以新手建议先从返回值开始思路更直白。6.2 删除节点时先 free 再断链这个 bug 的后果非常惨烈。free 之后那块内存可能被系统回收数据被覆盖你再读它的 next 字段拿到的可能是垃圾值。而且这种问题很难稳定复现有时跑得好好的有时随机崩溃。调试时 gdb 会给你报Segmentation fault但定位到哪一行往往已经晚了。错误代码长这样// 错误示例 free(cur); prev-next cur-next; // cur 已经被释放cur-next 是野访问正确的一定是先把 cur 的 next 保存起来或者先把 prev-next 改了最后 free(cur)。这个顺序一定不要搞反。6.3 遍历判空条件写错遍历链表的时候你经常会看到两种判空条件while (p ! NULL)和while (p-next ! NULL)。它们有本质区别while (p ! NULL)会访问到最后一个节点。while (p-next ! NULL)会在最后一个节点停下此时 p 指向的是“最后一个非空节点”。很多场景比如尾插需要停在最后一个节点所以用p-next ! NULL很多场景比如打印、查找需要访问每一个节点所以用p ! NULL。把这两个搞混就会出现“少处理一个节点”或者“空指针访问”的问题。我建议你刚开始写代码时每次写 while 都问自己一句我这个循环结束后 p 应该在哪个位置。6.4 忘记检查 malloc 的返回值刷题的时候可以不检查因为刷题内存充足但课设、项目、甚至以后的嵌入式开发里malloc 失败是真实存在的。如果 malloc 返回 NULL你直接写p-data就是往 NULL 地址写数据程序直接崩溃。养成每次 malloc 后检查 NULL 的习惯不费事但很重要。提示更好的实践是把“创建节点”封装成函数在函数内部统一处理 malloc 失败的情况。这样调用方代码只需要一行createNode(data)不用每次 malloc 都写三行检查。这是代码质量提升非常实用的一步。6.5 调试利器画图 打印 gdb链表代码出 bug 时最没用的事情是盯着代码干看。我调试链表的时候只用三板斧第一板斧画图。在纸上画方框表示节点箭头表示指针。把链表当前状态画出来把每一步操作对应到图上画出新来的箭头、擦掉不要的箭头。80% 的指针错误一画图就清楚了。第二板斧写一个打印函数。每操作一步就调用printList(head)看结果是否符合预期这是最直观的手段。很多“逻辑问题”比如顺序不对、指针接错一打印就暴露了。第三板斧gdb 启动。如果你怀疑哪里崩溃编译时加-g参数用 gdb 跑到崩溃的位置用print查看相关指针的值。比如print p-next看看是不是野指针print head看看地址是否合理。学会在 gdb 里查看结构体字段print p-data排查速度能提升好几倍。调试链表还有一个原则一次只验证一个操作。不要写完增删改查四个函数再一起测试那样出了问题你不知道是哪一个函数惹的祸。我一般顺序是先写创建和遍历验证能存能读再写头插打印验证再写尾插打印验证再写删除分别测试删头、删中间、删尾、链表为空这四种情况最后再写修改和查找。每一步都验证通过才继续下一步这样写出来的代码几乎不会有难调的 bug。最后分享一点我个人的使用体验链表这个东西入门确实有点门槛但一旦跨过去你会发现它是你理解很多数据结构的钥匙。栈、队列、二叉树、图的邻接表底层都是链式结构你以后学数据库里的索引、内核里的链表、操作系统里的任务队列本质上都在跟“节点 指针”打交道。语言只是语法差异核心模型是通用的你学会了 C 语言版本的增删改查去看 C、Python 的链表实现会发现结构一样只是写法不同。最后分享一个我在实际课设里发现的细节如果你用链表存数据千万注意“释放链表”和“程序退出”之间的顺序。在课设这种小项目里程序一结束操作系统会自动回收内存很多人就偷懒不写 destroyList这能跑但会养成坏习惯。到了真实项目嵌入式、服务端长期运行的进程如果每次创建链表用完不释放内存泄漏是累积的跑几天就崩。所以每次写完增删改查记得补一个 destroyList 把整条链清掉再 valgrind 跑一遍看到 zero bytes lost你会觉得很安心。