先从一道课后题说起如果让你用 C 语言保存一组学生成绩并且要求支持“在任意位置插入一条记录”“删除指定学号的记录”你会选顺序表还是链表很多同学在学数据结构时都有过这种困惑数组用得好好的为什么要引入链表单链表Singly Linked List是数据结构课程的第一个“硬骨头”也是后续栈、队列、图、哈希链地址法等内容的基石。本文围绕“单链表的定义与实现”展开从最基础的结构体定义讲起逐步完成初始化、遍历、插入、删除、查找、释放等核心操作最后补充常见的面试变式与排错思路。如果你正在准备《数据结构》期末考试或者刚开始学习 C 语言版的数据结构这篇文章可以直接对照着敲代码。每段代码我都会说明“为什么这样写”帮助你把链表真正理解透而不是死记硬背。1. 单链表的背景与核心概念1.1 什么是单链表单链表是一种链式存储的线性表。它的逻辑顺序和物理存储顺序不一定相同每个结点除了保存数据元素之外还需要额外保存“下一个结点的地址”。为什么需要这种结构看一个对比场景操作顺序表数组单链表按下标访问第 i 个元素O(1)直接算地址O(n)需要从头遍历在头部插入元素O(n)需要搬移数据O(1)修改指针即可在中间插入元素O(n)数据搬移代价高O(1)已定位到前驱只需改指针空间分配需要预分配连续空间可能浪费或溢出按需申请空间分散但总大小灵活通俗地理解顺序表是“连续坐一排”链表是“手拉手站成一串”。数组在内存中是一块连续空间而链表通过指针把零散的内存块“串”起来。单链表结点由两部分组成数据域 data存储实际数据。指针域 next存储指向下一个结点的指针。最后一个结点的 next 指向 NULL表示链表结束。1.2 头指针与头结点的区别这是初学者最容易混淆的两个概念。头指针指向链表中第一个结点的指针变量是链表的“入口”。只要头指针丢失整条链表就无法访问了。头结点在第一个数据结点之前额外申请的一个结点data 可以不用next 指向真正的第一个数据结点。引入头结点有什么好处在第一个数据结点前插入或删除时不需要特殊处理“头指针是否改变”。空链表和非空链表的处理逻辑统一了空链表在带头结点的情况下头结点的 next 为 NULL但头指针本身始终存在。不过本文为了更清晰地展示指针变化先采用带头结点的实现方式来讲解。理解带头结点之后不带头结点的版本只需要去掉头结点在插入删除时单独处理头指针即可。1.3 单链表的常见应用场景单链表在工程中非常常见内存池的空闲块管理操作系统进程调度队列LRU 缓存淘汰算法图的邻接表存储哈希表中的链地址法多项式相加、大整数运算学习单链表实现的意义并不只是考试而是训练一种“操作指针/引用”的思维能力。2. 环境准备与工程结构2.1 开发环境本文代码使用 C 语言编写只涉及标准库不依赖平台特性。你可以在以下任意环境中运行Dev-C 5.11选择 C 语言编译选项Visual Studio创建空项目新建 .c 文件VS Code GCCMinGW-w64Linux/Mac 终端 gcc以 Linux 或 MinGW 为例gcc -o linkedlist linkedlist.c ./linkedlist版本方面没有特殊要求C89/C99 均可只要编译器支持结构体和指针即可。如果你的编译器较旧请把变量的声明集中在函数开头。2.2 示例工程结构本文用一个单文件即可演示文件结构如下linkedlist_demo/ └── linkedlist.c如果你希望拆分模块可以这样组织linkedlist_demo/ ├── linklist.h // 类型定义、函数声明 ├── linklist.c // 函数实现 └── main.c // 测试入口单文件版本调试起来更方便适合学习者多文件版本更接近企业工程风格。下面以单文件为主展开文末会贴出头文件的接口设计。2.3 编译与运行预期本文最终代码运行后将依次输出链表创建结果、遍历结果、按位置插入后的结果、按值删除后的结果、按值查找的结果以及链表释放后的提示信息。3. 单链表的定义与存储结构3.1 结点类型的结构体定义单链表结点用结构体描述。// 定义链表结点数据结构 typedef struct Node { int data; // 数据域存储整型数据 struct Node *next; // 指针域指向下一个结点 } LNode, *LinkList;这里有两个关键点struct Node *next为什么不能改成Node *next因为在结构体内部Node这个别名还没有定义完成C 语言规定结构体内部必须使用struct Node *来声明自引用指针。LNode是结点类型LinkList是指向结点的指针类型。两者指向的结构相同但在语义上区分LinkList表示“这是一个链表”LNode *表示“这是一个结点指针”。3.2 为什么 data 的类型先定义为 int教学示例中 data 用 int 最简单。实际开发中data 可以是任意类型// 学生信息结点的示例 typedef struct Student { char id[20]; char name[32]; int score; struct Student *next; } StuNode;也可以使用泛型思路用void *保存任意类型指针。本文为方便演示统一使用int。3.3 带头结点的初始化初始化一个空链表就是申请一个头结点并把 next 置空。#include stdio.h #include stdlib.h // 初始化带头结点的空链表 LinkList InitList() { LinkList L (LinkList)malloc(sizeof(LNode)); if (L NULL) { printf(内存分配失败\n); exit(1); } L-data 0; // 头结点数据域不用可置 0 L-next NULL; // 空链表 return L; }为什么头结点要申请内存因为头指针如果只是一个局部变量返回后就失效了。链表的生命力来自动态内存分配头结点也需要分配在堆上。4. 核心操作实现4.1 创建链表头插法与尾插法创建链表有两种常见方式。头插法每次把新结点插入到头结点之后。输入顺序和链表顺序相反。// 头插法建立链表输入 -1 结束 void CreateListByHead(LinkList L) { int x; printf(请输入若干整数以 -1 结束\n); while (scanf(%d, x) 1 x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data x; s-next L-next; // 新结点指向原来第一个数据结点 L-next s; // 头结点指向新结点 } }尾插法需要用一个尾指针 r 始终指向链表最后一个结点。输入顺序和链表顺序一致更符合常规逻辑。// 尾插法建立链表输入 -1 结束 void CreateListByTail(LinkList L) { LNode *r L; // r 指向尾结点初始为头结点 int x; printf(请输入若干整数以 -1 结束\n); while (scanf(%d, x) 1 x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data x; s-next NULL; r-next s; // 尾结点指向新结点 r s; // 更新尾指针 } }头插法在“单链表逆序”场景中非常有用因为头插顺序天然是反的。尾插法则用于保持输入顺序。4.2 获取链表长度遍历链表统计数据结点个数。// 求链表长度不包含头结点 int ListLength(LinkList L) { int count 0; LNode *p L-next; // 从第一个数据结点开始 while (p ! NULL) { count; p p-next; } return count; }4.3 按位置查找结点注意链表的下标习惯。实际工程中通常用 0 或 1 开始本文按学校教材习惯第 1 个数据结点为位置 1。// 按位置查找返回指向该位置结点的指针找不到返回 NULL LNode *GetElem(LinkList L, int i) { if (i 1) { return NULL; } LNode *p L-next; // 指向第一个数据结点 int j 1; while (p ! NULL j i) { p p-next; j; } return p; // 如果 p 为 NULL说明位置 i 超出链表长度 }4.4 按值查找结点// 按值查找返回第一个值为 x 的结点找不到返回 NULL LNode *LocateElem(LinkList L, int x) { LNode *p L-next; while (p ! NULL p-data ! x) { p p-next; } return p; }如果链表中的 data 是结构体无法直接用p-data ! x比较需要用专门的比较函数。这里只是演示 int 类型。4.5 在指定位置插入结点插入的关键是先找到前驱结点然后执行两步指针操作s-next p-next; p-next s;这两步顺序不能颠倒。如果先执行p-next s原后继结点就找不到了。// 在链表的第 i 个位置插入新结点data 为 x int ListInsert(LinkList L, int i, int x) { if (i 1) { printf(插入位置不合法\n); return 0; } // 寻找第 i-1 个结点即前驱 LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { // 前驱不存在 printf(插入位置超出链表长度\n); return 0; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return 0; } s-data x; s-next p-next; p-next s; return 1; }这里有个细节插入到链表末尾时前驱是尾结点尾结点的 next 为 NULL所以s-next NULL新结点自然成为新的尾结点。4.6 删除指定位置的结点删除也需要先找前驱。找到前驱后用q记录待删除结点q p-next; p-next q-next; free(q);// 删除第 i 个结点并把删除结点的值保存到 *e 中 int ListDelete(LinkList L, int i, int *e) { if (i 1) { return 0; } LNode *p L; // 从头结点开始最后 p 指向第 i-1 个结点 int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) { // 第 i 个结点不存在 return 0; } LNode *q p-next; *e q-data; p-next q-next; free(q); // 释放被删除结点的内存 return 1; }注意while条件写的是p-next ! NULL而不是p ! NULL。因为我们要找的是“第 i-1 个结点”并且要保证“第 i 个结点存在”所以必须先判断p-next。4.7 遍历链表与释放链表遍历链表// 遍历并输出链表 void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }释放链表遍历过程中记录下一个结点一边遍历一边 free。绝对不能先 free(p) 再访问 p-next。// 释放整个链表包括头结点 void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *temp p; p p-next; free(temp); } }5. 完整可运行代码5.1 完整代码单文件把上面的函数整合到一个文件中添加 main 测试函数// 文件路径linkedlist_demo/linkedlist.c #include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } LNode, *LinkList; LinkList InitList() { LinkList L (LinkList)malloc(sizeof(LNode)); if (L NULL) { printf(内存分配失败\n); exit(1); } L-data 0; L-next NULL; return L; } void CreateListByTail(LinkList L) { LNode *r L; int x; printf(请输入若干整数以 -1 结束\n); while (scanf(%d, x) 1 x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data x; s-next NULL; r-next s; r s; } } int ListLength(LinkList L) { int count 0; LNode *p L-next; while (p ! NULL) { count; p p-next; } return count; } LNode *GetElem(LinkList L, int i) { if (i 1) { return NULL; } LNode *p L-next; int j 1; while (p ! NULL j i) { p p-next; j; } return p; } LNode *LocateElem(LinkList L, int x) { LNode *p L-next; while (p ! NULL p-data ! x) { p p-next; } return p; } int ListInsert(LinkList L, int i, int x) { if (i 1) { printf(插入位置不合法\n); return 0; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { printf(插入位置超出链表长度\n); return 0; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return 0; } s-data x; s-next p-next; p-next s; return 1; } int ListDelete(LinkList L, int i, int *e) { if (i 1) { return 0; } LNode *p L; int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) { return 0; } LNode *q p-next; *e q-data; p-next q-next; free(q); return 1; } void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *temp p; p p-next; free(temp); } } int main() { LinkList L InitList(); CreateListByTail(L); printf(链表长度%d\n, ListLength(L)); printf(链表内容); PrintList(L); // 在第 2 个位置插入 100 if (ListInsert(L, 2, 100)) { printf(在第 2 个位置插入 100 后); PrintList(L); } // 查找值为 100 的结点 LNode *findNode LocateElem(L, 100); if (findNode ! NULL) { printf(找到值为 100 的结点\n); } else { printf(未找到值为 100 的结点\n); } // 删除第 3 个结点 int deletedValue; if (ListDelete(L, 3, deletedValue)) { printf(删除了第 3 个结点值为 %d删除后, deletedValue); PrintList(L); } // 释放链表 DestroyList(L); printf(链表已释放\n); return 0; }5.2 运行演示假设输入数据为10 20 30 40 -1预期输出请输入若干整数以 -1 结束 10 20 30 40 -1 链表长度4 链表内容10 20 30 40 在第 2 个位置插入 100 后10 100 20 30 40 找到值为 100 的结点 删除了第 3 个结点值为 20删除后10 100 30 40 链表已释放这里注意插入 100 之后链表为10 100 20 30 40原来第 3 个结点是 20所以删除第 3 个结点时删掉的是 20。如果直接拿着原始序列“第 3 个结点是 30”去对照会觉得输出不对这正是链表状态动态变化带来的易错点。6. 常见面试变式与进阶实验6.1 单链表逆序链表面试中出现频率最高的题目之一。核心思路从第二个数据结点开始逐个使用头插法插入到头结点之后。// 就地逆置单链表 void ReverseList(LinkList L) { if (L NULL || L-next NULL) { return; } LNode *p L-next; // p 指向当前待处理结点 LNode *q NULL; // q 保存 p 的下一个结点 L-next NULL; // 先把链表拆空 while (p ! NULL) { q p-next; // 先保存下一个结点 p-next L-next; // 头插 L-next p; p q; // 继续处理原来的下一个结点 } }测试时可以在main()中添加调用并打印结果ReverseList(L); printf(逆置后); PrintList(L);假设链表是10 20 30逆置后变成30 20 10。时间复杂度 O(n)空间复杂度 O(1)。除了迭代法还可以用递归法逆置但递归对长链表容易导致栈溢出工程上优先选择迭代。6.2 合并两个升序单链表经典题型已知两个长度为 m 和 n 的升序单链表将它们合并为一个升序链表。// 合并两个升序链表结果仍升序 LinkList MergeList(LinkList A, LinkList B) { LinkList C InitList(); LNode *pa A-next; LNode *pb B-next; LNode *pc C; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { pc-next pa; pa pa-next; } else { pc-next pb; pb pb-next; } pc pc-next; } // 把剩余结点直接接上 if (pa ! NULL) { pc-next pa; } if (pb ! NULL) { pc-next pb; } return C; }注意这种合并方式复用了原链表的结点没有为新链表额外申请内存所以最终释放时不能重复释放 A 和 B 的结点。如果不想破坏原链表就需要逐个拷贝结点。6.3 判断单链表是否有环快慢指针法slow 每次走一步fast 每次走两步。如果存在环两个指针最终会在环内相遇。// 判断是否有环 int HasCycle(LinkList L) { if (L NULL || L-next NULL) { return 0; } LNode *slow L-next; LNode *fast L-next-next; while (fast ! NULL fast-next ! NULL) { if (slow fast) { return 1; } slow slow-next; fast fast-next-next; } return 0; }快慢指针的时间复杂度是 O(n)空间复杂度 O(1)。这是比“遍历并用哈希表记录结点地址”更优的解法。7. 常见问题与排查思路7.1 程序运行时崩溃或输出无序问题现象常见原因解决思路插入操作后遍历出现乱码或崩溃新结点未初始化next是野指针插入前把s-next置为 NULL再做指针连接删除结点后链表断裂删除了头结点或没有接好前驱的后继删除前先保存p-next q-next再 free(q)遍历时死循环尾结点 next 没有置 NULL或链上出现环创建新结点时s-next NULL检查是否误把某个结点 next 指回前面链表“插入位置超出”判断不准确前驱查找条件写错插入第 i 个结点时前驱是第 i-1 个结点用位置计数器逐步验证释放后仍访问链表悬空指针释放后把指针置 NULL或不再访问该指针7.2 scanf 吸收换行符的问题如果上面代码运行后第一次输入没有响应可能是输入缓冲区残留了换行符。在教学环境中最简单的方式是保持输入格式为“连续输入数字最后输 -1”不要混用字符输入。7.3 内存泄漏如何检测C 语言没有自动垃圾回收每次 malloc 都要对应 free。可以使用工具检测Linux 下用 valgrindvalgrind --leak-checkfull ./linkedlistWindows 下用 Visual Studio 的 CRT 调试或者 VLDVisual Leak Detector养成“写完链表操作后遍历检查是否每个 malloc 都释放”的习惯。8. 最佳实践与工程建议8.1 统一使用头结点在实际工程中带头结点的单链表能大幅简化边界条件处理。插入删除时不再需要为“第一个数据结点”单独写 if 分支。8.2 函数接口设计推荐把“链表专用接口”定义到头文件中便于复用// 文件路径linkedlist_demo/linklist.h #ifndef LINKLIST_H #define LINKLIST_H typedef struct Node { int data; struct Node *next; } LNode, *LinkList; LinkList InitList(); void CreateListByTail(LinkList L); void CreateListByHead(LinkList L); int ListLength(LinkList L); LNode *GetElem(LinkList L, int i); LNode *LocateElem(LinkList L, int x); int ListInsert(LinkList L, int i, int x); int ListDelete(LinkList L, int i, int *e); void PrintList(LinkList L); void DestroyList(LinkList L); #endif模块化之后业务代码只需要包含头文件不需要关心内部指针如何跳转。8.3 插入删除时保证“安全顺序”口诀先接后继再改前驱。插入时s-next p-next; p-next s;删除时p-next q-next;这两行顺序错不得。很多初学者写成p-next s; s-next p-next; // 错误p-next 已经变成 s 了这时候 s 的 next 指向自己形成一个环。8.4 边界条件测试清单每实现一个函数至少测试以下场景空链表操作只包含一个数据结点操作位置为 1操作位置为链表长度操作位置为链表长度 1越界删除最后一个结点后链表变空8.5 动态内存管理的安全习惯写链表代码时时刻问自己三个问题每个 malloc 是否都有对应的 free释放之后是否还会有指针指向这块内存如果 malloc 失败程序是否安全退出这种习惯能避免绝大多数“野指针”“内存泄漏”“重复释放”的坑。9. 总结本文围绕“单链表的定义与实现”做了完整梳理单链表的基本概念结点、头指针、头结点、链式存储结构体定义方式struct Node *next的自引用核心操作实现初始化、头插、尾插、遍历、查找、插入、删除、释放完整可运行的 C 语言示例经典面试变式链表逆序、两个升序链表合并、环检测常见崩溃与内存问题的排查思路链表的核心不在于语法而在于指针变化的顺序和边界条件的处理。建议你亲手在纸上画出每一步插入、删除的箭头变化再对照代码逐步验证。下一步可以继续学习双向链表、循环链表、静态链表以及用链表实现栈和队列在熟悉 C 语言版本后也可以用 Python 写一遍同样的操作对比两种语言在“指针/引用”处理上的差异。如果在练习过程中遇到 “Segmentation fault” 或内存泄漏不用慌按照本文第 7 节的排查表逐项检查大多数问题都出在“忘记把新结点的 next 置空”或“释放前没有保存后继地址”这两类操作上。单链表只是数据结构的开始把它彻底搞懂后面很多内容会顺利很多。
先从一道课后题说起如果让你用 C 语言保存一组学生成绩并且要求支持“在任意位置插入一条记录”“删除指定学号的记录”你会选顺序表还是链表很多同学在学数据结构时都有过这种困惑数组用得好好的为什么要引入链表单链表Singly Linked List是数据结构课程的第一个“硬骨头”也是后续栈、队列、图、哈希链地址法等内容的基石。本文围绕“单链表的定义与实现”展开从最基础的结构体定义讲起逐步完成初始化、遍历、插入、删除、查找、释放等核心操作最后补充常见的面试变式与排错思路。如果你正在准备《数据结构》期末考试或者刚开始学习 C 语言版的数据结构这篇文章可以直接对照着敲代码。每段代码我都会说明“为什么这样写”帮助你把链表真正理解透而不是死记硬背。1. 单链表的背景与核心概念1.1 什么是单链表单链表是一种链式存储的线性表。它的逻辑顺序和物理存储顺序不一定相同每个结点除了保存数据元素之外还需要额外保存“下一个结点的地址”。为什么需要这种结构看一个对比场景操作顺序表数组单链表按下标访问第 i 个元素O(1)直接算地址O(n)需要从头遍历在头部插入元素O(n)需要搬移数据O(1)修改指针即可在中间插入元素O(n)数据搬移代价高O(1)已定位到前驱只需改指针空间分配需要预分配连续空间可能浪费或溢出按需申请空间分散但总大小灵活通俗地理解顺序表是“连续坐一排”链表是“手拉手站成一串”。数组在内存中是一块连续空间而链表通过指针把零散的内存块“串”起来。单链表结点由两部分组成数据域 data存储实际数据。指针域 next存储指向下一个结点的指针。最后一个结点的 next 指向 NULL表示链表结束。1.2 头指针与头结点的区别这是初学者最容易混淆的两个概念。头指针指向链表中第一个结点的指针变量是链表的“入口”。只要头指针丢失整条链表就无法访问了。头结点在第一个数据结点之前额外申请的一个结点data 可以不用next 指向真正的第一个数据结点。引入头结点有什么好处在第一个数据结点前插入或删除时不需要特殊处理“头指针是否改变”。空链表和非空链表的处理逻辑统一了空链表在带头结点的情况下头结点的 next 为 NULL但头指针本身始终存在。不过本文为了更清晰地展示指针变化先采用带头结点的实现方式来讲解。理解带头结点之后不带头结点的版本只需要去掉头结点在插入删除时单独处理头指针即可。1.3 单链表的常见应用场景单链表在工程中非常常见内存池的空闲块管理操作系统进程调度队列LRU 缓存淘汰算法图的邻接表存储哈希表中的链地址法多项式相加、大整数运算学习单链表实现的意义并不只是考试而是训练一种“操作指针/引用”的思维能力。2. 环境准备与工程结构2.1 开发环境本文代码使用 C 语言编写只涉及标准库不依赖平台特性。你可以在以下任意环境中运行Dev-C 5.11选择 C 语言编译选项Visual Studio创建空项目新建 .c 文件VS Code GCCMinGW-w64Linux/Mac 终端 gcc以 Linux 或 MinGW 为例gcc -o linkedlist linkedlist.c ./linkedlist版本方面没有特殊要求C89/C99 均可只要编译器支持结构体和指针即可。如果你的编译器较旧请把变量的声明集中在函数开头。2.2 示例工程结构本文用一个单文件即可演示文件结构如下linkedlist_demo/ └── linkedlist.c如果你希望拆分模块可以这样组织linkedlist_demo/ ├── linklist.h // 类型定义、函数声明 ├── linklist.c // 函数实现 └── main.c // 测试入口单文件版本调试起来更方便适合学习者多文件版本更接近企业工程风格。下面以单文件为主展开文末会贴出头文件的接口设计。2.3 编译与运行预期本文最终代码运行后将依次输出链表创建结果、遍历结果、按位置插入后的结果、按值删除后的结果、按值查找的结果以及链表释放后的提示信息。3. 单链表的定义与存储结构3.1 结点类型的结构体定义单链表结点用结构体描述。// 定义链表结点数据结构 typedef struct Node { int data; // 数据域存储整型数据 struct Node *next; // 指针域指向下一个结点 } LNode, *LinkList;这里有两个关键点struct Node *next为什么不能改成Node *next因为在结构体内部Node这个别名还没有定义完成C 语言规定结构体内部必须使用struct Node *来声明自引用指针。LNode是结点类型LinkList是指向结点的指针类型。两者指向的结构相同但在语义上区分LinkList表示“这是一个链表”LNode *表示“这是一个结点指针”。3.2 为什么 data 的类型先定义为 int教学示例中 data 用 int 最简单。实际开发中data 可以是任意类型// 学生信息结点的示例 typedef struct Student { char id[20]; char name[32]; int score; struct Student *next; } StuNode;也可以使用泛型思路用void *保存任意类型指针。本文为方便演示统一使用int。3.3 带头结点的初始化初始化一个空链表就是申请一个头结点并把 next 置空。#include stdio.h #include stdlib.h // 初始化带头结点的空链表 LinkList InitList() { LinkList L (LinkList)malloc(sizeof(LNode)); if (L NULL) { printf(内存分配失败\n); exit(1); } L-data 0; // 头结点数据域不用可置 0 L-next NULL; // 空链表 return L; }为什么头结点要申请内存因为头指针如果只是一个局部变量返回后就失效了。链表的生命力来自动态内存分配头结点也需要分配在堆上。4. 核心操作实现4.1 创建链表头插法与尾插法创建链表有两种常见方式。头插法每次把新结点插入到头结点之后。输入顺序和链表顺序相反。// 头插法建立链表输入 -1 结束 void CreateListByHead(LinkList L) { int x; printf(请输入若干整数以 -1 结束\n); while (scanf(%d, x) 1 x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data x; s-next L-next; // 新结点指向原来第一个数据结点 L-next s; // 头结点指向新结点 } }尾插法需要用一个尾指针 r 始终指向链表最后一个结点。输入顺序和链表顺序一致更符合常规逻辑。// 尾插法建立链表输入 -1 结束 void CreateListByTail(LinkList L) { LNode *r L; // r 指向尾结点初始为头结点 int x; printf(请输入若干整数以 -1 结束\n); while (scanf(%d, x) 1 x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data x; s-next NULL; r-next s; // 尾结点指向新结点 r s; // 更新尾指针 } }头插法在“单链表逆序”场景中非常有用因为头插顺序天然是反的。尾插法则用于保持输入顺序。4.2 获取链表长度遍历链表统计数据结点个数。// 求链表长度不包含头结点 int ListLength(LinkList L) { int count 0; LNode *p L-next; // 从第一个数据结点开始 while (p ! NULL) { count; p p-next; } return count; }4.3 按位置查找结点注意链表的下标习惯。实际工程中通常用 0 或 1 开始本文按学校教材习惯第 1 个数据结点为位置 1。// 按位置查找返回指向该位置结点的指针找不到返回 NULL LNode *GetElem(LinkList L, int i) { if (i 1) { return NULL; } LNode *p L-next; // 指向第一个数据结点 int j 1; while (p ! NULL j i) { p p-next; j; } return p; // 如果 p 为 NULL说明位置 i 超出链表长度 }4.4 按值查找结点// 按值查找返回第一个值为 x 的结点找不到返回 NULL LNode *LocateElem(LinkList L, int x) { LNode *p L-next; while (p ! NULL p-data ! x) { p p-next; } return p; }如果链表中的 data 是结构体无法直接用p-data ! x比较需要用专门的比较函数。这里只是演示 int 类型。4.5 在指定位置插入结点插入的关键是先找到前驱结点然后执行两步指针操作s-next p-next; p-next s;这两步顺序不能颠倒。如果先执行p-next s原后继结点就找不到了。// 在链表的第 i 个位置插入新结点data 为 x int ListInsert(LinkList L, int i, int x) { if (i 1) { printf(插入位置不合法\n); return 0; } // 寻找第 i-1 个结点即前驱 LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { // 前驱不存在 printf(插入位置超出链表长度\n); return 0; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return 0; } s-data x; s-next p-next; p-next s; return 1; }这里有个细节插入到链表末尾时前驱是尾结点尾结点的 next 为 NULL所以s-next NULL新结点自然成为新的尾结点。4.6 删除指定位置的结点删除也需要先找前驱。找到前驱后用q记录待删除结点q p-next; p-next q-next; free(q);// 删除第 i 个结点并把删除结点的值保存到 *e 中 int ListDelete(LinkList L, int i, int *e) { if (i 1) { return 0; } LNode *p L; // 从头结点开始最后 p 指向第 i-1 个结点 int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) { // 第 i 个结点不存在 return 0; } LNode *q p-next; *e q-data; p-next q-next; free(q); // 释放被删除结点的内存 return 1; }注意while条件写的是p-next ! NULL而不是p ! NULL。因为我们要找的是“第 i-1 个结点”并且要保证“第 i 个结点存在”所以必须先判断p-next。4.7 遍历链表与释放链表遍历链表// 遍历并输出链表 void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }释放链表遍历过程中记录下一个结点一边遍历一边 free。绝对不能先 free(p) 再访问 p-next。// 释放整个链表包括头结点 void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *temp p; p p-next; free(temp); } }5. 完整可运行代码5.1 完整代码单文件把上面的函数整合到一个文件中添加 main 测试函数// 文件路径linkedlist_demo/linkedlist.c #include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } LNode, *LinkList; LinkList InitList() { LinkList L (LinkList)malloc(sizeof(LNode)); if (L NULL) { printf(内存分配失败\n); exit(1); } L-data 0; L-next NULL; return L; } void CreateListByTail(LinkList L) { LNode *r L; int x; printf(请输入若干整数以 -1 结束\n); while (scanf(%d, x) 1 x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data x; s-next NULL; r-next s; r s; } } int ListLength(LinkList L) { int count 0; LNode *p L-next; while (p ! NULL) { count; p p-next; } return count; } LNode *GetElem(LinkList L, int i) { if (i 1) { return NULL; } LNode *p L-next; int j 1; while (p ! NULL j i) { p p-next; j; } return p; } LNode *LocateElem(LinkList L, int x) { LNode *p L-next; while (p ! NULL p-data ! x) { p p-next; } return p; } int ListInsert(LinkList L, int i, int x) { if (i 1) { printf(插入位置不合法\n); return 0; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) { printf(插入位置超出链表长度\n); return 0; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return 0; } s-data x; s-next p-next; p-next s; return 1; } int ListDelete(LinkList L, int i, int *e) { if (i 1) { return 0; } LNode *p L; int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) { return 0; } LNode *q p-next; *e q-data; p-next q-next; free(q); return 1; } void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *temp p; p p-next; free(temp); } } int main() { LinkList L InitList(); CreateListByTail(L); printf(链表长度%d\n, ListLength(L)); printf(链表内容); PrintList(L); // 在第 2 个位置插入 100 if (ListInsert(L, 2, 100)) { printf(在第 2 个位置插入 100 后); PrintList(L); } // 查找值为 100 的结点 LNode *findNode LocateElem(L, 100); if (findNode ! NULL) { printf(找到值为 100 的结点\n); } else { printf(未找到值为 100 的结点\n); } // 删除第 3 个结点 int deletedValue; if (ListDelete(L, 3, deletedValue)) { printf(删除了第 3 个结点值为 %d删除后, deletedValue); PrintList(L); } // 释放链表 DestroyList(L); printf(链表已释放\n); return 0; }5.2 运行演示假设输入数据为10 20 30 40 -1预期输出请输入若干整数以 -1 结束 10 20 30 40 -1 链表长度4 链表内容10 20 30 40 在第 2 个位置插入 100 后10 100 20 30 40 找到值为 100 的结点 删除了第 3 个结点值为 20删除后10 100 30 40 链表已释放这里注意插入 100 之后链表为10 100 20 30 40原来第 3 个结点是 20所以删除第 3 个结点时删掉的是 20。如果直接拿着原始序列“第 3 个结点是 30”去对照会觉得输出不对这正是链表状态动态变化带来的易错点。6. 常见面试变式与进阶实验6.1 单链表逆序链表面试中出现频率最高的题目之一。核心思路从第二个数据结点开始逐个使用头插法插入到头结点之后。// 就地逆置单链表 void ReverseList(LinkList L) { if (L NULL || L-next NULL) { return; } LNode *p L-next; // p 指向当前待处理结点 LNode *q NULL; // q 保存 p 的下一个结点 L-next NULL; // 先把链表拆空 while (p ! NULL) { q p-next; // 先保存下一个结点 p-next L-next; // 头插 L-next p; p q; // 继续处理原来的下一个结点 } }测试时可以在main()中添加调用并打印结果ReverseList(L); printf(逆置后); PrintList(L);假设链表是10 20 30逆置后变成30 20 10。时间复杂度 O(n)空间复杂度 O(1)。除了迭代法还可以用递归法逆置但递归对长链表容易导致栈溢出工程上优先选择迭代。6.2 合并两个升序单链表经典题型已知两个长度为 m 和 n 的升序单链表将它们合并为一个升序链表。// 合并两个升序链表结果仍升序 LinkList MergeList(LinkList A, LinkList B) { LinkList C InitList(); LNode *pa A-next; LNode *pb B-next; LNode *pc C; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { pc-next pa; pa pa-next; } else { pc-next pb; pb pb-next; } pc pc-next; } // 把剩余结点直接接上 if (pa ! NULL) { pc-next pa; } if (pb ! NULL) { pc-next pb; } return C; }注意这种合并方式复用了原链表的结点没有为新链表额外申请内存所以最终释放时不能重复释放 A 和 B 的结点。如果不想破坏原链表就需要逐个拷贝结点。6.3 判断单链表是否有环快慢指针法slow 每次走一步fast 每次走两步。如果存在环两个指针最终会在环内相遇。// 判断是否有环 int HasCycle(LinkList L) { if (L NULL || L-next NULL) { return 0; } LNode *slow L-next; LNode *fast L-next-next; while (fast ! NULL fast-next ! NULL) { if (slow fast) { return 1; } slow slow-next; fast fast-next-next; } return 0; }快慢指针的时间复杂度是 O(n)空间复杂度 O(1)。这是比“遍历并用哈希表记录结点地址”更优的解法。7. 常见问题与排查思路7.1 程序运行时崩溃或输出无序问题现象常见原因解决思路插入操作后遍历出现乱码或崩溃新结点未初始化next是野指针插入前把s-next置为 NULL再做指针连接删除结点后链表断裂删除了头结点或没有接好前驱的后继删除前先保存p-next q-next再 free(q)遍历时死循环尾结点 next 没有置 NULL或链上出现环创建新结点时s-next NULL检查是否误把某个结点 next 指回前面链表“插入位置超出”判断不准确前驱查找条件写错插入第 i 个结点时前驱是第 i-1 个结点用位置计数器逐步验证释放后仍访问链表悬空指针释放后把指针置 NULL或不再访问该指针7.2 scanf 吸收换行符的问题如果上面代码运行后第一次输入没有响应可能是输入缓冲区残留了换行符。在教学环境中最简单的方式是保持输入格式为“连续输入数字最后输 -1”不要混用字符输入。7.3 内存泄漏如何检测C 语言没有自动垃圾回收每次 malloc 都要对应 free。可以使用工具检测Linux 下用 valgrindvalgrind --leak-checkfull ./linkedlistWindows 下用 Visual Studio 的 CRT 调试或者 VLDVisual Leak Detector养成“写完链表操作后遍历检查是否每个 malloc 都释放”的习惯。8. 最佳实践与工程建议8.1 统一使用头结点在实际工程中带头结点的单链表能大幅简化边界条件处理。插入删除时不再需要为“第一个数据结点”单独写 if 分支。8.2 函数接口设计推荐把“链表专用接口”定义到头文件中便于复用// 文件路径linkedlist_demo/linklist.h #ifndef LINKLIST_H #define LINKLIST_H typedef struct Node { int data; struct Node *next; } LNode, *LinkList; LinkList InitList(); void CreateListByTail(LinkList L); void CreateListByHead(LinkList L); int ListLength(LinkList L); LNode *GetElem(LinkList L, int i); LNode *LocateElem(LinkList L, int x); int ListInsert(LinkList L, int i, int x); int ListDelete(LinkList L, int i, int *e); void PrintList(LinkList L); void DestroyList(LinkList L); #endif模块化之后业务代码只需要包含头文件不需要关心内部指针如何跳转。8.3 插入删除时保证“安全顺序”口诀先接后继再改前驱。插入时s-next p-next; p-next s;删除时p-next q-next;这两行顺序错不得。很多初学者写成p-next s; s-next p-next; // 错误p-next 已经变成 s 了这时候 s 的 next 指向自己形成一个环。8.4 边界条件测试清单每实现一个函数至少测试以下场景空链表操作只包含一个数据结点操作位置为 1操作位置为链表长度操作位置为链表长度 1越界删除最后一个结点后链表变空8.5 动态内存管理的安全习惯写链表代码时时刻问自己三个问题每个 malloc 是否都有对应的 free释放之后是否还会有指针指向这块内存如果 malloc 失败程序是否安全退出这种习惯能避免绝大多数“野指针”“内存泄漏”“重复释放”的坑。9. 总结本文围绕“单链表的定义与实现”做了完整梳理单链表的基本概念结点、头指针、头结点、链式存储结构体定义方式struct Node *next的自引用核心操作实现初始化、头插、尾插、遍历、查找、插入、删除、释放完整可运行的 C 语言示例经典面试变式链表逆序、两个升序链表合并、环检测常见崩溃与内存问题的排查思路链表的核心不在于语法而在于指针变化的顺序和边界条件的处理。建议你亲手在纸上画出每一步插入、删除的箭头变化再对照代码逐步验证。下一步可以继续学习双向链表、循环链表、静态链表以及用链表实现栈和队列在熟悉 C 语言版本后也可以用 Python 写一遍同样的操作对比两种语言在“指针/引用”处理上的差异。如果在练习过程中遇到 “Segmentation fault” 或内存泄漏不用慌按照本文第 7 节的排查表逐项检查大多数问题都出在“忘记把新结点的 next 置空”或“释放前没有保存后继地址”这两类操作上。单链表只是数据结构的开始把它彻底搞懂后面很多内容会顺利很多。
