C语言链表实现教程从定义到插入操作详解链表在C语言里是绕不开的一道坎也是很多人从“会写结构体”迈向“能写数据结构”的临界点。说实话链表本身不复杂难就难在指针的指向关系和处理顺序尤其插入操作里那一两个被写成反方向的赋值语句能把人折腾一晚上。我见过太多初学者对着报错信息发呆其实把链表画成图理解每个节点“除了装数据还记着下一个节点的地址”这件事很多问题就能自己想明白。这篇内容不准备给你整那些高大上的术语而是从链表用来干什么、节点的结构体怎么定义、初始化要注意什么、三种插入操作怎么分别实现到常见报错怎么排查一步一图地拆给你看。适合刚开始学C语言、对结构体和指针一知半解或者学校作业正卡在“链表插入”这道题上的同学。代码我会贴全关键行会提出来讲保证你照着敲完能跑通并且下次再写不迷糊。1. 链表到底解决什么问题——先搞懂为什么不用数组写链表之前咱们得先想清楚一个问题数组用得好好的为什么非要整链表出来这里不是矫情而是因为数组和链表的适用场景确实不一样理解了这个区别你才知道什么时候该用什么。数组在C语言里有个让人头疼的特点大小必须在定义时确定。要么写死一个“足够大”的数字要么用变长数组VLA凑合但VLA在C99之后也只是编译器层面支持并不适用于所有场景。更麻烦的是如果定义了一个100个元素的数组实际只需要存20个数据内存就白白浪费了80个位置反过来如果数据量超过了100数组就装不下了只能改代码重新编译。数组的另一个痛点是插入和删除。在数组中间插入一个元素需要把后面的所有元素依次往后挪一位平均时间复杂度是O(n)。举个例子你有个数组存了十个学生的成绩现在要在第三个位置插入一个新成绩那就得先把第3到第10个元素全部往后移动你的代码里会多出这样一段循环for (int i len; i pos; i--) { arr[i] arr[i - 1]; } arr[pos] newValue; len;一次插入还好如果业务逻辑需要频繁在中间插入或删除这种搬移操作就会让程序变慢而且代码也容易因为边界判断出错。链表就不一样了。链表的每个节点在内存里的位置是随机分配的节点之间靠指针“串”在一起就像一群人围成一个圈每个人只记住下一个人的位置不需要所有人都挨着坐。要插入一个新节点只需要把前一个节点的“下一个地址”改指向新节点新节点再指向原来的下一个节点不需要搬动任何已有数据。所以链表的适用场景很明确数据量不确定、需要频繁在任意位置插入或删除。它用“多存一个指针”的代价换来了插入删除的灵活性和动态扩展的能力。这也是为什么链表的节点定义里必然有一个“数据域”加一个“指针域”。我给新手的建议是别急着把链表当成数组的替代品它们在思维方式上是两种东西。数组讲究的是“连续内存、下标访问”链表讲究的是“离散内存、指针串联”。理解了这一点后面看节点定义和插入代码的指向关系就不会懵。2. 节点的定义链表的基本单元怎么设计知道了链表靠“指针串联”那每个“节点”长什么样就很关键了。C语言里要描述这种“一个数据加一个指向同类节点的指针”的结构标准答案就是结构体struct。2.1 结构体声明里的一个经典坑节点定义最经典也最常见的写法如下typedef struct Node { int data; // 数据域存具体的数据 struct Node *next; // 指针域存下一个节点的地址 } Node;注意看这一行struct Node *next。很多新手会好奇为什么指针类型不直接写成Node *next而是非要写成struct Node *next原因是这个结构体类型还没完全定义完Node这个别名是在结构体声明结束后的那个}后面才生效的。在typedef定义还没结束时你已经想在结构体内部引用这个类型了唯一的办法就是用结构体的“真名”——struct Node。这是C语言的一个经典又容易踩坑的细节面试也经常拿出来考要牢记。那int data和struct Node *next分别干什么用data就是实际存在链表里的数据简单起见咱们先存int你以后可以改成其他具体业务数据类型next是一个指针它存的是下一个节点的地址。如果链表到头了next就赋值为NULL作为链表的终止标志。2.2 为什么要用typedeftypedef struct Node {...} Node;这行代码的作用是给struct Node起了一个别名Node。以后你声明一个节点变量就不用写struct Node node1直接写Node node1就行。我实习时带过几个新人有人觉得typedef多此一举“省几个字母而已嘛有啥大不了的。”其实不只是省字母在声明函数返回值、函数参数的时候Node *createNode(int data)和struct Node *createNode(int data)的阅读体验差别很大。尤其在复杂项目里链表节点可能是嵌套的、带有若干字段的、甚至是指向多个方向的比如二叉树节点这时候一个简洁的别名能让代码天差地别。顺便说一句如果你用C写链表连typedef都可以省了直接用struct Node { ... };就能声明Node类型。但咱们这篇是C语言的教程所以typedef的写法还是要会的。2.3 一个节点在内存里到底是什么样子我曾经用Debug模式观察过一个只含一个节点的链表。申请优先级比较高这里简单用一张表描述它的内存模型部分名称内容说明数据域data例如42节点真正存储的值指针域next例如0x7ffc1234指向下一个节点的地址没有下一个节点则为NULL一个节点就是一个结构体变量它在内存里有自己的地址next存的是下一个结构体变量的地址。所谓“链表头”就是第一个节点的地址一般用一个指针变量head来保存。你理解了这三样东西——节点、next指针、head头指针——链表的基本模型就彻底建起来了。3. 初始化与内存分配链表从无到有的第一步定义好节点结构体之后就要让链表真正“活”起来。这一步的关键是掌握malloc动态内存分配以及搞清楚头节点、头指针、首节点这几个概念的区别。3.1 头指针和头节点千万别搞混链表的第一个节点地址保存在一个变量里这个变量是“头指针”。头指针本身不是节点它只是一个用来指向节点的指针变量。很多教材或者网课会引入一个“头节点”的概念也就是在真正的首节点之前加一个不存数据或者存链表长度等附加信息的哨兵节点。带不带头节点各有各的玩法带头节点的链表插入、删除可以不改变头指针的值函数传参不用二级指针对新手更友好不带头节点的链表则更贴近“一个节点就是一个元素”的直觉但插入首位置时必须通过操作来更新头指针指向。我在实际写代码的时候更倾向于带头节点的写法因为它让插入、删除的逻辑统一不用对“第一个位置”和“后面位置”写两段不同逻辑。但为了让你接触到不同题目和教材的常见写法也为了让链表结构更直观这篇教程采用不带头指针的保护方式直接用一个头指针指向第一个节点。这样的设计在你做OJ时更常见因为很多题让你自己管理头指针。3.2 malloc和NULL检查不能省动态分配内存用的是malloc。它做的事情是向系统申请一块连续内存返回这块内存的首地址如果我们定义节点类型为Node通常这么申请Node *newNode (Node*)malloc(sizeof(Node));很多人写完后不检查返回值直接用这是要出事的。malloc申请内存有可能失败比如内存不足时返回NULL。这时候如果你直接newNode-data 42就是往空地址写数据程序会崩。正确的姿势是Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); }注意一个问题malloc分配出来的是未经初始化的内存里面的内容是随机值。所以务必给data赋值也务必把next置成NULL。很多“链表打印停不下来”的bug根源就是新节点的next没初始化变成了野指针让遍历程序跑飞了。初始化一个节点建议封装成函数后面插入操作都要反复用到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; }以后每次要新节点直接Node *p createNode(10);就行不用每次都重复写那些malloc和判空的样板代码。这也是一个让代码更干净的实战小习惯。3.3 手动搭出第一条链表在写插入函数之前我习惯先手工创建三个节点验证一下结构体定义和指针关联写对了没有。这个过程能帮你直观理解“节点靠next串起来”这件事int main() { Node *head createNode(1); Node *second createNode(2); Node *third createNode(3); head-next second; second-next third; // third-next 在 createNode 里已经是 NULL // 遍历打印 Node *temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); return 0; }输出结果是1 - 2 - 3 - NULL。看到这个输出说明节点定义、内存分配、指针串联都成功了。很多教材喜欢用这种方式教你搭链表因为它不涉及复杂算法就是最朴素的“定义节点、分配内存、串指针”。4. 插入操作详解头插、尾插、指定位置插入插入是链表操作里最容易出问题的地方但也是有规律可循的。只要记住一句话先把新节点的next指好再断开原来的连接你就能避免绝大多数指针混乱。4.1 头插法每次插在最前面头插法适合构建栈这种“后进先出”的数据结构。思路特别直白新节点变成新的头节点原来的头指针指向它即可。void insertAtHead(Node **head, int data) { Node *newNode createNode(data); newNode-next *head; *head newNode; }为什么这里参数要写成Node **head而不是Node *head这是很多刚入门同学最蒙的地方。我打个比方Node *head传进函数函数里能修改head-next但修改不了外部的head这个变量本身。如果函数里写了head newNode改的只是形参函数调用结束后外部的头指针还是原来的。只有传Node **head函数拿到的是“头指针的地址”才能通过*head newNode直接改写外部的头指针变量。很多题解会写head insertAtHead(head, data)也就是把新头指针作为返回值传出来。这也是一种常见写法。我在这里展示Node **的写法是因为它更贴近“直接修改内存”的原生C思维也是新手必须看懂的一种形态。4.2 尾插法每次插到最后面尾插法逻辑也不复杂头指针不用改但要先遍历找到最后一个节点然后把新节点接到它后面。特殊情况是链表为空时直接让头指针指向新节点就行了。void insertAtTail(Node **head, int data) { Node *newNode createNode(data); if (*head NULL) { *head newNode; return; } Node *temp *head; while (temp-next ! NULL) { temp temp-next; } temp-next newNode; }这里有一个性能上的提醒每次尾插都要从头走到尾时间复杂度是O(n)如果频繁往尾部插入大量节点效率会受影响。通常的改进办法是额外维护一个尾指针插完新节点就更新尾指针。我在代码里先不加这个等你看懂基础的尾插法再去优化这个流程会更顺畅。4.3 指定位置插入最考验指针操作的地方指定位置插入是在第pos个位置插入一个新节点从0开始数。它是最能体现“链表插入思想”的操作也是最容易出错的。完整实现如下void insertAtPosition(Node **head, int data, int pos) { if (pos 0) { printf(位置非法\n); return; } if (pos 0) { insertAtHead(head, data); return; } Node *newNode createNode(data); Node *temp *head; // 找到第 pos-1 个节点 for (int i 0; i pos - 1 temp ! NULL; i) { temp temp-next; } if (temp NULL) { printf(插入位置超出链表长度\n); free(newNode); // 没有插入成功得释放内存避免泄漏 return; } newNode-next temp-next; temp-next newNode; }这个函数里的顺序极其重要。请务必记住这两行的先后newNode-next temp-next; // 先让新节点指向原来的下一个节点 temp-next newNode; // 再让前驱节点指向新节点如果写反了先执行temp-next newNode那原来的后续节点就找不到了也就是常说的“丢链”。这时你再去连newNode-next接到的就不是原来的后续节点了。丢链之后原有链表后半截就彻底访问不到了变成内存泄漏严重的直接导致程序逻辑错乱。我还见过有人把newNode-next temp-next写成newNode-next temp最后链表被接成了一个环输出永远停不下来。这种bug本质上都是对“谁指向谁”没想清楚。在纸上画一画原有链是A-B要在A后面插入X第一步X-B第二步A-X两步完成图特别清晰。4.4 三种插入方式对比为了方便你快速对照我把三种插入方式的要点整理成一张表插入方式要改的指针时间复杂度特殊情况核心注意点头插法只有头指针O(1)链表为空也不怕先让新节点指向原头节点再更新头指针尾插法尾节点的nextO(n)链表为空时直接设置头指针记得遍历到最后一个节点优化可加尾指针指定位置插入前驱节点的next和新节点的nextO(n)插入位置为0位置越界先接新节点再接前驱越界时要free新节点5. 遍历与验证插入之后怎么确认没插错写完插入函数光看代码对了不算数一定要跑起来看输出。这一节聊聊怎么用遍历来验证链表是否正确以及为什么我建议你在关键节点加上打印语句。5.1 写出一个能打印全链表的函数遍历链表的思想很简单从head出发沿着next一直走直到NULL为止。void printList(Node *head) { Node *temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); }我在调试链表问题时几乎每一步都会调用这个函数。这不丢人很多写了几年代码的老手做链表题时也会printList一下看看情况。可视化输出是调试里最快的手段别在一开始就指望大脑能模拟指针跳转。5.2 一个完整的测试程序串起所有操作这里给出一个把三种插入方式都跑一遍的完整可编译程序你可以直接复制下来丢进编辑器里运行#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) { printf(内存分配失败\n); exit(1); } newNode-data data; newNode-next NULL; return newNode; } void insertAtHead(Node **head, int data) { Node *newNode createNode(data); newNode-next *head; *head newNode; } void insertAtTail(Node **head, int data) { Node *newNode createNode(data); if (*head NULL) { *head newNode; return; } Node *temp *head; while (temp-next ! NULL) { temp temp-next; } temp-next newNode; } void insertAtPosition(Node **head, int data, int pos) { if (pos 0) { printf(位置非法\n); return; } if (pos 0) { insertAtHead(head, data); return; } Node *newNode createNode(data); Node *temp *head; for (int i 0; i pos - 1 temp ! NULL; i) { temp temp-next; } if (temp NULL) { printf(插入位置超出链表长度\n); free(newNode); return; } newNode-next temp-next; temp-next newNode; } void printList(Node *head) { Node *temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); } int main() { Node *head NULL; insertAtTail(head, 10); insertAtTail(head, 20); insertAtTail(head, 30); printList(head); // 期待10 - 20 - 30 - NULL insertAtHead(head, 5); printList(head); // 期待5 - 10 - 20 - 30 - NULL insertAtPosition(head, 15, 2); printList(head); // 期待5 - 10 - 15 - 20 - 30 - NULL insertAtPosition(head, 100, 99); printList(head); // 提示越界链表不变 return 0; }我建议你把每一处printList对应的期待输出先写在纸上再运行对比。如果某一步输出和期待不一致定位问题的范围就能直接锁定到刚刚调用的那个函数里排查效率会高很多。6. 常见问题与排查技巧走过的坑都替你踩过了链表写多了踩过的坑来来去去就是那么几个。这里我把新手期最容易遇到的几类问题整理出来附带排查思路。你可以收藏起来等真报错了再翻出来对号入座。6.1 程序运行起来就崩大概率是空指针或野指针常见的崩法编译过了运行直接“segmentation fault”或者窗口弹出崩溃提示。这种情况十有八九是访问了NULL地址或者未分配内存的野指针。排查思路很简单在你觉得可疑的函数入口处打印一下指针。比如在printList里加一句if (head NULL) { printf(链表为空\n); return; }如果确认不是空指针那再检查一下你是不是用了一个没有初始化的局部指针。C语言里局部指针变量如果不初始化值是不确定的也就是野指针。我见过最典型的错误是Node *temp; // 没有初始化 while (temp-next ! NULL) { // 直接用必崩 // ... }正确做法是声明指针变量时随手初始化为NULL用之前判断一下这是能帮你减少一半崩溃问题的小习惯。6.2 输出死循环停不下来链表八成成环了如果你打印链表时屏幕上一直输出不停那几乎可以断定某个节点的next指回了前面的节点形成环了。常见原因是插入时指针顺序写反或者某个节点的next没置NULL。遇到死循环先别急了拔电源。我教你一个快速定位的方法写一个“数节点”的临时函数设置一个计数器循环到1000次就强制退出并打印当前节点地址。通过对比打印出来的地址你就能看到哪两个节点的地址重复了从而找到成环的位置。这个方法虽然粗犷但在调试链表环时特别管用。6.3 插入了但打印看不出来检查是不是改到形参了有些同学写完插入函数调用后打印链表还是老样子很疑惑。我一看代码多半是参数传的是Node *head而函数里写了head newNode。这种情况函数内部改了形参外部的head根本没变化。解决方式就两种一种是我前面展示的传二级指针Node **head另一种是让函数返回新头指针调用时赋值回去。这两种都是合法且常见的写法你选一个用就好。我推荐掌握二级指针的写法因为它对理解C语言“传地址与传值的区别”特别有帮助。说到这我还想提醒你使用完链表之后别忘了释放内存malloc和free要成对出现。如果你在指定位置插入时发现位置越界直接free(newNode)否则这个节点就永久性泄漏了。平时练习时确实可以不较真但到了写工程代码或参加面试时内存泄漏是会直接被扣分的点。6.4 常见问题速查表现象可能原因排查/解决方向编译都不过提示 unknown type name Node结构体定义顺序不对确认typedef struct Node完整写在了使用之前运行崩溃空指针或野指针初始化指针为NULL使用前判空输出死循环链表成环检查插入时next赋值顺序确认没有环插入没生效只修改了形参改用二级指针或返回新头指针输出少了后半段节点插入时丢失了后续节点检查是否先执行了temp-next newNode导致丢链越界插入后内存一直涨节点分配了没释放在越界分支里加上free(newNode)新节点数据是乱值malloc后没初始化data和nextcreateNode里统一初始化我把这些坑写在最后不是吓唬你而是因为每一行都是我自己实际调试中抠出来的。那时候没有网上的社区文章可看只能盯着屏幕一遍一遍看内存地址一遍一遍打印输出。现在的学习条件好多了遇到问题先想“指针指向对不对”“顺序有没有反”“空值判断有没有漏”基本就八九不离十了。有个我特别推荐的技巧也送给你写链表操作之前先在纸上把节点画出来用箭头表示指针指向操作一步画一步。你画过两三张图之后写代码就再也不心虚了。你的第一个链表可能花了两小时才调通调通了后面就顺手了很快你也会写出属于自己的头插尾插和反转算法。 C语言链表实现教程：从结构体定义到三种插入操作
C语言链表实现教程从定义到插入操作详解链表在C语言里是绕不开的一道坎也是很多人从“会写结构体”迈向“能写数据结构”的临界点。说实话链表本身不复杂难就难在指针的指向关系和处理顺序尤其插入操作里那一两个被写成反方向的赋值语句能把人折腾一晚上。我见过太多初学者对着报错信息发呆其实把链表画成图理解每个节点“除了装数据还记着下一个节点的地址”这件事很多问题就能自己想明白。这篇内容不准备给你整那些高大上的术语而是从链表用来干什么、节点的结构体怎么定义、初始化要注意什么、三种插入操作怎么分别实现到常见报错怎么排查一步一图地拆给你看。适合刚开始学C语言、对结构体和指针一知半解或者学校作业正卡在“链表插入”这道题上的同学。代码我会贴全关键行会提出来讲保证你照着敲完能跑通并且下次再写不迷糊。1. 链表到底解决什么问题——先搞懂为什么不用数组写链表之前咱们得先想清楚一个问题数组用得好好的为什么非要整链表出来这里不是矫情而是因为数组和链表的适用场景确实不一样理解了这个区别你才知道什么时候该用什么。数组在C语言里有个让人头疼的特点大小必须在定义时确定。要么写死一个“足够大”的数字要么用变长数组VLA凑合但VLA在C99之后也只是编译器层面支持并不适用于所有场景。更麻烦的是如果定义了一个100个元素的数组实际只需要存20个数据内存就白白浪费了80个位置反过来如果数据量超过了100数组就装不下了只能改代码重新编译。数组的另一个痛点是插入和删除。在数组中间插入一个元素需要把后面的所有元素依次往后挪一位平均时间复杂度是O(n)。举个例子你有个数组存了十个学生的成绩现在要在第三个位置插入一个新成绩那就得先把第3到第10个元素全部往后移动你的代码里会多出这样一段循环for (int i len; i pos; i--) { arr[i] arr[i - 1]; } arr[pos] newValue; len;一次插入还好如果业务逻辑需要频繁在中间插入或删除这种搬移操作就会让程序变慢而且代码也容易因为边界判断出错。链表就不一样了。链表的每个节点在内存里的位置是随机分配的节点之间靠指针“串”在一起就像一群人围成一个圈每个人只记住下一个人的位置不需要所有人都挨着坐。要插入一个新节点只需要把前一个节点的“下一个地址”改指向新节点新节点再指向原来的下一个节点不需要搬动任何已有数据。所以链表的适用场景很明确数据量不确定、需要频繁在任意位置插入或删除。它用“多存一个指针”的代价换来了插入删除的灵活性和动态扩展的能力。这也是为什么链表的节点定义里必然有一个“数据域”加一个“指针域”。我给新手的建议是别急着把链表当成数组的替代品它们在思维方式上是两种东西。数组讲究的是“连续内存、下标访问”链表讲究的是“离散内存、指针串联”。理解了这一点后面看节点定义和插入代码的指向关系就不会懵。2. 节点的定义链表的基本单元怎么设计知道了链表靠“指针串联”那每个“节点”长什么样就很关键了。C语言里要描述这种“一个数据加一个指向同类节点的指针”的结构标准答案就是结构体struct。2.1 结构体声明里的一个经典坑节点定义最经典也最常见的写法如下typedef struct Node { int data; // 数据域存具体的数据 struct Node *next; // 指针域存下一个节点的地址 } Node;注意看这一行struct Node *next。很多新手会好奇为什么指针类型不直接写成Node *next而是非要写成struct Node *next原因是这个结构体类型还没完全定义完Node这个别名是在结构体声明结束后的那个}后面才生效的。在typedef定义还没结束时你已经想在结构体内部引用这个类型了唯一的办法就是用结构体的“真名”——struct Node。这是C语言的一个经典又容易踩坑的细节面试也经常拿出来考要牢记。那int data和struct Node *next分别干什么用data就是实际存在链表里的数据简单起见咱们先存int你以后可以改成其他具体业务数据类型next是一个指针它存的是下一个节点的地址。如果链表到头了next就赋值为NULL作为链表的终止标志。2.2 为什么要用typedeftypedef struct Node {...} Node;这行代码的作用是给struct Node起了一个别名Node。以后你声明一个节点变量就不用写struct Node node1直接写Node node1就行。我实习时带过几个新人有人觉得typedef多此一举“省几个字母而已嘛有啥大不了的。”其实不只是省字母在声明函数返回值、函数参数的时候Node *createNode(int data)和struct Node *createNode(int data)的阅读体验差别很大。尤其在复杂项目里链表节点可能是嵌套的、带有若干字段的、甚至是指向多个方向的比如二叉树节点这时候一个简洁的别名能让代码天差地别。顺便说一句如果你用C写链表连typedef都可以省了直接用struct Node { ... };就能声明Node类型。但咱们这篇是C语言的教程所以typedef的写法还是要会的。2.3 一个节点在内存里到底是什么样子我曾经用Debug模式观察过一个只含一个节点的链表。申请优先级比较高这里简单用一张表描述它的内存模型部分名称内容说明数据域data例如42节点真正存储的值指针域next例如0x7ffc1234指向下一个节点的地址没有下一个节点则为NULL一个节点就是一个结构体变量它在内存里有自己的地址next存的是下一个结构体变量的地址。所谓“链表头”就是第一个节点的地址一般用一个指针变量head来保存。你理解了这三样东西——节点、next指针、head头指针——链表的基本模型就彻底建起来了。3. 初始化与内存分配链表从无到有的第一步定义好节点结构体之后就要让链表真正“活”起来。这一步的关键是掌握malloc动态内存分配以及搞清楚头节点、头指针、首节点这几个概念的区别。3.1 头指针和头节点千万别搞混链表的第一个节点地址保存在一个变量里这个变量是“头指针”。头指针本身不是节点它只是一个用来指向节点的指针变量。很多教材或者网课会引入一个“头节点”的概念也就是在真正的首节点之前加一个不存数据或者存链表长度等附加信息的哨兵节点。带不带头节点各有各的玩法带头节点的链表插入、删除可以不改变头指针的值函数传参不用二级指针对新手更友好不带头节点的链表则更贴近“一个节点就是一个元素”的直觉但插入首位置时必须通过操作来更新头指针指向。我在实际写代码的时候更倾向于带头节点的写法因为它让插入、删除的逻辑统一不用对“第一个位置”和“后面位置”写两段不同逻辑。但为了让你接触到不同题目和教材的常见写法也为了让链表结构更直观这篇教程采用不带头指针的保护方式直接用一个头指针指向第一个节点。这样的设计在你做OJ时更常见因为很多题让你自己管理头指针。3.2 malloc和NULL检查不能省动态分配内存用的是malloc。它做的事情是向系统申请一块连续内存返回这块内存的首地址如果我们定义节点类型为Node通常这么申请Node *newNode (Node*)malloc(sizeof(Node));很多人写完后不检查返回值直接用这是要出事的。malloc申请内存有可能失败比如内存不足时返回NULL。这时候如果你直接newNode-data 42就是往空地址写数据程序会崩。正确的姿势是Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); }注意一个问题malloc分配出来的是未经初始化的内存里面的内容是随机值。所以务必给data赋值也务必把next置成NULL。很多“链表打印停不下来”的bug根源就是新节点的next没初始化变成了野指针让遍历程序跑飞了。初始化一个节点建议封装成函数后面插入操作都要反复用到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; }以后每次要新节点直接Node *p createNode(10);就行不用每次都重复写那些malloc和判空的样板代码。这也是一个让代码更干净的实战小习惯。3.3 手动搭出第一条链表在写插入函数之前我习惯先手工创建三个节点验证一下结构体定义和指针关联写对了没有。这个过程能帮你直观理解“节点靠next串起来”这件事int main() { Node *head createNode(1); Node *second createNode(2); Node *third createNode(3); head-next second; second-next third; // third-next 在 createNode 里已经是 NULL // 遍历打印 Node *temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); return 0; }输出结果是1 - 2 - 3 - NULL。看到这个输出说明节点定义、内存分配、指针串联都成功了。很多教材喜欢用这种方式教你搭链表因为它不涉及复杂算法就是最朴素的“定义节点、分配内存、串指针”。4. 插入操作详解头插、尾插、指定位置插入插入是链表操作里最容易出问题的地方但也是有规律可循的。只要记住一句话先把新节点的next指好再断开原来的连接你就能避免绝大多数指针混乱。4.1 头插法每次插在最前面头插法适合构建栈这种“后进先出”的数据结构。思路特别直白新节点变成新的头节点原来的头指针指向它即可。void insertAtHead(Node **head, int data) { Node *newNode createNode(data); newNode-next *head; *head newNode; }为什么这里参数要写成Node **head而不是Node *head这是很多刚入门同学最蒙的地方。我打个比方Node *head传进函数函数里能修改head-next但修改不了外部的head这个变量本身。如果函数里写了head newNode改的只是形参函数调用结束后外部的头指针还是原来的。只有传Node **head函数拿到的是“头指针的地址”才能通过*head newNode直接改写外部的头指针变量。很多题解会写head insertAtHead(head, data)也就是把新头指针作为返回值传出来。这也是一种常见写法。我在这里展示Node **的写法是因为它更贴近“直接修改内存”的原生C思维也是新手必须看懂的一种形态。4.2 尾插法每次插到最后面尾插法逻辑也不复杂头指针不用改但要先遍历找到最后一个节点然后把新节点接到它后面。特殊情况是链表为空时直接让头指针指向新节点就行了。void insertAtTail(Node **head, int data) { Node *newNode createNode(data); if (*head NULL) { *head newNode; return; } Node *temp *head; while (temp-next ! NULL) { temp temp-next; } temp-next newNode; }这里有一个性能上的提醒每次尾插都要从头走到尾时间复杂度是O(n)如果频繁往尾部插入大量节点效率会受影响。通常的改进办法是额外维护一个尾指针插完新节点就更新尾指针。我在代码里先不加这个等你看懂基础的尾插法再去优化这个流程会更顺畅。4.3 指定位置插入最考验指针操作的地方指定位置插入是在第pos个位置插入一个新节点从0开始数。它是最能体现“链表插入思想”的操作也是最容易出错的。完整实现如下void insertAtPosition(Node **head, int data, int pos) { if (pos 0) { printf(位置非法\n); return; } if (pos 0) { insertAtHead(head, data); return; } Node *newNode createNode(data); Node *temp *head; // 找到第 pos-1 个节点 for (int i 0; i pos - 1 temp ! NULL; i) { temp temp-next; } if (temp NULL) { printf(插入位置超出链表长度\n); free(newNode); // 没有插入成功得释放内存避免泄漏 return; } newNode-next temp-next; temp-next newNode; }这个函数里的顺序极其重要。请务必记住这两行的先后newNode-next temp-next; // 先让新节点指向原来的下一个节点 temp-next newNode; // 再让前驱节点指向新节点如果写反了先执行temp-next newNode那原来的后续节点就找不到了也就是常说的“丢链”。这时你再去连newNode-next接到的就不是原来的后续节点了。丢链之后原有链表后半截就彻底访问不到了变成内存泄漏严重的直接导致程序逻辑错乱。我还见过有人把newNode-next temp-next写成newNode-next temp最后链表被接成了一个环输出永远停不下来。这种bug本质上都是对“谁指向谁”没想清楚。在纸上画一画原有链是A-B要在A后面插入X第一步X-B第二步A-X两步完成图特别清晰。4.4 三种插入方式对比为了方便你快速对照我把三种插入方式的要点整理成一张表插入方式要改的指针时间复杂度特殊情况核心注意点头插法只有头指针O(1)链表为空也不怕先让新节点指向原头节点再更新头指针尾插法尾节点的nextO(n)链表为空时直接设置头指针记得遍历到最后一个节点优化可加尾指针指定位置插入前驱节点的next和新节点的nextO(n)插入位置为0位置越界先接新节点再接前驱越界时要free新节点5. 遍历与验证插入之后怎么确认没插错写完插入函数光看代码对了不算数一定要跑起来看输出。这一节聊聊怎么用遍历来验证链表是否正确以及为什么我建议你在关键节点加上打印语句。5.1 写出一个能打印全链表的函数遍历链表的思想很简单从head出发沿着next一直走直到NULL为止。void printList(Node *head) { Node *temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); }我在调试链表问题时几乎每一步都会调用这个函数。这不丢人很多写了几年代码的老手做链表题时也会printList一下看看情况。可视化输出是调试里最快的手段别在一开始就指望大脑能模拟指针跳转。5.2 一个完整的测试程序串起所有操作这里给出一个把三种插入方式都跑一遍的完整可编译程序你可以直接复制下来丢进编辑器里运行#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) { printf(内存分配失败\n); exit(1); } newNode-data data; newNode-next NULL; return newNode; } void insertAtHead(Node **head, int data) { Node *newNode createNode(data); newNode-next *head; *head newNode; } void insertAtTail(Node **head, int data) { Node *newNode createNode(data); if (*head NULL) { *head newNode; return; } Node *temp *head; while (temp-next ! NULL) { temp temp-next; } temp-next newNode; } void insertAtPosition(Node **head, int data, int pos) { if (pos 0) { printf(位置非法\n); return; } if (pos 0) { insertAtHead(head, data); return; } Node *newNode createNode(data); Node *temp *head; for (int i 0; i pos - 1 temp ! NULL; i) { temp temp-next; } if (temp NULL) { printf(插入位置超出链表长度\n); free(newNode); return; } newNode-next temp-next; temp-next newNode; } void printList(Node *head) { Node *temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); } int main() { Node *head NULL; insertAtTail(head, 10); insertAtTail(head, 20); insertAtTail(head, 30); printList(head); // 期待10 - 20 - 30 - NULL insertAtHead(head, 5); printList(head); // 期待5 - 10 - 20 - 30 - NULL insertAtPosition(head, 15, 2); printList(head); // 期待5 - 10 - 15 - 20 - 30 - NULL insertAtPosition(head, 100, 99); printList(head); // 提示越界链表不变 return 0; }我建议你把每一处printList对应的期待输出先写在纸上再运行对比。如果某一步输出和期待不一致定位问题的范围就能直接锁定到刚刚调用的那个函数里排查效率会高很多。6. 常见问题与排查技巧走过的坑都替你踩过了链表写多了踩过的坑来来去去就是那么几个。这里我把新手期最容易遇到的几类问题整理出来附带排查思路。你可以收藏起来等真报错了再翻出来对号入座。6.1 程序运行起来就崩大概率是空指针或野指针常见的崩法编译过了运行直接“segmentation fault”或者窗口弹出崩溃提示。这种情况十有八九是访问了NULL地址或者未分配内存的野指针。排查思路很简单在你觉得可疑的函数入口处打印一下指针。比如在printList里加一句if (head NULL) { printf(链表为空\n); return; }如果确认不是空指针那再检查一下你是不是用了一个没有初始化的局部指针。C语言里局部指针变量如果不初始化值是不确定的也就是野指针。我见过最典型的错误是Node *temp; // 没有初始化 while (temp-next ! NULL) { // 直接用必崩 // ... }正确做法是声明指针变量时随手初始化为NULL用之前判断一下这是能帮你减少一半崩溃问题的小习惯。6.2 输出死循环停不下来链表八成成环了如果你打印链表时屏幕上一直输出不停那几乎可以断定某个节点的next指回了前面的节点形成环了。常见原因是插入时指针顺序写反或者某个节点的next没置NULL。遇到死循环先别急了拔电源。我教你一个快速定位的方法写一个“数节点”的临时函数设置一个计数器循环到1000次就强制退出并打印当前节点地址。通过对比打印出来的地址你就能看到哪两个节点的地址重复了从而找到成环的位置。这个方法虽然粗犷但在调试链表环时特别管用。6.3 插入了但打印看不出来检查是不是改到形参了有些同学写完插入函数调用后打印链表还是老样子很疑惑。我一看代码多半是参数传的是Node *head而函数里写了head newNode。这种情况函数内部改了形参外部的head根本没变化。解决方式就两种一种是我前面展示的传二级指针Node **head另一种是让函数返回新头指针调用时赋值回去。这两种都是合法且常见的写法你选一个用就好。我推荐掌握二级指针的写法因为它对理解C语言“传地址与传值的区别”特别有帮助。说到这我还想提醒你使用完链表之后别忘了释放内存malloc和free要成对出现。如果你在指定位置插入时发现位置越界直接free(newNode)否则这个节点就永久性泄漏了。平时练习时确实可以不较真但到了写工程代码或参加面试时内存泄漏是会直接被扣分的点。6.4 常见问题速查表现象可能原因排查/解决方向编译都不过提示 unknown type name Node结构体定义顺序不对确认typedef struct Node完整写在了使用之前运行崩溃空指针或野指针初始化指针为NULL使用前判空输出死循环链表成环检查插入时next赋值顺序确认没有环插入没生效只修改了形参改用二级指针或返回新头指针输出少了后半段节点插入时丢失了后续节点检查是否先执行了temp-next newNode导致丢链越界插入后内存一直涨节点分配了没释放在越界分支里加上free(newNode)新节点数据是乱值malloc后没初始化data和nextcreateNode里统一初始化我把这些坑写在最后不是吓唬你而是因为每一行都是我自己实际调试中抠出来的。那时候没有网上的社区文章可看只能盯着屏幕一遍一遍看内存地址一遍一遍打印输出。现在的学习条件好多了遇到问题先想“指针指向对不对”“顺序有没有反”“空值判断有没有漏”基本就八九不离十了。有个我特别推荐的技巧也送给你写链表操作之前先在纸上把节点画出来用箭头表示指针指向操作一步画一步。你画过两三张图之后写代码就再也不心虚了。你的第一个链表可能花了两小时才调通调通了后面就顺手了很快你也会写出属于自己的头插尾插和反转算法。