🏠个人主页：黎雁
🎬作者简介：C/C++/JAVA后端开发学习者
❄️个人专栏：C语言、数据结构（C语言）、EasyX、游戏、规划、程序人生
✨ 从来绝巘须孤往，万里同尘即玉京
文章目录
- 【线性表系列进阶篇】手搓单向链表：从指针迷宫到代码实现
- 一、核心概念回顾
- 二、工程结构规划
- 三、第一步：定义链表节点与函数声明（SList.h）
- 四、第二步：实现链表核心操作函数（SList.c）
- 1. 辅助函数：创建新节点
- 2. 打印链表
- 3. 尾插操作
- 4. 头插操作
- 5. 尾删操作
- 6. 头删操作
- 7. 查找操作
- 8. 指定位置前插入
- 9. 指定位置删除
- 五、第三步：编写测试用例（Test.c）
- 编译与运行指令（Windows + MinGW）
- 预期输出结果
- 六、常见问题与避坑指南 🚫
- 七、进阶篇小结
【线性表系列进阶篇】手搓单向链表：从指针迷宫到代码实现
你好！欢迎来到线性表系列的进阶篇。
在上一篇的入门篇中，我们了解了链表诞生的背景和核心思想。今天，我们将不再纸上谈兵，而是亲自动手，用C语言实现一个完整的单向不带头非循环链表。
这不仅是对理论知识的巩固，更是一次绝佳的指针实战演练。我们将从定义节点开始，一步步实现头插、尾插、头删、尾删、查找、任意位置插入和删除等所有核心操作。
准备好了吗？系好安全带，我们要进入指针的世界了！💻
一、核心概念回顾
【线性表系列入门篇】从顺序表到链表：解锁数据结构的进化密码
在开始编码之前，我们先来回顾一下单向不带头非循环链表的核心特征，这是我们实现代码的理论基础：
- 单向链表：每个节点只有一个指向下一个节点的指针 (
next)，只能从前往后遍历，无法反向查找。 - 不带头链表：链表的第一个节点就存储有效数据，我们用一个指针
phead来指向它，链表为空时phead = NULL。 - 非循环链表：链表的最后一个节点的
next指针指向NULL，NULL是链表的结束标志。
学习提示：单向不带头非循环链表是链表学习的重中之重，它的操作逻辑最能体现指针的精髓，也是笔试面试的高频考点。
二、工程结构规划
在实际开发中，一个清晰的工程结构能大大提升代码的可读性和可维护性。我们将采用头文件+源文件+测试文件的分离模式：
| 文件名称 | 作用 |
|---|---|
SList.h | 存放节点结构体定义、函数声明、必要的头文件包含 |
SList.c | 存放链表所有操作函数的具体实现 |
Test.c | 编写测试用例，验证链表功能的正确性 |
这种分离模式的优势：
- 接口与实现分离，调用者只需关注
SList.h中的函数声明 - 便于多人协作开发，避免函数重复定义
- 提高代码复用性，修改实现逻辑时无需改动测试代码
三、第一步：定义链表节点与函数声明（SList.h）
链表的基本单元是节点（Node）。我们用结构体来定义节点，同时在头文件中声明所有操作函数。
#pragmaonce// 防止头文件被重复包含#include<stdio.h>#include<stdlib.h>#include<assert.h>// 定义链表存储的数据类型，方便后续修改typedefintSLTDataType;// 定义单向链表节点结构体typedefstructSListNode{SLTDataType data;// 节点存储的数据域structSListNode*next;// 节点的指针域，指向下一个节点}SLTNode;// 函数声明// 辅助函数：创建一个新节点SLTNode*BuySListNode(SLTDataType x);// 打印链表voidSListPrint(SLTNode*phead);// 尾插：在链表尾部插入元素voidSListPushBack(SLTNode**pphead,SLTDataType x);// 头插：在链表头部插入元素voidSListPushFront(SLTNode**pphead,SLTDataType x);// 尾删：删除链表尾部元素voidSListPopBack(SLTNode**pphead);// 头删：删除链表头部元素voidSListPopFront(SLTNode**pphead);// 查找：查找值为x的节点，找到返回节点地址，否则返回NULLSLTNode*SListFind(SLTNode*phead,SLTDataType x);// 在pos节点之前插入值为x的节点voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x);// 删除pos位置的节点voidSListErase(SLTNode**pphead,SLTNode*pos);代码解析：
typedef int SLTDataType：使用类型重定义，后续如果要存储double类型，只需修改这一行代码。struct SListNode：包含data（数据域）和next（指针域）两个成员，指针域的类型必须是struct SListNode*，才能指向同类型节点。#pragma once：C语言的预处理指令，避免头文件被多次包含导致的重复定义错误。assert.h：提供断言函数assert，用于在调试阶段检查非法参数，比如传入的pos节点不能为NULL。
四、第二步：实现链表核心操作函数（SList.c）
所有函数的具体实现都放在SList.c中，我们逐个分析每个操作的实现逻辑、关键点和注意事项。
1. 辅助函数：创建新节点
#include"SList.h"// 辅助函数：创建一个新节点并初始化SLTNode*BuySListNode(SLTDataType x){// 动态分配内存SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));// 检查内存分配是否成功if(newnode==NULL){perror("malloc fail");// 打印错误原因exit(1);// 异常退出程序}// 初始化节点newnode->data=x;newnode->next=NULL;// 新节点默认指向NULL，避免野指针returnnewnode;}关键点：
- 动态内存分配后必须检查是否成功，否则会导致程序崩溃
- 新节点的
next指针必须初始化为NULL，防止出现野指针
2. 打印链表
// 打印链表：遍历链表，打印每个节点的数据voidSListPrint(SLTNode*phead){SLTNode*cur=phead;// cur指针用于遍历链表while(cur!=NULL)// 遍历到NULL时停止{printf("%d->",cur->data);cur=cur->next;// cur指针后移}printf("NULL\n");// 打印链表结束标志}关键点：
- 使用
cur指针遍历，避免修改原链表的头指针phead - 打印格式
%d->清晰展示链表结构，结尾的NULL明确链表的结束位置
3. 尾插操作
// 尾插：在链表尾部插入元素voidSListPushBack(SLTNode**pphead,SLTDataType x){SLTNode*newnode=BuySListNode(x);// 情况1：链表为空if(*pphead==NULL){*pphead=newnode;}// 情况2：链表不为空else{// 找到尾节点（next为NULL的节点）SLTNode*tail=*pphead;while(tail->next!=NULL){tail=tail->next;}// 尾节点的next指向新节点tail->next=newnode;}}核心思考：为什么参数是二级指针SLTNode** pphead？
- 当链表为空时，需要修改
main函数中头指针plist的值（让它指向新节点） - 在C语言中，要修改一个变量的值，必须传递它的地址
plist是一级指针，它的地址就是二级指针pphead
4. 头插操作
// 头插：在链表头部插入元素voidSListPushFront(SLTNode**pphead,SLTDataType x){SLTNode*newnode=BuySListNode(x);// 新节点的next指向原来的头节点newnode->next=*pphead;// 头指针指向新节点，新节点成为新的头*pphead=newnode;}关键点：
- 头插操作无需遍历链表，时间复杂度为
O(1)，效率极高 - 操作顺序不能颠倒：必须先让新节点指向原头节点，再更新头指针
5. 尾删操作
// 尾删：删除链表尾部元素voidSListPopBack(SLTNode**pphead){// 情况1：链表为空，直接返回if(*pphead==NULL){return;}// 情况2：链表只有一个节点elseif((*pphead)->next==NULL){free(*pphead);// 释放节点内存*pphead=NULL;// 头指针置空，避免野指针}// 情况3：链表有多个节点else{// 找到倒数第二个节点SLTNode*prev=*pphead;while(prev->next->next!=NULL){prev=prev->next;}// 释放尾节点free(prev->next);// 倒数第二个节点的next置空，成为新的尾节点prev->next=NULL;}}关键点：
- 必须处理三种边界情况：空链表、单节点链表、多节点链表
- 释放内存后必须将指针置空，否则会出现野指针问题
- 单节点链表删除后，头指针必须置空
6. 头删操作
// 头删：删除链表头部元素voidSListPopFront(SLTNode**pphead){// 链表为空，直接返回if(*pphead==NULL){return;}// 保存下一个节点的地址，防止链表断裂SLTNode*next=(*pphead)->next;// 释放头节点free(*pphead);// 头指针指向原头节点的下一个节点*pphead=next;}关键点：
- 删除前必须保存原头节点的下一个节点地址，否则会丢失整个链表
- 时间复杂度为
O(1)，效率高于尾删
7. 查找操作
// 查找：查找值为x的节点SLTNode*SListFind(SLTNode*phead,SLTDataType x){SLTNode*cur=phead;while(cur!=NULL){if(cur->data==x){returncur;// 找到，返回节点地址}cur=cur->next;}returnNULL;// 未找到，返回NULL}关键点：
- 查找成功返回节点地址，方便后续在该节点附近进行插入/删除操作
- 查找失败返回
NULL，调用者可以根据返回值判断是否找到目标节点
8. 指定位置前插入
// 在pos节点之前插入值为x的节点voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pos!=NULL);// 断言pos不为空，非法参数直接终止程序// 情况1：pos是头节点，等价于头插if(pos==*pphead){SListPushFront(pphead,x);}// 情况2：pos在链表中间或尾部else{// 找到pos的前一个节点prevSLTNode*prev=*pphead;while(prev!=NULL&&prev->next!=pos){prev=prev->next;}assert(prev!=NULL);// 确保pos在链表中// 创建新节点并插入SLTNode*newnode=BuySListNode(x);prev->next=newnode;newnode->next=pos;}}关键点：
- 使用
assert检查pos的合法性，调试阶段快速发现问题 - 当
pos是头节点时，直接复用头插函数，减少代码冗余 - 必须找到
pos的前驱节点prev，才能完成插入操作
9. 指定位置删除
// 删除pos位置的节点voidSListErase(SLTNode**pphead,SLTNode*pos){assert(pos!=NULL);// 情况1：pos是头节点，等价于头删if(pos==*pphead){SListPopFront(pphead);}// 情况2：pos在链表中间或尾部else{// 找到pos的前驱节点prevSLTNode*prev=*pphead;while(prev!=NULL&&prev->next!=pos){prev=prev->next;}assert(prev!=NULL);// 前驱节点的next指向pos的下一个节点prev->next=pos->next;// 释放pos节点的内存free(pos);}}关键点：
- 删除操作的核心是让前驱节点跳过pos节点，指向pos的下一个节点
- 释放
pos节点的内存，避免内存泄漏 - 同样需要处理
pos是头节点的特殊情况
五、第三步：编写测试用例（Test.c）
测试是验证代码正确性的关键步骤。我们编写一个完整的测试函数，依次调用所有链表操作函数，观察输出结果是否符合预期。
#include"SList.h"voidTestSList1(){SLTNode*plist=NULL;// 链表头指针初始化为NULL，表示空链表printf("=== 尾插操作 ===\n");SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPrint(plist);// 预期输出：1->2->3->NULLprintf("=== 头插操作 ===\n");SListPushFront(&plist,0);SListPrint(plist);// 预期输出：0->1->2->3->NULLprintf("=== 查找操作 ===\n");SLTNode*pos=SListFind(plist,2);if(pos){printf("找到节点，值为：%d\n",pos->data);// 预期输出：找到节点，值为：2}printf("=== 指定位置前插入 ===\n");SListInsert(&plist,pos,20);SListPrint(plist);// 预期输出：0->1->20->2->3->NULLprintf("=== 指定位置删除 ===\n");pos=SListFind(plist,1);SListErase(&plist,pos);SListPrint(plist);// 预期输出：0->20->2->3->NULLprintf("=== 尾删操作 ===\n");SListPopBack(&plist);SListPrint(plist);// 预期输出：0->20->2->NULLprintf("=== 头删操作 ===\n");SListPopFront(&plist);SListPrint(plist);// 预期输出：20->2->NULL}intmain(){TestSList1();return0;}编译与运行指令（Windows + MinGW）
在命令行中输入以下指令，编译并运行程序：
gcc SList.c Test.c-oSListTest SListTest.exe预期输出结果
=== 尾插操作 === 1->2->3->NULL === 头插操作 === 0->1->2->3->NULL === 查找操作 === 找到节点，值为：2 === 指定位置前插入 === 0->1->20->2->3->NULL === 指定位置删除 === 0->20->2->3->NULL === 尾删操作 === 0->20->2->NULL === 头删操作 === 20->2->NULL六、常见问题与避坑指南 🚫
在实现单向链表的过程中，新手很容易遇到以下问题，我们提前总结并给出解决方案：
| 常见问题 | 产生原因 | 解决方案 |
|---|---|---|
| 野指针问题 | 释放内存后未将指针置空；未初始化指针就使用 | 1. 释放内存后立即将指针置空 2. 指针声明时初始化为NULL |
| 链表断裂 | 头插/头删时未保存原节点的指针；尾删时未找到前驱节点 | 1. 头删前保存原头节点的下一个节点 2. 尾删时遍历到倒数第二个节点 |
| 二级指针使用错误 | 不理解为什么需要二级指针；传递一级指针导致修改无效 | 牢记：要修改一级指针的值，必须传递它的地址（二级指针） |
| 内存泄漏 | 只删除节点但不释放内存；忘记释放链表所有节点 | 1. 删除节点时调用free函数2. 程序结束前遍历链表，释放所有节点 |
| 边界情况处理不全 | 忽略空链表、单节点链表的情况 | 编写代码时，先处理空链表、单节点链表的特殊情况，再处理通用情况 |
七、进阶篇小结
恭喜你！在这篇进阶篇中，你已经成功地：
- 掌握了链表的工程化实现方法：采用头文件+源文件+测试文件的分离模式，规范代码结构。
- 理解了单向链表的核心操作逻辑：深入掌握头插、尾插、头删、尾删、查找、指定位置插入/删除的实现细节。
- 攻克了二级指针的使用难点：明白为什么需要二级指针，以及如何正确使用二级指针修改头指针。
- 学会了编写测试用例验证代码：通过测试用例快速发现并修复代码中的问题。
- 规避了链表实现的常见陷阱：掌握野指针、链表断裂、内存泄漏等问题的解决方案。
通过这次实战，你对指针的理解和C语言的编程能力都得到了一次质的飞跃。
在下一篇高阶篇中，我们将挑战结构最复杂但操作最简单的双向带头循环链表，并通过几道经典的OJ题目，如反转链表、合并有序链表、判断环形链表等，来检验和升华我们所学的知识。
敬请期待！🚀
点赞+收藏+关注，后续内容不迷路~ 你的支持是我创作的最大动力！👍
