如果你正在学C语言大概率会在结构体和指针那里卡一阵子等把这两个搞明白了紧接着遇到的拦路虎就是链表。链表这个东西说难不难说简单也不简单它几乎是所有数据结构教材的第二章或第三章内容也是很多计算机专业学生第一次感受到“指针居然还能这么用”的地方。更关键的是链表的增删改查四个操作看起来只有几十行代码却能把动态内存管理、指针操作、边界条件、空指针判断这些问题全揉在一起写错一个地方程序直接崩溃给你看。这篇文章我会带着你从数组的痛点说起然后逐个实现链表节点的创建、插入、删除、查找、修改和销毁把每一步操作背后的原理、细节、坑点都讲清楚。不管你是刚学完C语言基础准备进阶的初学者还是需要复习数据结构的考研党、面试党这篇文章都能帮你把单链表这块硬骨头啃下来。1. 链表到底解决什么问题从数组的痛点说起要说链表得先从数组说起。很多初学者不理解明明数组用得好好的为什么要搞出链表这么个东西多此一举。其实不是的数组在固定长度、连续内存的使用场景下确实很好用但一旦涉及动态增删它就会暴露出一堆问题。1.1 数组的“固定床位”问题数组在创建的时候必须指定长度。你开int arr[10]它就固定占 10 个 int 的空间。这在很多场景下是麻烦的数据量不确定开小了装不下开大了浪费内存。你说用动态数组malloc一波那也得先知道大概需要多少个元素分配完之后想扩容还得重新开一块更大的内存再把旧数据搬过去。更麻烦的是插入和删除。假设你有一个有序数组[1, 3, 5, 7, 9]现在要在 3 和 5 之间插入一个 4正常做法是把 5、7、9 全部往后挪一位再把 4 填进去。删除也是同理后面所有元素都要往前移。这种搬移操作的时间复杂度是 O(n)数据量大了之后性能很难看。你可以把数组想象成电影院里的一排固定座位座位号就是下标观众必须一个挨一个坐着。这时候有个人想插队坐到正中间那么从中间到末尾的所有人都得起来挪位置。同理有人中途离场后面的人也要往前补位。链表就不一样了它更像排队时每个人只记住自己后面那个人是谁有人插队只需要改一下前面那个人“记住的人”就行后面的人完全不用动。1.2 链表的核心设计用指针把节点串成一条链链表的思路很简单每个节点不仅保存数据还额外保存一个“指向下一个节点的指针”。这样节点之间就不需要连续存放了每个节点想放在内存的哪个位置都可以只要指针能把它们串起来就行。一个单链表节点长这样typedef struct Node { int data; // 数据域存放实际数据 struct Node *next; // 指针域指向下一个节点 } Node;链表的第一个节点叫头节点通过一个头指针head来记录它在哪里。最后一个节点的next指向NULL表示链到这里就结束了。所以在链表中做增删改查本质不是搬数据而是改指针。插入一个新节点就是把新节点的 next 指向后一个节点再把前一个节点的 next 指向新节点删除一个节点就是让前一个节点跳过它直接指向后一个节点然后把这个节点 free 掉。这两种结构的差异直接决定了它们在不同操作上的表现。我习惯用一张表来对比操作数组单链表按下标访问第 i 个元素O(1)直接算地址O(n)必须从头遍历在已知位置插入元素O(n)需要搬移元素O(1)已知前驱节点后删除已知元素O(n)需要搬移元素O(1)已知前驱节点后按值查找O(n)O(n)内存空间连续可能浪费不连续额外存指针有开销数组擅长随机访问链表擅长频繁增删这俩是互补关系。明白这一点你就知道链表存在的理由了。1.3 单链表、双链表、循环链表怎么选链表家族里还有几个兄弟单链表、双向链表、循环链表。初学者先把单链表吃透后面学另外两种就轻松很多。单链表是最基础的每个节点只有 next 指针只能从头往后走不能回头。因为它最简单所以很多教材、面试题、考试题都拿它开刀。缺点是删除一个节点时你必须知道它的前驱节点是谁否则单链表删不了这一点后面会重点讲。双向链表在每个节点里多了一个 prev 指针指向前一个节点。这样一来删除节点就不需要找前驱了因为每个节点自己就存着前驱的地址。代价是每个节点多花一个指针的内存插入和删除时多改一行指针操作。Linux 内核里大量使用的就是双向链表不过内核那种链表和教材这种写法还不太一样它是把链表节点嵌到结构体里面去的。循环链表就是把尾节点的 next 指向头节点形成一个环。它适合那些需要循环轮转的场景比如约瑟夫环问题、操作系统的进程调度轮转、内存管理中的页置换等。我个人建议先把单向链表的手写代码练到滚瓜烂熟做到随堂测验能在十分钟内写出创建、插入、删除、遍历的完整代码再去看双向链表和循环链表。单链表都搞不定后面全是空中楼阁。2. 动手前的关键设计结构体、头节点与内存管理写链表代码之前有几个设计决策需要先想清楚。很多初学者上来就敲代码结果连头节点要不要、传参要不要用二级指针这些问题都没想明白写着写着就开始怀疑人生。这部分我们先把设计层面的问题解决掉。2.1 用结构体定义节点为什么 next 要写成 struct Node*先看这个经典的节点定义typedef struct Node { int data; struct Node *next; } Node;这里有个初学者常见的疑问都已经 typedef 成 Node 了为什么成员变量 next 不能用Node *next非要写struct Node *next原因很简单C 语言是顺序编译的编译器看到struct Node里面的成员时typedef的别名Node还没定义完。你自己想想Node这个别名还没诞生你就在结构体内部用它声明成员编译器当然不认。所以必须显式写struct Node *next等整个结构体定义结束Node这个别名才生效。另外注意数据域不一定是 int。你可以把它换成 double、char甚至是一个结构体。比如学生管理系统里你可以定义typedef struct Student { char name[20]; int id; float score; } Student; typedef struct Node { Student data; struct Node *next; } Node;更高级一点的做法是数据域用void *data这样链表可以存任意类型的数据但这种写法对初学者来说有点绕建议先把固定类型练熟。2.2 头节点到底要不要一个关键的设计决策这里说的“头节点”不是指第一个存储数据的节点而是指一个“哑节点”dummy node它自己不存有效数据只是作为链表的起点存在。因为它在链表最前面可以让所有插入、删除操作在逻辑上保持一致不需要特判“这是不是链表头”。举个例子如果你不用头节点删除第一个节点时头指针 head 本身需要更新因为原来指向第一个节点的 head 现在要指向第二个节点。这个操作牵扯到头指针的修改所以函数形参必须用二级指针Node **head或者让函数返回新的头指针。很多初学者在这里栽跟头就是因为忘了更新 head导致链表头丢了。如果用头节点head 始终指向那个哑节点不管删哪个节点头指针本身都不会变代码就少了很多特判。我做了一个对比表设计方式优点缺点不带头节点结构直观节省一个节点的内存删除/插入头节点时要更新头指针代码逻辑复杂一点带头节点插入删除逻辑统一不需要特判头节点多一个哑节点遍历时要注意跳过它后面我的完整代码会采用“不带头节点”的写法因为这是教材和面试里最常见的版本你练熟了之后再看带头节点的写法会非常轻松。2.3 malloc/free 配对链表的生命线链表节点是动态分配的每个节点都是用malloc在堆上申请的用完之后必须用free释放。这句听起来简单实际写代码时很多人根本不 care。每写一个malloc你就要问自己这个内存什么时候释放、在哪里释放、如果中途出错返回了这个节点会不会泄漏。这里有几个硬性规矩每次malloc之后必须判断返回值是不是NULL。虽然平时跑不出来但在嵌入式环境或者内存紧张的系统里分配失败是真实存在的。每次free一块内存后那个指针应该尽快置空或者不再使用否则就成了悬空指针。绝对不要对一个指针free两次那是未定义行为程序大概率直接崩。链表的增删改查之所以让人头疼就是因为这些内存管理细节和指针操作搅在一起。你不仅要保证逻辑正确还要保证内存安全。我见过很多同学代码逻辑看着没问题一跑就崩或者跑一次内存涨一点最后发现是free的位置不对。提示写链表代码前先在脑子里把“谁 malloc 的、谁 free 的”这条线理清楚再动手。3. 完整实现链表增删改查的四个核心操作接下来是重头戏。我会按 创建 → 插入 → 删除 → 查找 → 修改 → 销毁 的顺序把每个操作的核心代码和设计思路讲清楚。建议你边看边在本地编译器上敲一遍光看不练十有八九还是不会。3.1 准备工作节点创建与打印函数所有插入操作之前先得有个创建节点的函数。这个函数负责开辟内存、填充数据、把 next 置成 NULLNode* createNode(int data) { Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data data; newNode-next NULL; return newNode; }为什么要把创建节点单独抽成一个函数因为插入、尾插、指定位置插入都要创建新节点如果每处都写一遍 malloc 和判断代码会非常冗余而且容易漏掉对 malloc 返回值的检查。再配一个打印函数这个函数看着简单却是调试链表的利器void printList(Node *head) { Node *cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); }printList会从 head 开始依次打印每个节点的 data最后打印一个 NULL 表示链表结束。你每做完一次插入或删除就调用一次 printList就能立刻看到链表长什么样哪里出了问题一眼就能找到。3.2 插入操作头插、尾插与指定位置插入插入操作一般有三种头插法新节点插到链表最前面成为新的头节点。void insertAtHead(Node **head, int data) { Node *newNode createNode(data); newNode-next *head; *head newNode; }注意这里的参数是Node **head也就是二级指针。为什么要这么写因为当链表为空时*head是 NULL插入后 head 要指向新节点即使链表非空头插也会改变 head 的指向。如果不传二级指针函数内部只改了形参的副本外部 head 还是原来的值链表头就丢了。这就是经典的“传值 vs 传址”问题。如果你不想用二级指针也可以让函数返回新头指针Node* insertAtHead(Node *head, int data) { Node *newNode createNode(data); newNode-next head; return newNode; }调用时用head insertAtHead(head, data);。两种风格都常见我推荐初学者先把二级指针版本搞明白因为它能强迫你理解指针的本质。尾插法新节点插到链表末尾。需要先遍历到最后一个节点然后把它的 next 指向新节点void insertAtTail(Node **head, int data) { Node *newNode createNode(data); if (*head NULL) { *head newNode; return; } Node *cur *head; while (cur-next ! NULL) { cur cur-next; } cur-next newNode; }尾插的边界条件是链表为空。如果*head NULL说明链表里一个节点都没有那么新节点就是头节点直接让 head 指向它。如果不加这个判断第二轮访问cur-next时就会对 NULL 解引用直接段错误。指定位置插入假设位置从 0 开始计数要把新节点插到下标为 pos 的位置上。思路是先找到当前位置是第 pos-1 个节点的前驱节点 cur然后把新节点插到 cur 后面。比如在A - B - C中要在位置 1 插入 X意思是插入后变成A - X - B - C那么我们需要找到的是位置 0 的 A 节点int insertAtPos(Node **head, int pos, int data) { Node *newNode createNode(data); if (pos 0) { printf(插入位置不能为负数\n); free(newNode); return 0; } if (pos 0) { newNode-next *head; *head newNode; return 1; } Node *cur *head; for (int i 0; i pos - 1 cur ! NULL; i) { cur cur-next; } if (cur NULL) { printf(插入位置超出链表长度\n); free(newNode); return 0; } newNode-next cur-next; cur-next newNode; return 1; }这段代码有两个地方值得停下来想一想。第一个是为什么插入失败时要free(newNode)。因为 newNode 已经 malloc 了如果位置不合法它就不该被加进链表。如果不 free这个节点就变成了内存泄漏程序每次执行到这里都会丢一小块内存。这种细节恰恰是区分“能跑”和“写得好”的分水岭。第二个是最后两行指针操作的顺序newNode-next cur-next; cur-next newNode;这个顺序不能乱。如果先把cur-next改成 newNode那原来 cur 后面的节点地址就丢了新节点找不回去链表就断了。所以必须先把新节点和后一个节点连起来再把前一个节点连到新节点上。下面这个断链场景几乎是每个初学者都踩过的坑。3.3 删除操作找到前驱再动手单链表的删除有一个核心痛点你只有 next 指针没有 prev 指针所以要删除节点 B你必须找到 B 的前驱节点 A然后让 A 的 next 直接指向 B 的 next最后 free 掉 B。按值删除的代码如下int deleteByValue(Node **head, int data) { if (*head NULL) return 0; // 如果要删的是头节点 if ((*head)-data data) { Node *tmp *head; *head (*head)-next; free(tmp); return 1; } Node *cur *head; // 找到目标节点的前驱节点 while (cur-next ! NULL cur-next-data ! data) { cur cur-next; } if (cur-next NULL) return 0; Node *tmp cur-next; cur-next tmp-next; free(tmp); return 1; }为什么删除头节点要单独处理因为删除头节点会改变 head 的指向所以必须用二级指针。删除非头节点时cur 从头开始走直到cur-next指向的值等于 target。这个循环条件很巧妙它同时判断了“下一个节点存在”和“下一个节点的值不等于目标”循环结束后要么cur-next NULL说明链表里没有这个值要么cur-next-data data那么 cur 就是目标节点的前驱。如果要按位置删除思路也差不多找到第 pos-1 个节点然后让它的 next 跳过目标节点int deleteByPos(Node **head, int pos) { if (*head NULL || pos 0) return 0; if (pos 0) { Node *tmp *head; *head (*head)-next; free(tmp); return 1; } Node *cur *head; for (int i 0; i pos - 1 cur-next ! NULL; i) { cur cur-next; } if (cur-next NULL) return 0; Node *tmp cur-next; cur-next tmp-next; free(tmp); return 1; }删除操作最容易犯的错误就是 free 了节点之后还去访问它的成员比如free(tmp); tmp-next;这在 C 语言里是未定义行为。你看着好像有时候还能跑但那是运气好内存还没被系统回收运气不好程序当场崩掉而且崩的位置往往离问题代码很近排查起来很迷惑。3.4 查找与修改遍历的基本功查找操作没有太多花活核心就是从头遍历逐个比较 data 值Node* findByValue(Node *head, int data) { Node *cur head; while (cur ! NULL) { if (cur-data data) { return cur; } cur cur-next; } return NULL; }这个函数返回的是找到的那个节点指针调用方可以直接用found-data来访问数据。如果没找到返回 NULL调用方一定要判断 NULL 再使用否则就是对空指针解引用。修改操作就更直接了。比如按位置修改节点的 dataint updateByPos(Node *head, int pos, int newData) { Node *cur head; for (int i 0; cur ! NULL i pos; i) { cur cur-next; } if (cur NULL) return 0; cur-data newData; return 1; }注意这里的循环条件是cur ! NULL i pos也就是说一边往后走一边数位置。如果走到一半链表就结束了说明 pos 越界返回 0。查找和修改看起来简单但它们其实是在帮你建立一种“遍历思维”对链表大部分操作本质上都是从一个节点开始通过 next 指针不断走向下一个节点直到满足某个条件或者碰到 NULL。你写多了就会发现插入、删除、查找、修改、销毁底子都是同一个 while 循环。3.5 销毁链表free 的完整循环链表用完了必须把每个节点都 free 掉不然会内存泄漏。销毁的代码长这样void destroyList(Node **head) { Node *cur *head; while (cur ! NULL) { Node *next cur-next; free(cur); cur next; } *head NULL; }这里有一个非常关键的细节在 free 当前节点之前必须先保存它的 next 指针。如果你写成while (cur ! NULL) { free(cur); cur cur-next; // 已经 free 了cur-next 是无效访问 }那程序大概率会崩。因为 cur 指向的内存已经被释放了你再访问 cur-next 就相当于读一块已经交还给系统的内存。正确做法是先把下一个节点的地址存到临时变量 next 里free 完当前节点后用 next 继续往前走。最后把*head NULL也是必须的。这样做的目的是让外部头指针不再指向一块已经被释放的内存避免后面误用。这是防御性编程的好习惯。到这里链表增删改查的核心代码已经齐了。我建议你把 createNode、insertAtHead、insertAtTail、insertAtPos、deleteByValue、deleteByPos、findByValue、updateByPos、destroyList、printList 这十个函数放在一起编译一下用一个 main 函数把它们全部串起来跑一遍。看到屏幕上链表一步步变化你会对链表有一种“原来如此”的感觉。4. 常见问题与排查技巧实录链表代码不长但出错方式花样百出。我捋了一下自己带人学习和实际写代码时遇到过的高频问题整理成下面这份排查记录希望能帮你少踩几个坑。4.1 段错误头号杀手段错误出现在哪里基本就说明问题出在哪。最常见的三个原因第一个是空指针解引用。比如你写cur-next-data但如果cur-next是 NULL这行代码当场崩。尤其在某些边界条件下比如删除最后一个节点、在空链表上插入很容易触发。第二个是内存已经被释放却还在用。比如上面说的销毁链表时先 free 再访问 next或者删除节点后还拿那个节点的指针去访问数据。第三个是指针指向错误。比如链表断了某个节点的 next 根本没被正确赋值导致遍历到一个未知地址上。排查段错误我的经验是“二分定位”。先用 printList 看链表结构对不对然后在可疑的循环里加 printf 打印当前走到了哪个节点。不要小看这个土办法十次段错误有八次是这么定位出来的。也可以用 gdb 跑一下程序崩了之后输入 bt 看调用栈能直接告诉你崩在哪一行。4.2 内存泄漏程序越跑越卡内存泄漏的典型表现是程序运行一段时间后内存占用越来越大最后卡死。链表场景下的泄漏点主要有三类一是删除节点时只改了指针没有 free。比如你写删除操作只剩了cur-next tmp-next;忘了free(tmp)那个节点还在堆上躺着但已经没人能找到它了。二是插入失败时没有释放新节点。就像前面 insertAtPos 里的处理如果位置不合法一定记得 free(newNode)否则每次失败都泄漏一次。三是销毁链表写得不完整。比如只 free 了第一个节点就返回剩下的节点全挂在堆上没人管。Linux 下可以用 valgrind 来检测内存泄漏命令是valgrind --leak-checkfull ./your_program。它会告诉你哪些内存是 definitely lost、indirectly lost 还是 possibly lost。我第一次用 valgrind 检查链表代码时发现自己的销毁函数少处理了一个分支当场被自己蠢到。4.3 边界条件空链表、单节点和头尾操作链表代码里最容易翻车的永远是边界条件。我整理了一个自查清单写代码时逐条打勾场景常见错误正确做法空链表上插入直接对 head 解引用先判断 head NULL新节点直接作为头节点删除头节点忘了更新 head用二级指针或者函数返回新头指针删除尾节点找不到尾节点的前驱用 cur-next 遍历到最后一个而不是 cur 本身插入位置为 0走通用逻辑导致越界位置为 0 时单独走头插逻辑pos 超过链表长度循环里越界访问循环条件加上 cur ! NULL 判断单节点链表删除删除后 head 没置 NULL删除后 *head 指向 NULL链表变空我见过很多同学在“单节点链表删除”这个问题上翻车链表里只有一个节点 5你调用 deleteByValue 删除 5期望结果是 head 变成 NULL。如果代码只处理了“删除非头节点”的情况把 5 当普通节点删那 head 指针仍然指向已经被 free 的内存下一次遍历就出鬼。4.4 调试链表的三板斧最后分享三个我实际调试链表时的小技巧。第一个是 printList 大法。我在写链表的每个关键步骤后都会调用 printList 确认链表状态因为指针操作看不见摸不着只有打印出来才能验证逻辑对不对。比如插入后打印一次删除后打印一次看到结构如预期心里就有底。第二个是“画图法”。大家别嫌土硬核程序员也照样在纸上画链表。遇到指针操作混淆的时候把节点画成方框把 next 画成箭头然后手动把每个步骤的箭头改一遍逻辑立刻清晰。我教学生的时候经常说链表的代码是抄不来的因为你如果不懂指针是怎么指的永远都会在某个地方写出 bug但只要你画过一次图这个操作就刻在脑子里了。第三个是构造测试用例。写链表代码不能只测正常情况空表、单节点、两个节点、删除头、删除尾、插入中间、插入越界位置这些用例都要跑一遍。把这些边界情况全部覆盖到你的链表代码才算真正稳了。提示如果你发现删除或插入之后链表“少了一截”十有八九是某个节点的 next 被不小心覆盖了。这时候从打印结果往回推看是哪个操作导致链表断裂再用画图法定位具体是哪一行指针操作出了问题。最后再分享一点个人体会链表这个东西代码量不大但知识点密度极高夹杂了结构体、指针、动态内存、函数传参这些 C 语言最核心的内容。我自己的习惯是正式写代码之前先花三分钟在纸上把节点结构和操作步骤画出来画清楚了再敲键盘写起来基本一遍过。如果你正在学链表千万别觉得画图是在浪费时间恰恰是那几分钟画图能帮你省下几个小时的调试时间。如果你已经能把这篇文章里的代码全部自己默写出来我建议你再往前走一步试试把单链表改成双链表或者实现一个带头节点的版本甚至去研究一下内核里是怎么用链表把模块串起来的。链表的本质就是“用指针组织数据”这个思想是你以后学习树、图、哈希表、缓存淘汰算法等各种高级主题的地基值得你多花点时间把它打牢。
