1. 为什么要单独把“查、插、删”拎出来讲如果你正在学数据结构或者正在复习考研《数据结构》里的线性表章节应该对“单链表”不陌生。很多同学刚开始接触链表时会觉得定义非常简单struct LNode { int data; struct LNode *next; };一个数据域一个指针域每个节点通过 next 指针串起来。但一旦开始写代码问题就来了为什么插入节点时语句顺序不能颠倒为什么删除节点后要 free()为什么按位置查找时循环条件要写成p ! NULL而不是p-next ! NULL问题不大但每一个都可能让程序直接崩溃或者在考试、面试时丢掉关键分数。本文围绕单链表最基本的三种操作——查找、插入、删除——展开。你可以把这篇文章当成一份“带解析的链表操作速查手册”也可以当成一个“从零到完整可运行程序的实战教程”。我会把每一步的思路、指针变化、边界情况、常见错误都拆开讲适合正在学习数据结构的新手也适合准备考研复试或面试前快速复习的同学。在继续阅读之前建议你先打开 IDE准备好一个 C 语言编译环境。因为链表操作光看文字很难形成感觉亲手写一遍、跑一遍比单纯记忆结论要有效得多。2. 环境准备与结构定义2.1 编译环境说明本文示例代码使用 C 语言编写因为国内数据结构教材大多使用 C/C 描述算法考试和面试也通常要求用 C 风格实现。你需要准备GCC 编译器或者任何一个支持 C99 标准的 IDE常用选择Dev-C、Code::Blocks、Visual Studio、VS Code C/C 插件不需要额外安装第三方库代码全部基于标准 C。版本不需要过于纠结。链表操作是非常基础且稳定的内容不同编译器之间几乎没有差异。重点在于理解指针和内存管理。2.2 定义链表结构体创建项目后我们建议把结构体定义、函数声明和主函数分开。不过为了演示方便本文先用一个头文件风格的结构说明完整代码最后给出单个 main.c 的综合程序。结构体定义如下// 文件路径LinkList.h #ifndef LINKLIST_H #define LINKLIST_H #include stdio.h #include stdlib.h #include stdbool.h // 单链表节点定义 typedef struct LNode { int data; // 数据域这里以 int 为例 struct LNode *next; // 指针域指向下一个节点 } LNode; // 给指向节点的指针起个别名方便书写 typedef LNode* LinkList; #endif这里有个常见问题LinkList到底是结构体还是指针从上面定义可以看出LinkList就是LNode*也就是一个指向头节点的指针。有些教材用LinkList L表示头指针用LNode *p表示工作指针二者本质相同不要被名字绕晕。2.3 初始化一个带头节点的链表在实现查找、插入、删除之前需要先有链表。为了统一操作逻辑本文采用“带头节点”的方式。头节点不存放有效数据它的 next 指向第一个实际节点。好处是插入和删除第一个节点时不需要单独修改头指针代码可以统一处理。初始化函数// 初始化带头节点的空链表 void InitList(LinkList *L) { // 分配头节点 *L (LNode*)malloc(sizeof(LNode)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next NULL; }这段代码为什么要用二级指针LinkList *L因为我们需要在函数内部修改L本身的值让它指向新分配的头节点。如果只传LinkList L形参和外界的实参互不相干函数结束之后L依然是原来的野指针。这一点也是链表入门最常见的困惑之一。3. 单链表的查找操作查找是线性表最基础的操作之一。单链表查找分为两种按位置查找找到第 i 个节点按值查找找到第一个值为 目标值 的节点。由于单链表只能从前往后遍历两种查找的时间复杂度都是 O(n)。3.1 按位置查找按位置查找的含义是给定位置 ii 从 1 开始返回第 i 个节点的指针。如果 i 不合法返回 NULL。先看代码// 按位置查找返回第 i 个节点的指针i 从 1 开始 LNode* GetElem(LinkList L, int i) { if (i 1) { return NULL; } int j 0; // 当前指向的是第 j 个节点 LNode *p L; // p 从头节点开始 // 从头节点开始向后移动直到 p 为空 或 j i while (p ! NULL j i) { p p-next; j; } return p; // 如果 i 超过链表长度p 为 NULL }这个代码是经典写法。我们来拆解循环的终止条件如果p NULL说明已经走到链表尾部还没找到第 i 个节点说明 i 越界如果j i说明 p 正好指向第 i 个节点。注意一个重要细节这里返回的可能是 NULL。调用方在使用返回值之前必须判断否则对 NULL 取-data会直接触发段错误。测试代码void TestGetElem(LinkList L) { LNode *p GetElem(L, 3); if (p ! NULL) { printf(第 3 个节点的值是%d\n, p-data); } else { printf(第 3 个节点不存在\n); } }3.2 按值查找按值查找的逻辑更直观从第一个实际节点开始依次比较每个节点的 data找到第一个等于目标值的节点返回它的指针找不到则返回 NULL。// 按值查找返回第一个值为 e 的节点指针找不到返回 NULL LNode* LocateElem(LinkList L, int e) { LNode *p L-next; // 跳过带头节点 while (p ! NULL p-data ! e) { p p-next; } return p; }这段代码要注意一点为什么把p L-next而不是p L因为头节点不参与数据比较。如果从头节点开始的话万一头节点的 data 恰好等于目标值就会返回错误结果。3.3 查找操作的时间复杂度与边界情况时间复杂度查找第 i 个节点需要移动 i 次查找指定值最多需要遍历整个链表平均时间复杂度都是 O(n)。这个结论需要记住因为很多面试题会在此基础上延伸比如“查找链表倒数第 k 个节点”“找到链表中间节点”等。边界情况总结场景结果i 1返回 NULLi 0返回头节点有些算法题会用到i 超过链表长度循环终止返回 NULL链表为空按值查找返回 NULL查找值不存在返回 NULL不要觉得返回 NULL 是代码的“缺陷”恰恰相反返回 NULL 是给调用方的明确信号。凡是调用查找函数都要养成判断空指针的习惯。4. 单链表的插入操作插入是单链表操作中最容易出错的环节。很多初学者在写插入代码时经常出现“链表断成两截”的现象原因就是没有理解指针赋值的执行顺序。4.1 插入操作的本质单链表的插入本质上是修改节点的 next 指针让新节点“插入”到两个已有节点之间。假设要在节点 p 的后面插入一个新节点 s需要两步s-next p-next; // 第一步新节点先指向 p 原来的后继节点 p-next s; // 第二步p 的 next 改为指向新节点这两步的顺序不能颠倒。如果把第二步写在前面p-next s; // 错误这会丢失 p 原来的后继节点地址 s-next p-next; // 此时 p-next 已经是 ss-next 指向自己链表从中间断开后续节点全部丢失而且 s-next 指向自己一遍历就死循环。这是初学链表时最常见的错误之一。4.2 头插法插入节点头插法把新节点插入到头节点之后也就是链表的起始位置。头插法不需要遍历链表时间复杂度 O(1)。// 头插法在链表头部插入节点e 是新节点数据 void HeadInsert(LinkList L, int e) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data e; // 核心插入步骤 s-next L-next; L-next s; }这种插入方式有一个特点后插入的节点反而排在前面。所以如果连续调用HeadInsert(L, 1)、HeadInsert(L, 2)、HeadInsert(L, 3)最终链表顺序是 3 2 1。很多算法题用头插法实现链表逆序思路就是从原链表中逐个取出节点再用头插法插到新链表中。4.3 尾插法插入节点如果需要保持插入顺序可以用尾插法。尾插法需要先找到最后一个节点再把新节点挂在末尾。// 尾插法在链表末尾插入节点 void TailInsert(LinkList L, int e) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data e; s-next NULL; // 找到最后一个节点 LNode *p L; while (p-next ! NULL) { p p-next; } p-next s; }尾插法每次都需要从头遍历到尾时间复杂度 O(n)。如果在一个循环中插入 n 个元素总时间复杂度是 O(n²)。如果需要频繁尾插更好的做法是额外维护一个尾指针tail每次插入后更新 tail这样单次插入就是 O(1)。4.4 在指定位置插入节点按位置插入可以理解为“先找位置再做插入”。思路如下找到第 i-1 个节点也就是待插入位置的前驱节点判断前驱节点是否存在执行核心插入步骤。// 在链表的第 i 个位置插入节点数据为 e bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } // 查找第 i-1 个节点 LNode *p GetElem(L, i - 1); if (p NULL) { printf(插入位置不合法\n); return false; } // 创建新节点 LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; // 核心插入步骤 s-next p-next; p-next s; return true; }这里用到了前面实现的GetElem函数。注意GetElem(L, i-1)返回的是前驱节点。如果前驱节点为空说明 i 超出了链表长度范围。举个例子链表当前是1 - 3 - 4执行ListInsert(L, 2, 2)GetElem(L, 1)找到值为 1 的节点新建节点 sdata 2s-next p-next此时 s-next 指向值为 3 的节点p-next s值为 1 的节点指向新节点。最终链表变为1 - 2 - 3 - 4。4.5 插入操作的时间复杂度头插法O(1)尾插法O(n)维护尾指针后可以做到 O(1)指定位置插入定位需要 O(n)插入本身 O(1)总复杂度 O(n)。对于“在指定节点后插入”这种已知节点指针的情况插入操作本身是 O(1)。很多考试题就问这一点给定节点 p如何在 O(1) 时间内在 p 后面插入节点答案就是上面那两句赋值语句不包含查找过程。5. 单链表的删除操作删除操作的核心是先找到待删除节点的前驱节点然后让前驱节点跳过待删除节点直接指向待删除节点的下一个节点最后释放待删除节点的内存。5.1 删除指定位置节点删除第 i 个节点// 删除链表的第 i 个节点并用 e 返回被删除节点的数据 bool ListDelete(LinkList L, int i, int *e) { if (i 1) { return false; } // 找到第 i-1 个节点即待删除节点的前驱 LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) { printf(删除位置不合法\n); return false; } LNode *q p-next; // q 指向待删除节点 *e q-data; // 保存被删除节点的值 p-next q-next; // 前驱节点跳过 q指向 q 的后继 free(q); // 释放 q 的内存 return true; }注意这里有两个判断p NULL前驱节点不存在位置太靠后p-next NULL前驱节点是最后一个节点后面没有可删除的节点。把这两步合并写成if (p NULL || p-next NULL)是标准写法。漏掉任何一个判断都可能产生空指针访问。free(q)这一步非常关键。C 语言中malloc 分配的内存必须由 free 释放。如果不释放每删除一个节点就泄漏一块内存程序长时间运行后内存占用会越来越大。而释放之后不能让 p 继续指向 q因为 q 已经成为一个悬空指针dangling pointer。5.2 按值删除节点按值删除的实现思路从第一个实际节点开始遍历找到第一个数据等于目标值的节点删除这个节点。但问题是我们要找到的是待删除节点本身还是它的前驱答案是前驱。因为删除操作需要修改前驱节点的 next 指针。// 删除第一个值为 e 的节点 bool DeleteByValue(LinkList L, int e) { LNode *p L; // p 指向头节点 LNode *q NULL; // q 用来临时保存待删除节点 // 从头开始遍历p 始终是当前节点的前驱 while (p-next ! NULL) { if (p-next-data e) { q p-next; p-next q-next; free(q); return true; } p p-next; } return false; // 没找到值为 e 的节点 }这里使用p-next-data进行比较这样 p 始终是待删除节点的前驱。一旦找到目标节点直接让 p-next 跳过它。这个技巧在链表类算法题中非常常用。5.3 删除操作的时间复杂度删除指定位置节点查找前驱 O(n)删除 O(1)总复杂度 O(n)。如果已经给出了待删除节点的前驱指针删除本身只要两句话q p-next; p-next q-next; free(q);这是 O(1) 操作。如果题目要求 O(1) 时间删除某个给定指针指向的节点不提供前驱可以用“值覆盖法”// 只给定节点指针 delO(1) 删除该节点 // 思路用后继节点的值覆盖当前节点再删除后继节点 bool DeleteNodeO1(LNode *del) { if (del NULL || del-next NULL) { return false; // 无法处理尾节点 } LNode *nextNode del-next; del-data nextNode-data; del-next nextNode-next; free(nextNode); return true; }这种做法的本质是“偷天换日”把后继节点的数据复制到当前节点然后删除后继节点。它要求待删除节点不能是尾节点因为尾节点没有后继可以用来顶替。6. 完整可运行的综合示例前面把每个操作拆开讲解下面给出一个完整的可运行程序。这个程序把链表初始化、头插、尾插、按位插入、按位删除、查找、打印等功能整合在一起你可以直接复制到本地运行。// 文件路径main.c #include stdio.h #include stdlib.h #include stdbool.h // 单链表节点定义 typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 初始化带头节点的空链表 void InitList(LinkList *L) { *L (LNode*)malloc(sizeof(LNode)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next NULL; } // 尾插法建立链表依次插入数组 a 中的 n 个元素 void CreateListByTail(LinkList L, int a[], int n) { LNode *tail L; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data a[i]; s-next NULL; tail-next s; tail s; } } // 按位置查找返回第 i 个节点指针i 从 1 开始 LNode* GetElem(LinkList L, int i) { if (i 1) { return NULL; } int j 0; LNode *p L; while (p ! NULL j i) { p p-next; j; } return p; } // 按值查找返回第一个值为 e 的节点指针 LNode* LocateElem(LinkList L, int e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; } // 在指定位置插入 bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p GetElem(L, i - 1); if (p NULL) { return false; } LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next p-next; p-next s; return true; } // 删除指定位置节点 bool ListDelete(LinkList L, int i, int *e) { if (i 1) { return false; } LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) { return false; } LNode *q p-next; *e q-data; p-next q-next; free(q); return true; } // 打印链表所有节点 void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } int main() { LinkList L; InitList(L); // 通过尾插法创建链表1 2 3 4 5 int a[] {1, 2, 3, 4, 5}; CreateListByTail(L, a, 5); printf(初始链表); PrintList(L); // 测试插入在第 2 个位置插入 99 if (ListInsert(L, 2, 99)) { printf(在第 2 个位置插入 99 后); PrintList(L); } // 测试查找查找第 3 个节点 LNode *p GetElem(L, 3); if (p ! NULL) { printf(第 3 个节点的值是%d\n, p-data); } else { printf(第 3 个节点不存在\n); } // 测试按值查找查找 99 p LocateElem(L, 99); if (p ! NULL) { printf(找到值为 99 的节点它的下一个节点是); if (p-next ! NULL) { printf(%d\n, p-next-data); } else { printf(NULL\n); } } else { printf(未找到值为 99 的节点\n); } // 测试删除删除第 2 个节点 int delVal 0; if (ListDelete(L, 2, delVal)) { printf(删除第 2 个节点值为 %d删除后, delVal); PrintList(L); } return 0; }预期输出初始链表1 2 3 4 5 在第 2 个位置插入 99 后1 99 2 3 4 5 第 3 个节点的值是2 找到值为 99 的节点它的下一个节点是2 删除第 2 个节点值为 99删除后1 2 3 4 5运行结果符合预期插入 99 后链表变成1 99 2 3 4 5查找第 3 个节点时由于 99 插入到了第 2 个位置原来的 2 变成了第 3 个节点按值查找 99 后可以访问其后继节点删除第 2 个节点后链表恢复成初始顺序。这里有一个细节值得注意插入和删除操作会改变节点位置。所以“第 2 个节点”在不同操作之间指的对象可能是不同的。写算法时一定要区分“按值定位”和“按位置定位”之间的区别。7. 常见问题与排查思路链表代码崩溃是学习过程中的常态。多数情况下问题不是语法错误而是指针使用不当。下面整理几个高频问题。问题现象常见原因解决思路程序崩溃提示段错误对空指针或野指针取 next/data操作前先判断指针是否为 NULL打印链表时死循环插入节点时丢了后继地址节点自己指向自己检查 s-next p-next 是否在 p-next s 之前执行插入第 1 个位置失败没有带头节点且没有特殊处理头指针使用带头节点的方式统一逻辑删除节点后程序崩溃free(q) 之后还通过 q 访问内存free 后不继续使用旧指针查找位置越界没有提示忘记判断 GetElem 返回值调用 GetElem 后必须判断是否为 NULL内存泄漏malloc 后忘记 free删除节点或程序结束前释放所有 malloc 的内存头插法建立的链表顺序和插入顺序相反头插法本身的特点需要保持顺序时改为尾插法下面单独说明几个高频率问题。7.1 为什么插入顺序错了会丢失节点假设当前链表是A - B - C我们要在 A 后面插入新节点 S。正确顺序S-next A-next; // S 指向 B A-next S; // A 指向 S错误顺序A-next S; // A 直接指向 SB 地址丢失 S-next A-next; // S 指向 S形成环第一种错误会让 B 和 C 再也找不到造成节点丢失第二种错误会让链表陷入死循环。写代码时先把两条语句背熟再理解背后的指针指向变化。7.2 free 之后指针还能用吗不能。free(q)的作用是释放 q 指向的那块堆内存但 q 本身的值不会自动变成 NULL。此时 q 指向的内存已经不属于程序继续访问是未定义行为。保险做法是在 free 之后手动置空free(q); q NULL;这样可以避免误用悬空指针。7.3 为什么初始化链表要用二级指针InitList(L)中传入的是LinkList*也就是LNode**目的是在函数内部修改实参L的值。如果不这么做会写成这样void InitListWrong(LinkList L) { L (LNode*)malloc(sizeof(LNode)); // 修改的是形参 L-next NULL; }表面上好像分配了内存但函数结束之后外部的 L 仍然是 NULL。这个错误非常隐蔽代码不报错但后续一访问 L-next 就崩溃。7.4 为什么按位置删除前要判断 p-next ! NULL因为GetElem(L, i-1)只能保证前驱节点 p 存在不能保证 p 后面有节点。如果 i 恰好等于链表长度 1p 指向最后一个节点p-next 是 NULL。此时执行LNode *q p-next; // q NULL p-next q-next; // 对 NULL 取 next崩溃所以判断条件必须是if (p NULL || p-next NULL) { return false; }这是链表删除中最容易遗漏的边界判断。8. 最佳实践与工程建议链表操作虽然简单但写成可靠、可读、易维护的代码需要养成一些习惯。下面这几条建议不仅适用于链表也适用于所有涉及指针和内存的 C/C 程序。8.1 总是使用头节点带头节点的实现方式比不带头节点的实现方式更利于统一代码逻辑。头插、指定位置插入、删除第一个节点时都不需要单独处理“修改头指针”的情况。笔试和面试中如果允许优先使用带头节点的链表。8.2 核心插入和删除语句固定写法插入新节点固定使用s-next p-next; p-next s;删除后继节点固定使用q p-next; p-next q-next; free(q);初次学习时不要尝试发明新的写法。先把这两组语句写熟理解指针变化之后再考虑“前插”“后插”的变形问题。8.3 每个 malloc 都要对应一个 free内存泄漏是 C 语言开发中最需要警惕的问题。链表程序中凡是 malloc 创建的节点最终都要被 free 释放。写删除函数时一定要记得释放被摘下来的节点。完整的链表销毁函数可以参考void DestroyList(LinkList L) { LNode *p L; LNode *temp NULL; while (p ! NULL) { temp p; p p-next; free(temp); } }这样写不需要担心“先保存后释放”的顺序问题每访问一个节点记录下一个节点地址然后释放当前节点循环可以安全结束。8.4 不要相信任何指针参数在函数入口处对传入的指针做合法性判断if (L NULL || p NULL) { return false; }这些判断看起来冗余但在工程项目中能挽救大量线上问题。链表操作尤其容易受到外部非法输入影响宁可多写一个判断也不要省掉防御性检查。8.5 使用调试工具辅助排查如果程序崩溃不要急着加 printf先考虑用调试器定位问题。Linux / macOS 下可以用 gdbWindows 下可以用 Visual Studio 的断点调试也可以通过 AddressSanitizer 等工具检查内存错误。比如使用 gcc 编译时加上gcc -g -fsanitizeaddress -o main main.c这样程序在发生内存访问错误时会直接输出详细报告比肉眼查代码高效很多。9. 进一步扩展单链表的其他常见考点单链表的查、插、删是基础但很多教材和面试题都会在它们之上进一步延伸。如果你已经掌握了前面这些内容可以继续挑战以下方向。9.1 链表逆序链表逆序是“插入操作”的高级应用。核心思路是从原链表中依次取出每个节点用头插法插入到新链表头部。这个思路基于“头插法会让后插入的节点排前面”的特性。参考实现void ReverseList(LinkList L) { if (L NULL || L-next NULL) { return; } LNode *p L-next; // p 指向第一个节点 LNode *q NULL; L-next NULL; // 将头节点与旧链断开 while (p ! NULL) { q p-next; // 保存下一个节点 // 头插法把 p 插入到 L 后 p-next L-next; L-next p; p q; // 继续处理原链表的下一个节点 } }这段代码综合了查找、头插、指针保存等技术是检验链表操作是否真正理解的好题目。9.2 合并两个升序单链表除了链表逆序合并两个有序链表也是热点。比如题目“已知两个长度为 m 和 n 的升序单链表将它们合并为一个升序链表”思路通常是用双指针遍历两个链表不断把较小节点接到新链表尾部。9.3 链表排序插入排序、归并排序都可以在链表上实现。链表归并排序只需要掌握“合并两个有序链表”和“寻找中间节点”两个子问题是不少大厂面试的常客。9.4 语言变体如果你学的是 Python单链表操作也有对应的写法。Python 原生列表虽然可以模拟链表但真正的链表通常通过类来实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython 的自动内存管理省去了 malloc/free 的环节但指针指向的思维和 C 语言完全一致。理解 C 语言的实现换成 Python 只需要调整语法细节即可。10. 总结单链表的查、插、删是数据结构课程中最基础的操作也是后续二叉树、图、哈希表等复杂结构操作的基础。很多人学链表时容易陷入“看得懂写不对”的困境原因往往不是智商问题而是缺少对指针变化的直观认识。建议你按照本文顺序自己动手完成以下步骤把综合示例代码敲一遍运行看结果尝试修改代码实现“在第 i 个位置插入节点”时如果 i 非法给出提示尝试实现“删除第一个值大于某个阈值的节点”尝试实现链表逆序打开调试器在插入、删除的关键语句上打断点观察每一步 p、s、q 的地址变化。链表操作没有太多高深理论关键是把 execute 的顺序、边界条件、内存释放变成肌肉记忆。真正写代码的时候你会发现大多数问题都集中在几行核心语句上。如果本文对你有帮助可以收藏备用。后续我也会继续更新更多数据结构与算法相关的内容欢迎交流你在链表学习中遇到的报错和困惑。
单链表查插删详解：查找、插入、删除操作与C语言实现
1. 为什么要单独把“查、插、删”拎出来讲如果你正在学数据结构或者正在复习考研《数据结构》里的线性表章节应该对“单链表”不陌生。很多同学刚开始接触链表时会觉得定义非常简单struct LNode { int data; struct LNode *next; };一个数据域一个指针域每个节点通过 next 指针串起来。但一旦开始写代码问题就来了为什么插入节点时语句顺序不能颠倒为什么删除节点后要 free()为什么按位置查找时循环条件要写成p ! NULL而不是p-next ! NULL问题不大但每一个都可能让程序直接崩溃或者在考试、面试时丢掉关键分数。本文围绕单链表最基本的三种操作——查找、插入、删除——展开。你可以把这篇文章当成一份“带解析的链表操作速查手册”也可以当成一个“从零到完整可运行程序的实战教程”。我会把每一步的思路、指针变化、边界情况、常见错误都拆开讲适合正在学习数据结构的新手也适合准备考研复试或面试前快速复习的同学。在继续阅读之前建议你先打开 IDE准备好一个 C 语言编译环境。因为链表操作光看文字很难形成感觉亲手写一遍、跑一遍比单纯记忆结论要有效得多。2. 环境准备与结构定义2.1 编译环境说明本文示例代码使用 C 语言编写因为国内数据结构教材大多使用 C/C 描述算法考试和面试也通常要求用 C 风格实现。你需要准备GCC 编译器或者任何一个支持 C99 标准的 IDE常用选择Dev-C、Code::Blocks、Visual Studio、VS Code C/C 插件不需要额外安装第三方库代码全部基于标准 C。版本不需要过于纠结。链表操作是非常基础且稳定的内容不同编译器之间几乎没有差异。重点在于理解指针和内存管理。2.2 定义链表结构体创建项目后我们建议把结构体定义、函数声明和主函数分开。不过为了演示方便本文先用一个头文件风格的结构说明完整代码最后给出单个 main.c 的综合程序。结构体定义如下// 文件路径LinkList.h #ifndef LINKLIST_H #define LINKLIST_H #include stdio.h #include stdlib.h #include stdbool.h // 单链表节点定义 typedef struct LNode { int data; // 数据域这里以 int 为例 struct LNode *next; // 指针域指向下一个节点 } LNode; // 给指向节点的指针起个别名方便书写 typedef LNode* LinkList; #endif这里有个常见问题LinkList到底是结构体还是指针从上面定义可以看出LinkList就是LNode*也就是一个指向头节点的指针。有些教材用LinkList L表示头指针用LNode *p表示工作指针二者本质相同不要被名字绕晕。2.3 初始化一个带头节点的链表在实现查找、插入、删除之前需要先有链表。为了统一操作逻辑本文采用“带头节点”的方式。头节点不存放有效数据它的 next 指向第一个实际节点。好处是插入和删除第一个节点时不需要单独修改头指针代码可以统一处理。初始化函数// 初始化带头节点的空链表 void InitList(LinkList *L) { // 分配头节点 *L (LNode*)malloc(sizeof(LNode)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next NULL; }这段代码为什么要用二级指针LinkList *L因为我们需要在函数内部修改L本身的值让它指向新分配的头节点。如果只传LinkList L形参和外界的实参互不相干函数结束之后L依然是原来的野指针。这一点也是链表入门最常见的困惑之一。3. 单链表的查找操作查找是线性表最基础的操作之一。单链表查找分为两种按位置查找找到第 i 个节点按值查找找到第一个值为 目标值 的节点。由于单链表只能从前往后遍历两种查找的时间复杂度都是 O(n)。3.1 按位置查找按位置查找的含义是给定位置 ii 从 1 开始返回第 i 个节点的指针。如果 i 不合法返回 NULL。先看代码// 按位置查找返回第 i 个节点的指针i 从 1 开始 LNode* GetElem(LinkList L, int i) { if (i 1) { return NULL; } int j 0; // 当前指向的是第 j 个节点 LNode *p L; // p 从头节点开始 // 从头节点开始向后移动直到 p 为空 或 j i while (p ! NULL j i) { p p-next; j; } return p; // 如果 i 超过链表长度p 为 NULL }这个代码是经典写法。我们来拆解循环的终止条件如果p NULL说明已经走到链表尾部还没找到第 i 个节点说明 i 越界如果j i说明 p 正好指向第 i 个节点。注意一个重要细节这里返回的可能是 NULL。调用方在使用返回值之前必须判断否则对 NULL 取-data会直接触发段错误。测试代码void TestGetElem(LinkList L) { LNode *p GetElem(L, 3); if (p ! NULL) { printf(第 3 个节点的值是%d\n, p-data); } else { printf(第 3 个节点不存在\n); } }3.2 按值查找按值查找的逻辑更直观从第一个实际节点开始依次比较每个节点的 data找到第一个等于目标值的节点返回它的指针找不到则返回 NULL。// 按值查找返回第一个值为 e 的节点指针找不到返回 NULL LNode* LocateElem(LinkList L, int e) { LNode *p L-next; // 跳过带头节点 while (p ! NULL p-data ! e) { p p-next; } return p; }这段代码要注意一点为什么把p L-next而不是p L因为头节点不参与数据比较。如果从头节点开始的话万一头节点的 data 恰好等于目标值就会返回错误结果。3.3 查找操作的时间复杂度与边界情况时间复杂度查找第 i 个节点需要移动 i 次查找指定值最多需要遍历整个链表平均时间复杂度都是 O(n)。这个结论需要记住因为很多面试题会在此基础上延伸比如“查找链表倒数第 k 个节点”“找到链表中间节点”等。边界情况总结场景结果i 1返回 NULLi 0返回头节点有些算法题会用到i 超过链表长度循环终止返回 NULL链表为空按值查找返回 NULL查找值不存在返回 NULL不要觉得返回 NULL 是代码的“缺陷”恰恰相反返回 NULL 是给调用方的明确信号。凡是调用查找函数都要养成判断空指针的习惯。4. 单链表的插入操作插入是单链表操作中最容易出错的环节。很多初学者在写插入代码时经常出现“链表断成两截”的现象原因就是没有理解指针赋值的执行顺序。4.1 插入操作的本质单链表的插入本质上是修改节点的 next 指针让新节点“插入”到两个已有节点之间。假设要在节点 p 的后面插入一个新节点 s需要两步s-next p-next; // 第一步新节点先指向 p 原来的后继节点 p-next s; // 第二步p 的 next 改为指向新节点这两步的顺序不能颠倒。如果把第二步写在前面p-next s; // 错误这会丢失 p 原来的后继节点地址 s-next p-next; // 此时 p-next 已经是 ss-next 指向自己链表从中间断开后续节点全部丢失而且 s-next 指向自己一遍历就死循环。这是初学链表时最常见的错误之一。4.2 头插法插入节点头插法把新节点插入到头节点之后也就是链表的起始位置。头插法不需要遍历链表时间复杂度 O(1)。// 头插法在链表头部插入节点e 是新节点数据 void HeadInsert(LinkList L, int e) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data e; // 核心插入步骤 s-next L-next; L-next s; }这种插入方式有一个特点后插入的节点反而排在前面。所以如果连续调用HeadInsert(L, 1)、HeadInsert(L, 2)、HeadInsert(L, 3)最终链表顺序是 3 2 1。很多算法题用头插法实现链表逆序思路就是从原链表中逐个取出节点再用头插法插到新链表中。4.3 尾插法插入节点如果需要保持插入顺序可以用尾插法。尾插法需要先找到最后一个节点再把新节点挂在末尾。// 尾插法在链表末尾插入节点 void TailInsert(LinkList L, int e) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data e; s-next NULL; // 找到最后一个节点 LNode *p L; while (p-next ! NULL) { p p-next; } p-next s; }尾插法每次都需要从头遍历到尾时间复杂度 O(n)。如果在一个循环中插入 n 个元素总时间复杂度是 O(n²)。如果需要频繁尾插更好的做法是额外维护一个尾指针tail每次插入后更新 tail这样单次插入就是 O(1)。4.4 在指定位置插入节点按位置插入可以理解为“先找位置再做插入”。思路如下找到第 i-1 个节点也就是待插入位置的前驱节点判断前驱节点是否存在执行核心插入步骤。// 在链表的第 i 个位置插入节点数据为 e bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } // 查找第 i-1 个节点 LNode *p GetElem(L, i - 1); if (p NULL) { printf(插入位置不合法\n); return false; } // 创建新节点 LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; // 核心插入步骤 s-next p-next; p-next s; return true; }这里用到了前面实现的GetElem函数。注意GetElem(L, i-1)返回的是前驱节点。如果前驱节点为空说明 i 超出了链表长度范围。举个例子链表当前是1 - 3 - 4执行ListInsert(L, 2, 2)GetElem(L, 1)找到值为 1 的节点新建节点 sdata 2s-next p-next此时 s-next 指向值为 3 的节点p-next s值为 1 的节点指向新节点。最终链表变为1 - 2 - 3 - 4。4.5 插入操作的时间复杂度头插法O(1)尾插法O(n)维护尾指针后可以做到 O(1)指定位置插入定位需要 O(n)插入本身 O(1)总复杂度 O(n)。对于“在指定节点后插入”这种已知节点指针的情况插入操作本身是 O(1)。很多考试题就问这一点给定节点 p如何在 O(1) 时间内在 p 后面插入节点答案就是上面那两句赋值语句不包含查找过程。5. 单链表的删除操作删除操作的核心是先找到待删除节点的前驱节点然后让前驱节点跳过待删除节点直接指向待删除节点的下一个节点最后释放待删除节点的内存。5.1 删除指定位置节点删除第 i 个节点// 删除链表的第 i 个节点并用 e 返回被删除节点的数据 bool ListDelete(LinkList L, int i, int *e) { if (i 1) { return false; } // 找到第 i-1 个节点即待删除节点的前驱 LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) { printf(删除位置不合法\n); return false; } LNode *q p-next; // q 指向待删除节点 *e q-data; // 保存被删除节点的值 p-next q-next; // 前驱节点跳过 q指向 q 的后继 free(q); // 释放 q 的内存 return true; }注意这里有两个判断p NULL前驱节点不存在位置太靠后p-next NULL前驱节点是最后一个节点后面没有可删除的节点。把这两步合并写成if (p NULL || p-next NULL)是标准写法。漏掉任何一个判断都可能产生空指针访问。free(q)这一步非常关键。C 语言中malloc 分配的内存必须由 free 释放。如果不释放每删除一个节点就泄漏一块内存程序长时间运行后内存占用会越来越大。而释放之后不能让 p 继续指向 q因为 q 已经成为一个悬空指针dangling pointer。5.2 按值删除节点按值删除的实现思路从第一个实际节点开始遍历找到第一个数据等于目标值的节点删除这个节点。但问题是我们要找到的是待删除节点本身还是它的前驱答案是前驱。因为删除操作需要修改前驱节点的 next 指针。// 删除第一个值为 e 的节点 bool DeleteByValue(LinkList L, int e) { LNode *p L; // p 指向头节点 LNode *q NULL; // q 用来临时保存待删除节点 // 从头开始遍历p 始终是当前节点的前驱 while (p-next ! NULL) { if (p-next-data e) { q p-next; p-next q-next; free(q); return true; } p p-next; } return false; // 没找到值为 e 的节点 }这里使用p-next-data进行比较这样 p 始终是待删除节点的前驱。一旦找到目标节点直接让 p-next 跳过它。这个技巧在链表类算法题中非常常用。5.3 删除操作的时间复杂度删除指定位置节点查找前驱 O(n)删除 O(1)总复杂度 O(n)。如果已经给出了待删除节点的前驱指针删除本身只要两句话q p-next; p-next q-next; free(q);这是 O(1) 操作。如果题目要求 O(1) 时间删除某个给定指针指向的节点不提供前驱可以用“值覆盖法”// 只给定节点指针 delO(1) 删除该节点 // 思路用后继节点的值覆盖当前节点再删除后继节点 bool DeleteNodeO1(LNode *del) { if (del NULL || del-next NULL) { return false; // 无法处理尾节点 } LNode *nextNode del-next; del-data nextNode-data; del-next nextNode-next; free(nextNode); return true; }这种做法的本质是“偷天换日”把后继节点的数据复制到当前节点然后删除后继节点。它要求待删除节点不能是尾节点因为尾节点没有后继可以用来顶替。6. 完整可运行的综合示例前面把每个操作拆开讲解下面给出一个完整的可运行程序。这个程序把链表初始化、头插、尾插、按位插入、按位删除、查找、打印等功能整合在一起你可以直接复制到本地运行。// 文件路径main.c #include stdio.h #include stdlib.h #include stdbool.h // 单链表节点定义 typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 初始化带头节点的空链表 void InitList(LinkList *L) { *L (LNode*)malloc(sizeof(LNode)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next NULL; } // 尾插法建立链表依次插入数组 a 中的 n 个元素 void CreateListByTail(LinkList L, int a[], int n) { LNode *tail L; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { printf(内存分配失败\n); return; } s-data a[i]; s-next NULL; tail-next s; tail s; } } // 按位置查找返回第 i 个节点指针i 从 1 开始 LNode* GetElem(LinkList L, int i) { if (i 1) { return NULL; } int j 0; LNode *p L; while (p ! NULL j i) { p p-next; j; } return p; } // 按值查找返回第一个值为 e 的节点指针 LNode* LocateElem(LinkList L, int e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; } // 在指定位置插入 bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p GetElem(L, i - 1); if (p NULL) { return false; } LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next p-next; p-next s; return true; } // 删除指定位置节点 bool ListDelete(LinkList L, int i, int *e) { if (i 1) { return false; } LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) { return false; } LNode *q p-next; *e q-data; p-next q-next; free(q); return true; } // 打印链表所有节点 void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } int main() { LinkList L; InitList(L); // 通过尾插法创建链表1 2 3 4 5 int a[] {1, 2, 3, 4, 5}; CreateListByTail(L, a, 5); printf(初始链表); PrintList(L); // 测试插入在第 2 个位置插入 99 if (ListInsert(L, 2, 99)) { printf(在第 2 个位置插入 99 后); PrintList(L); } // 测试查找查找第 3 个节点 LNode *p GetElem(L, 3); if (p ! NULL) { printf(第 3 个节点的值是%d\n, p-data); } else { printf(第 3 个节点不存在\n); } // 测试按值查找查找 99 p LocateElem(L, 99); if (p ! NULL) { printf(找到值为 99 的节点它的下一个节点是); if (p-next ! NULL) { printf(%d\n, p-next-data); } else { printf(NULL\n); } } else { printf(未找到值为 99 的节点\n); } // 测试删除删除第 2 个节点 int delVal 0; if (ListDelete(L, 2, delVal)) { printf(删除第 2 个节点值为 %d删除后, delVal); PrintList(L); } return 0; }预期输出初始链表1 2 3 4 5 在第 2 个位置插入 99 后1 99 2 3 4 5 第 3 个节点的值是2 找到值为 99 的节点它的下一个节点是2 删除第 2 个节点值为 99删除后1 2 3 4 5运行结果符合预期插入 99 后链表变成1 99 2 3 4 5查找第 3 个节点时由于 99 插入到了第 2 个位置原来的 2 变成了第 3 个节点按值查找 99 后可以访问其后继节点删除第 2 个节点后链表恢复成初始顺序。这里有一个细节值得注意插入和删除操作会改变节点位置。所以“第 2 个节点”在不同操作之间指的对象可能是不同的。写算法时一定要区分“按值定位”和“按位置定位”之间的区别。7. 常见问题与排查思路链表代码崩溃是学习过程中的常态。多数情况下问题不是语法错误而是指针使用不当。下面整理几个高频问题。问题现象常见原因解决思路程序崩溃提示段错误对空指针或野指针取 next/data操作前先判断指针是否为 NULL打印链表时死循环插入节点时丢了后继地址节点自己指向自己检查 s-next p-next 是否在 p-next s 之前执行插入第 1 个位置失败没有带头节点且没有特殊处理头指针使用带头节点的方式统一逻辑删除节点后程序崩溃free(q) 之后还通过 q 访问内存free 后不继续使用旧指针查找位置越界没有提示忘记判断 GetElem 返回值调用 GetElem 后必须判断是否为 NULL内存泄漏malloc 后忘记 free删除节点或程序结束前释放所有 malloc 的内存头插法建立的链表顺序和插入顺序相反头插法本身的特点需要保持顺序时改为尾插法下面单独说明几个高频率问题。7.1 为什么插入顺序错了会丢失节点假设当前链表是A - B - C我们要在 A 后面插入新节点 S。正确顺序S-next A-next; // S 指向 B A-next S; // A 指向 S错误顺序A-next S; // A 直接指向 SB 地址丢失 S-next A-next; // S 指向 S形成环第一种错误会让 B 和 C 再也找不到造成节点丢失第二种错误会让链表陷入死循环。写代码时先把两条语句背熟再理解背后的指针指向变化。7.2 free 之后指针还能用吗不能。free(q)的作用是释放 q 指向的那块堆内存但 q 本身的值不会自动变成 NULL。此时 q 指向的内存已经不属于程序继续访问是未定义行为。保险做法是在 free 之后手动置空free(q); q NULL;这样可以避免误用悬空指针。7.3 为什么初始化链表要用二级指针InitList(L)中传入的是LinkList*也就是LNode**目的是在函数内部修改实参L的值。如果不这么做会写成这样void InitListWrong(LinkList L) { L (LNode*)malloc(sizeof(LNode)); // 修改的是形参 L-next NULL; }表面上好像分配了内存但函数结束之后外部的 L 仍然是 NULL。这个错误非常隐蔽代码不报错但后续一访问 L-next 就崩溃。7.4 为什么按位置删除前要判断 p-next ! NULL因为GetElem(L, i-1)只能保证前驱节点 p 存在不能保证 p 后面有节点。如果 i 恰好等于链表长度 1p 指向最后一个节点p-next 是 NULL。此时执行LNode *q p-next; // q NULL p-next q-next; // 对 NULL 取 next崩溃所以判断条件必须是if (p NULL || p-next NULL) { return false; }这是链表删除中最容易遗漏的边界判断。8. 最佳实践与工程建议链表操作虽然简单但写成可靠、可读、易维护的代码需要养成一些习惯。下面这几条建议不仅适用于链表也适用于所有涉及指针和内存的 C/C 程序。8.1 总是使用头节点带头节点的实现方式比不带头节点的实现方式更利于统一代码逻辑。头插、指定位置插入、删除第一个节点时都不需要单独处理“修改头指针”的情况。笔试和面试中如果允许优先使用带头节点的链表。8.2 核心插入和删除语句固定写法插入新节点固定使用s-next p-next; p-next s;删除后继节点固定使用q p-next; p-next q-next; free(q);初次学习时不要尝试发明新的写法。先把这两组语句写熟理解指针变化之后再考虑“前插”“后插”的变形问题。8.3 每个 malloc 都要对应一个 free内存泄漏是 C 语言开发中最需要警惕的问题。链表程序中凡是 malloc 创建的节点最终都要被 free 释放。写删除函数时一定要记得释放被摘下来的节点。完整的链表销毁函数可以参考void DestroyList(LinkList L) { LNode *p L; LNode *temp NULL; while (p ! NULL) { temp p; p p-next; free(temp); } }这样写不需要担心“先保存后释放”的顺序问题每访问一个节点记录下一个节点地址然后释放当前节点循环可以安全结束。8.4 不要相信任何指针参数在函数入口处对传入的指针做合法性判断if (L NULL || p NULL) { return false; }这些判断看起来冗余但在工程项目中能挽救大量线上问题。链表操作尤其容易受到外部非法输入影响宁可多写一个判断也不要省掉防御性检查。8.5 使用调试工具辅助排查如果程序崩溃不要急着加 printf先考虑用调试器定位问题。Linux / macOS 下可以用 gdbWindows 下可以用 Visual Studio 的断点调试也可以通过 AddressSanitizer 等工具检查内存错误。比如使用 gcc 编译时加上gcc -g -fsanitizeaddress -o main main.c这样程序在发生内存访问错误时会直接输出详细报告比肉眼查代码高效很多。9. 进一步扩展单链表的其他常见考点单链表的查、插、删是基础但很多教材和面试题都会在它们之上进一步延伸。如果你已经掌握了前面这些内容可以继续挑战以下方向。9.1 链表逆序链表逆序是“插入操作”的高级应用。核心思路是从原链表中依次取出每个节点用头插法插入到新链表头部。这个思路基于“头插法会让后插入的节点排前面”的特性。参考实现void ReverseList(LinkList L) { if (L NULL || L-next NULL) { return; } LNode *p L-next; // p 指向第一个节点 LNode *q NULL; L-next NULL; // 将头节点与旧链断开 while (p ! NULL) { q p-next; // 保存下一个节点 // 头插法把 p 插入到 L 后 p-next L-next; L-next p; p q; // 继续处理原链表的下一个节点 } }这段代码综合了查找、头插、指针保存等技术是检验链表操作是否真正理解的好题目。9.2 合并两个升序单链表除了链表逆序合并两个有序链表也是热点。比如题目“已知两个长度为 m 和 n 的升序单链表将它们合并为一个升序链表”思路通常是用双指针遍历两个链表不断把较小节点接到新链表尾部。9.3 链表排序插入排序、归并排序都可以在链表上实现。链表归并排序只需要掌握“合并两个有序链表”和“寻找中间节点”两个子问题是不少大厂面试的常客。9.4 语言变体如果你学的是 Python单链表操作也有对应的写法。Python 原生列表虽然可以模拟链表但真正的链表通常通过类来实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython 的自动内存管理省去了 malloc/free 的环节但指针指向的思维和 C 语言完全一致。理解 C 语言的实现换成 Python 只需要调整语法细节即可。10. 总结单链表的查、插、删是数据结构课程中最基础的操作也是后续二叉树、图、哈希表等复杂结构操作的基础。很多人学链表时容易陷入“看得懂写不对”的困境原因往往不是智商问题而是缺少对指针变化的直观认识。建议你按照本文顺序自己动手完成以下步骤把综合示例代码敲一遍运行看结果尝试修改代码实现“在第 i 个位置插入节点”时如果 i 非法给出提示尝试实现“删除第一个值大于某个阈值的节点”尝试实现链表逆序打开调试器在插入、删除的关键语句上打断点观察每一步 p、s、q 的地址变化。链表操作没有太多高深理论关键是把 execute 的顺序、边界条件、内存释放变成肌肉记忆。真正写代码的时候你会发现大多数问题都集中在几行核心语句上。如果本文对你有帮助可以收藏备用。后续我也会继续更新更多数据结构与算法相关的内容欢迎交流你在链表学习中遇到的报错和困惑。