这次我们来看一个大家既熟悉又容易写错的基础模块单链表的查找、插入和删除。它不是什么新框架、新模型但它是一切链表类算法题的地基也是期末考试、考研408和初级算法面试里的常客。网上讲这部分的资料很多但不少教程只给代码不解释边界条件导致很多人抄完能跑却不明白为什么头节点要单独处理、为什么删除节点时有几种不同写法。先说结论带头节点单链表的三个基本操作核心就两句话——查找靠遍历插入靠改指针删除靠跳过节点。如果你能把两个位置处理清楚一个是“头节点之后的第一个节点位置”另一个是“链表尾部的最后位置”那么查、插、删基本不会翻车。这篇文章会把环境准备、代码骨架、查找、插入、删除、完整测试、复杂度分析和常见错误全部过一遍所有代码基于C语言风格实现可以直接编译运行。准备期末复习、考研复习或者面试前想把链表基础打牢的同学这篇文章可以收藏备用。1. 单链表查插删核心能力速览操作时间复杂度带头节点是否修改链表关键注意点初始化链表O(1)是创建头节点并置 next 为 NULL头插法插入O(1)是新节点插入到头节点之后顺序会反转尾插法插入O(n)是先遍历到链表尾部不维护尾指针时为 O(n)指定位置插入O(n)是先找第 i-1 个节点再执行后插在已知节点后插入O(1)是直接改两个指针即可在已知节点前插入O(1)是用“后插 交换数据”的经典技巧按位查找O(n)否从第一个数据节点开始遍历按值查找O(n)否依次比较 data 字段按位删除O(n)是先找第 i-1 个节点再删除后继删除已知节点O(1)是用后继节点数据覆盖再删除后继尾节点除外从表格能看出来单链表最核心的“性价比”在于只要已经拿到了目标节点的位置插入和删除都可以做到 O(1)但如果没有位置、只有序号或值就必须从头遍历时间复杂度升到 O(n)。这个特点直接决定了链表适合什么场景、不适合什么场景。2. 适用场景与学习价值单链表的查、插、删适合谁学第一类是正在上数据结构课的大一、大二学生期末考试基本必考手写链表第二类是准备考研408的同学链表是《数据结构》线性表章节的核心内容第三类是准备算法面试的开发者链表题目本身不难但非常考验指针操作的基本功和边界意识。它能解决什么问题从应用层面看单链表可以用于实现栈、队列、邻接表的底层存储。在很多需要频繁插入删除、不要求随机访问的场景下链表比数组更灵活。从学习层面看掌握单链表之后你再去看循环链表、双向链表、循环双链表会发现套路高度一致改指针、判空、处理头尾边界。这个模块不适合用来做什么它不适合需要快速随机访问的场景。如果你想按下标直接取第 100 个元素单链表做不到顺序表数组才是正解。另外如果链表节点数量非常小比如只有几个元素链表和数组的性能差异可以忽略但代码复杂度明显更高这时候用数组更省事。最后提醒一句学习链表时的代码都建议在本地测试环境里跑通不要只停留在“看懂了”的层面。3. 环境准备与基础代码骨架3.1 编译器与开发环境单链表的代码本身不依赖复杂环境。常见选择有三种Windows 下使用 Visual Studio新建 C 控制台项目。Windows 下使用 VS Code MinGW 的 gcc/g。Linux 或 macOS 下直接使用 gcc/g 编译。这里有一个很容易踩的坑下面很多函数会使用 C 的“引用传参”写法比如LinkList L。如果拿纯 C 编译器编译会直接报错因为 C 语言不支持引用。数据结构教材里为了简化代码经常在 C 环境下写这种风格。如果你想用纯 C 编译需要把LinkList L改成LinkList *L调用时传L。更省事的做法是直接用 g 编译代码主体仍然是“C 风格 引用传参”这也是许多数据结构教材的实际处理方式。3.2 结构体定义与初始化单链表节点的结构体定义如下每个节点保存一个数据域和一个指针域指针指向下一个节点#include stdio.h #include stdlib.h typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这里LNode表示节点类型LinkList表示链表类型。初始化链表时我们创建一个头节点。头节点的 data 可以不用next 先置为 NULLbool InitList(LinkList L) { L (LNode *)malloc(sizeof(LNode)); if (L NULL) { return false; // 内存分配失败 } L-next NULL; return true; }注意malloc返回的是内存地址如果分配失败会返回NULL所以一定要做判空处理。很多初学者写链表不判空在内存紧张或者链表规模很大时程序可能直接崩溃。3.3 打印链表辅助函数后期调试链表时我们经常需要把链表内容打印出来。打印函数从L-next开始遍历遇到NULL停止void PrintList(LinkList L) { LNode *p L-next; printf(head); while (p ! NULL) { printf( - %d, p-data); p p-next; } printf( - NULL\n); }如果打印结果正确显示为head - 10 - 20 - NULL说明当前链表的链接关系是正常的。如果出现死循环大概率是某个节点的 next 指回了前面的节点后面排查章节会展开讲。4. 单链表查找按位查找与按值查找4.1 按位查找按位查找就是按序号查找找到链表中第 i 个数据节点。这里必须注意头节点是第 0 个节点不参与计数。第一个数据节点的序号是 1。实现思路是从L-next开始用计数器 j 从 1 开始累加只要j i就一直往后移动指针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; }这个函数返回的是节点指针。查找成功时返回指向第 i 个节点的指针查找失败时返回 NULL。失败有两种情况一是i 1序号非法二是i超过链表长度循环走到尾节点之后p变成NULL。4.2 按值查找按值查找的顺序是从头节点后的第一个数据节点开始逐个比较 data 是否等于目标值 e。找到第一个相等的节点就返回该节点的指针如果整个链表遍历完都没有找到返回 NULLLNode *LocateElem(LinkList L, int e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; }这段代码的循环条件要理解透彻p ! NULL保证不访问空指针p-data ! e保证还没找到目标值。两者同时满足才继续往后走。只要有一个不满足循环结束。循环结束后如果p ! NULL说明找到了如果p NULL说明遍历完也不存在值等于 e 的节点。4.3 查找操作验证方式查找是后续插入和删除的基础。你可以写一个简单的验证函数比如创建一个包含 10、20、30 的链表调用GetElem(L, 1)预期得到第 1 个节点data 为 10。调用GetElem(L, 5)预期返回 NULL因为链表只有 3 个节点。调用LocateElem(L, 20)预期返回 data 为 20 的节点指针。调用LocateElem(L, 99)预期返回 NULL。查找操作本身不修改链表但它要频繁用到指针移动和判空是链表基本功里最容易出错的一环。写的时候建议在心里画一条指针移动轨迹p 先指向第一个数据节点每移动一次就指向下一个节点直到 NULL 为止。5. 单链表插入头插、尾插与指定位置插入5.1 头插法头插法是把新节点插入到头节点之后也就是每次插入的新节点都成为第一个数据节点。实现步骤是先申请一个新节点 s把数据写入 s-data再把 s 的 next 指向原来头节点后的第一个节点最后让头节点的 next 指向 sbool ListHeadInsert(LinkList L, int e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next L-next; L-next s; return true; }头插法最重要的作用是“逆序建表”。例如按顺序头插 1、2、3最终链表打印出来是head - 3 - 2 - 1 - NULL。这个规律在算法题里经常用到比如反转链表时就可以用头插法重建一条新链表。头插法的时间复杂度是 O(1)因为它永远操作头节点之后的位置。5.2 尾插法尾插法是把新节点追加到链表末尾保持输入顺序。实现时需要先遍历到尾节点然后把尾节点的 next 指向新节点。如果不维护尾指针时间复杂度是 O(n)bool ListTailInsert(LinkList L, int e) { LNode *p L; while (p-next ! NULL) { p p-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next NULL; p-next s; return true; }注意两个细节第一p 从 L 开始而不是从 L-next 开始目的是保持“p 停留在最后一个节点”的语义第二新节点 s-next 必须置为 NULL否则尾节点的 next 没有初始化打印链表时可能变成野指针严重时会崩溃。尾插法建表的结果是顺序保持的依次尾插 1、2、3打印出来是head - 1 - 2 - 3 - NULL。5.3 在指定位置插入指定位置插入比如把元素 e 插入到第 i 个位置。核心思路是先找到第 i-1 个节点然后在这个节点之后执行“后插”操作。如果第 i-1 个节点不存在说明插入位置不合法bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } 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; }这里的边界条件很值得展开。当i 1时我们要把新节点插入到头节点之后。此时循环条件j 0不成立p 停在 L 上等价于头插。当i len 1时p 会遍历到尾节点这时候插入在链表末尾等价于尾插。当i len 1时循环最后 p 变成 NULL直接返回 false。5.4 在已知节点之后插入如果你已经拿到了某个节点的指针 p想在 p 之后插入一个新节点不需要从头遍历。这个操作是 O(1) 的也是单链表的招牌能力。代码可以单独抽成一个辅助函数bool InsertNextNode(LNode *p, int e) { 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; }上一个ListInsert里的后插代码本质就是InsertNextNode(p, e)。抽出来之后代码复用性更好。5.5 在已知节点之前插入如果要求在已知节点 p 之前插入新节点正常情况下需要从头遍历找到 p 的前驱节点复杂度是 O(n)。但有一个非常经典的技巧可以做到 O(1)先把新节点插到 p 的后面然后把 p 的 data 和新节点的 data 交换。逻辑上等于新节点出现在了 p 之前实际物理位置在 p 之后bool InsertPriorNode(LNode *p, int e) { if (p NULL) { return false; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-next p-next; p-next s; s-data p-data; p-data e; return true; }到这里单链表的插入就有四种写法头插、尾插、指定位置插入、已知节点前后插入。建议不要死记代码而是记住一条主线只要是“在某个节点之后插”核心就是s-next p-next; p-next s;这两步其它插入方法都是在为这两步准备一个合适的 p。6. 单链表删除按位删除与删除指定节点6.1 按位删除按位删除是删除第 i 个数据节点。实现上需要找到第 i-1 个节点 p然后让 p 的 next 跨过待删除节点 q直接指向 q 的后继节点最后用free(q)释放 q 的内存bool ListDelete(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) { return false; } LNode *q p-next; e q-data; p-next q-next; free(q); return true; }这里用引用变量 e 把被删除节点的数据带出来方便调用方知道删掉的值。两个失败判断值得注意p NULL说明第 i-1 个节点不存在位置超出链表长度p-next NULL说明第 i-1 个节点是尾节点根本没有第 i 个节点可以删。这两种情况都要返回 false。删除头节点之后的第一个节点时p 就是 Lq 是 L-next执行L-next q-next后原来的第一个节点就从链表中断开了。6.2 删除指定节点如果已经拿到目标节点的指针 p想删除它能不能做到 O(1)可以但有一个关键限制p 不能是尾节点。思路是“偷梁换柱”先把 p 的后继节点 q 的数据拷贝到 p 上再删除 q。这样数据上是 p 被删除了实际释放的是 q 的内存bool DeleteNode(LNode *p) { if (p NULL || p-next NULL) { return false; } LNode *q p-next; p-data q-data; p-next q-next; free(q); return true; }这个函数为什么不能删除尾节点因为尾节点的p-next NULL它没有后继节点也就没有“偷”的对象。如果确实要删除尾节点必须从头遍历找到它的前驱节点再做常规删除。这是一个非常经典的边界题面试官很喜欢问“已知单链表节点的指针如何 O(1) 删除该节点”你如果能答出“非尾节点用后继覆盖尾节点需遍历前驱”就是合格的答案。6.3 清空整张链表删除操作还有一个常见场景销毁整张链表释放所有节点的内存。错误做法是只把L-next置为 NULL这样会造成大量内存泄漏。正确做法是从头节点开始逐节点 freevoid DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *q p-next; free(p); p q; } L NULL; }注意必须先用变量 q 保存 p 的后继节点再 free(p)。如果先 free 再取 p-next就会访问已经释放的内存属于未定义行为。7. 完整测试与效果验证这个主题不涉及网络接口 API也没有批量任务队列但我们可以用一组完整的本地测试用例来模拟“批量验证”的效果初始化链表依次做尾插、头插、指定位置插入、按位查找、按值查找、按位删除、删除指定节点、销毁链表每一步都打印链表结构验证结果是否符合预期。下面给出一份完整的可运行测试程序#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; bool InitList(LinkList L) { L (LNode *)malloc(sizeof(LNode)); if (L NULL) { return false; } L-next NULL; return true; } 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 e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; } bool ListHeadInsert(LinkList L, int e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next L-next; L-next s; return true; } bool ListTailInsert(LinkList L, int e) { LNode *p L; while (p-next ! NULL) { p p-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next NULL; p-next s; return true; } bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } 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 L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) { return false; } LNode *q p-next; e q-data; p-next q-next; free(q); return true; } bool DeleteNode(LNode *p) { if (p NULL || p-next NULL) { return false; } LNode *q p-next; p-data q-data; p-next q-next; free(q); return true; } void PrintList(LinkList L) { LNode *p L-next; printf(head); while (p ! NULL) { printf( - %d, p-data); p p-next; } printf( - NULL\n); } int main() { LinkList L; InitList(L); ListTailInsert(L, 10); ListTailInsert(L, 20); ListTailInsert(L, 30); printf(尾插 10,20,30 后: ); PrintList(L); ListHeadInsert(L, 5); printf(头插 5 后: ); PrintList(L); ListInsert(L, 2, 15); printf(在位置 2 插入 15 后: ); PrintList(L); LNode *node GetElem(L, 3); printf(按位查找第 3 个节点: %d\n, node ? node-data : -1); LNode *find LocateElem(L, 20); printf(按值查找 20: %s\n, find ? 找到了 : 未找到); int e -1; if (ListDelete(L, 1, e)) { printf(删除第 1 个节点删除的值是 %d删除后: , e); PrintList(L); } LNode *p GetElem(L, 2); if (p ! NULL) { DeleteNode(p); printf(删除第 2 个节点后: ); PrintList(L); } DestroyList(L); printf(链表已销毁\n); return 0; }预期输出如下尾插 10,20,30 后: head - 10 - 20 - 30 - NULL 头插 5 后: head - 5 - 10 - 20 - 30 - NULL 在位置 2 插入 15 后: head - 5 - 15 - 10 - 20 - 30 - NULL 按位查找第 3 个节点: 10 按值查找 20: 找到了 删除第 1 个节点删除的值是 5删除后: head - 15 - 10 - 20 - 30 - NULL 删除第 2 个节点后: head - 15 - 20 - 30 - NULL 链表已销毁这份测试覆盖了单链表最核心的路径尾插、头插、指定位置插入、按位查找、按值查找、按位删除、指定节点删除、链销毁。建议你把它跑通后再手动改几个边界场景继续测试在空链表上删除第 1 个节点预期返回 false。在链表长度为 3 时删除第 4 个节点预期返回 false。删除越界节点时 e 不会被写入调用方应保持默认值。在所有测试之后手动检查内存分配和释放是否配对。判断测试是否成功的标准很简单链表打印结果符合预期删除带出的值正确越界操作没有让程序崩溃。如果程序中途段错误优先检查是不是有节点没有初始化 next或者访问了已经 free 的节点。8. 时间复杂度与空间复杂度分析单链表查、插、删的复杂度规律可以总结成一张表操作平均时间复杂度说明按位查找O(n)必须从头开始遍历按值查找O(n)最坏情况遍历完整条链表头插O(1)只操作头节点之后指定位置插入O(n)主要耗时在查找第 i-1 个节点已知节点后插入O(1)只改两个指针已知节点前插入O(1)用后插加交换数据实现按位删除O(n)主要耗时在查找第 i-1 个节点删除已知节点O(1)非尾节点时用后继覆盖实现空间复杂度方面单链表本身需要 O(n) 的空间存储 n 个节点数据。额外操作时每次插入会申请一个节点空间每次删除用 free 释放一个节点空间因此插入和删除的额外辅助空间是 O(1)。需要特别理解的是链表和数组的复杂度差异。数组按下标访问是 O(1)但插入删除要移动大量元素。链表反过来按位访问是 O(n)但一旦拿到目标节点插入删除可以做到 O(1)。所以面试里常见的“数组和链表有什么区别”核心答案就是数组擅长随机访问、内存连续、缓存友好链表擅长频繁插入删除、不要求连续内存、动态扩容更方便。没有绝对优势只有场景匹配。9. 常见错误与排查方法实践过程中最常见的报错和异常现象可以对照下面的表排查问题现象可能原因排查方式解决方案编译报错 expected ‘LNode **’ but argument is of type ‘LNode *’纯 C 编译器不支持引用传参检查编译器和函数参数使用 g 编译或把参数改成LNode **L调用时传L程序段错误 Segfault访问了空指针或已释放节点用调试器定位崩溃行访问前判空释放后不要再使用打印链表死循环尾节点 next 没有置 NULL或插入时形成环打印每个节点地址检查是否重复新节点 next 必须初始化检查尾节点指向插入位置总是差 1ListInsert 中 p 的初始位置或者 j 的起算没写对画指针移动轨迹打印中间节点从 pL、j0 开始先移动 i-1 次删除后无法找到链表头部误删了头节点或头指针被修改打印 L 的值不要 free(L)删除数据节点时 p 保留在 L内存持续增长删除节点时没有 free使用内存检测工具free(q)销毁链表时逐节点释放DeleteNode 删除尾节点失败尾节点没有后继可覆盖断点打印 p-next尾节点必须找到前驱再删除链表打印多出随机值新节点 next 没有初始化检查 malloc 后是否赋值s-next NULL;这里最值得深入的是一个常见错误插入和删除时“指针更新顺序写反”。插入时正确顺序是先把新节点的 next 指向 p 的 next再把 p 的 next 指向新节点。如果先执行p-next s就会让 p 原来的后继节点丢失新节点就无法接上原来的链。这两行代码的顺序在面试手写链表时经常被考一定要形成肌肉记忆s-next p-next; p-next s;另一个常见错误是删除操作时没有先把 q 的后继存下来就开始 free。正确写法是先用p-next q-next断开再free(q)。如果先 free(q) 再访问 q-next就是典型的“悬垂指针”问题。10. 最佳实践与学习建议单链表的查、插、删虽然简单但要写得稳还是需要一些方法。第一画图比写代码重要。你在纸上画出头节点、数据节点和箭头然后手动模拟一次插入或删除操作观察指针指向的变化。画完再写代码正确率会高很多。很多指针写错的根源是脑子里没有清晰的箭头模型。第二维护一套最小可运行模板。把初始化、打印、查找、后插、删除这几个核心函数整合到一个文件里当作以后写链表题的“工具箱”。面试或考试时很多链表算法题都可以调用这些基础操作来简化思路。第三测试不能只看正常路径。要专门测边界在第 1 个位置插入、在末尾插入、在越界位置插入、在空链表上删除、删除最后一个节点。边界能过说明你对链表的位置语义理解是准确的。第四内存管理要养成习惯。malloc和free要配对删除节点后及时 free。写正规项目时链表的销毁、异常分支的内存释放都要处理好。这个问题在 C/C 面试里是高频追问点。第五学完单链表后建议用同样的思路扩展循环链表、双向链表、双向循环链表栈和队列的链式存储这些都离不开今天的指针操作。算法刷题方面可以拿 LeetCode 的链表反转、合并两个有序链表、删除倒数第 N 个节点、判断链表是否有环等题目练手但要从自己实现的链表节点和函数开始写而不是只调用现成库。第六数据结构的代码有一定重复性适合用“教材模板 自己改写”的方式学习。但不要把别人的代码直接背下来而是理解每一步的语义。比如看到p-next q-next你要能说出它的含义是“让 p 跳过 q指向 q 的后继节点”。11. 总结单链表的查找、插入和删除核心内容可以用三条主线概括查找靠遍历插入靠改指针删除靠跳过节点。真正的难点不在算法思想而在边界处理头节点位置、越界位置、空链表、尾节点、内存释放这些细节才是区分“看懂了”和“写得对”的分水岭。这篇文章给出的所有代码都围绕带头节点的单链表实现完整测试程序可以直接编译运行。建议你拿到代码后先跑一遍观察每一步打印结果再手动构造几个边界用例测试失败路径。如果能把插入的两个关键行写对、能说清楚为什么 DeleteNode 无法删除尾节点、能画出头插和尾插建表的顺序差异说明这块基础已经过关了。单链表学会之后下一步可以试着用同样的思路写循环链表和双向链表也可以直接去刷几道链表章节的算法题。平时写代码时记得保留一份最小可运行模板考试或面试前快速过一遍比临时翻书高效得多。这篇内容建议收藏备用等真正动手写链表时再翻出来对照。
带头节点单链表查插删实现：核心原理与边界条件详解
这次我们来看一个大家既熟悉又容易写错的基础模块单链表的查找、插入和删除。它不是什么新框架、新模型但它是一切链表类算法题的地基也是期末考试、考研408和初级算法面试里的常客。网上讲这部分的资料很多但不少教程只给代码不解释边界条件导致很多人抄完能跑却不明白为什么头节点要单独处理、为什么删除节点时有几种不同写法。先说结论带头节点单链表的三个基本操作核心就两句话——查找靠遍历插入靠改指针删除靠跳过节点。如果你能把两个位置处理清楚一个是“头节点之后的第一个节点位置”另一个是“链表尾部的最后位置”那么查、插、删基本不会翻车。这篇文章会把环境准备、代码骨架、查找、插入、删除、完整测试、复杂度分析和常见错误全部过一遍所有代码基于C语言风格实现可以直接编译运行。准备期末复习、考研复习或者面试前想把链表基础打牢的同学这篇文章可以收藏备用。1. 单链表查插删核心能力速览操作时间复杂度带头节点是否修改链表关键注意点初始化链表O(1)是创建头节点并置 next 为 NULL头插法插入O(1)是新节点插入到头节点之后顺序会反转尾插法插入O(n)是先遍历到链表尾部不维护尾指针时为 O(n)指定位置插入O(n)是先找第 i-1 个节点再执行后插在已知节点后插入O(1)是直接改两个指针即可在已知节点前插入O(1)是用“后插 交换数据”的经典技巧按位查找O(n)否从第一个数据节点开始遍历按值查找O(n)否依次比较 data 字段按位删除O(n)是先找第 i-1 个节点再删除后继删除已知节点O(1)是用后继节点数据覆盖再删除后继尾节点除外从表格能看出来单链表最核心的“性价比”在于只要已经拿到了目标节点的位置插入和删除都可以做到 O(1)但如果没有位置、只有序号或值就必须从头遍历时间复杂度升到 O(n)。这个特点直接决定了链表适合什么场景、不适合什么场景。2. 适用场景与学习价值单链表的查、插、删适合谁学第一类是正在上数据结构课的大一、大二学生期末考试基本必考手写链表第二类是准备考研408的同学链表是《数据结构》线性表章节的核心内容第三类是准备算法面试的开发者链表题目本身不难但非常考验指针操作的基本功和边界意识。它能解决什么问题从应用层面看单链表可以用于实现栈、队列、邻接表的底层存储。在很多需要频繁插入删除、不要求随机访问的场景下链表比数组更灵活。从学习层面看掌握单链表之后你再去看循环链表、双向链表、循环双链表会发现套路高度一致改指针、判空、处理头尾边界。这个模块不适合用来做什么它不适合需要快速随机访问的场景。如果你想按下标直接取第 100 个元素单链表做不到顺序表数组才是正解。另外如果链表节点数量非常小比如只有几个元素链表和数组的性能差异可以忽略但代码复杂度明显更高这时候用数组更省事。最后提醒一句学习链表时的代码都建议在本地测试环境里跑通不要只停留在“看懂了”的层面。3. 环境准备与基础代码骨架3.1 编译器与开发环境单链表的代码本身不依赖复杂环境。常见选择有三种Windows 下使用 Visual Studio新建 C 控制台项目。Windows 下使用 VS Code MinGW 的 gcc/g。Linux 或 macOS 下直接使用 gcc/g 编译。这里有一个很容易踩的坑下面很多函数会使用 C 的“引用传参”写法比如LinkList L。如果拿纯 C 编译器编译会直接报错因为 C 语言不支持引用。数据结构教材里为了简化代码经常在 C 环境下写这种风格。如果你想用纯 C 编译需要把LinkList L改成LinkList *L调用时传L。更省事的做法是直接用 g 编译代码主体仍然是“C 风格 引用传参”这也是许多数据结构教材的实际处理方式。3.2 结构体定义与初始化单链表节点的结构体定义如下每个节点保存一个数据域和一个指针域指针指向下一个节点#include stdio.h #include stdlib.h typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这里LNode表示节点类型LinkList表示链表类型。初始化链表时我们创建一个头节点。头节点的 data 可以不用next 先置为 NULLbool InitList(LinkList L) { L (LNode *)malloc(sizeof(LNode)); if (L NULL) { return false; // 内存分配失败 } L-next NULL; return true; }注意malloc返回的是内存地址如果分配失败会返回NULL所以一定要做判空处理。很多初学者写链表不判空在内存紧张或者链表规模很大时程序可能直接崩溃。3.3 打印链表辅助函数后期调试链表时我们经常需要把链表内容打印出来。打印函数从L-next开始遍历遇到NULL停止void PrintList(LinkList L) { LNode *p L-next; printf(head); while (p ! NULL) { printf( - %d, p-data); p p-next; } printf( - NULL\n); }如果打印结果正确显示为head - 10 - 20 - NULL说明当前链表的链接关系是正常的。如果出现死循环大概率是某个节点的 next 指回了前面的节点后面排查章节会展开讲。4. 单链表查找按位查找与按值查找4.1 按位查找按位查找就是按序号查找找到链表中第 i 个数据节点。这里必须注意头节点是第 0 个节点不参与计数。第一个数据节点的序号是 1。实现思路是从L-next开始用计数器 j 从 1 开始累加只要j i就一直往后移动指针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; }这个函数返回的是节点指针。查找成功时返回指向第 i 个节点的指针查找失败时返回 NULL。失败有两种情况一是i 1序号非法二是i超过链表长度循环走到尾节点之后p变成NULL。4.2 按值查找按值查找的顺序是从头节点后的第一个数据节点开始逐个比较 data 是否等于目标值 e。找到第一个相等的节点就返回该节点的指针如果整个链表遍历完都没有找到返回 NULLLNode *LocateElem(LinkList L, int e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; }这段代码的循环条件要理解透彻p ! NULL保证不访问空指针p-data ! e保证还没找到目标值。两者同时满足才继续往后走。只要有一个不满足循环结束。循环结束后如果p ! NULL说明找到了如果p NULL说明遍历完也不存在值等于 e 的节点。4.3 查找操作验证方式查找是后续插入和删除的基础。你可以写一个简单的验证函数比如创建一个包含 10、20、30 的链表调用GetElem(L, 1)预期得到第 1 个节点data 为 10。调用GetElem(L, 5)预期返回 NULL因为链表只有 3 个节点。调用LocateElem(L, 20)预期返回 data 为 20 的节点指针。调用LocateElem(L, 99)预期返回 NULL。查找操作本身不修改链表但它要频繁用到指针移动和判空是链表基本功里最容易出错的一环。写的时候建议在心里画一条指针移动轨迹p 先指向第一个数据节点每移动一次就指向下一个节点直到 NULL 为止。5. 单链表插入头插、尾插与指定位置插入5.1 头插法头插法是把新节点插入到头节点之后也就是每次插入的新节点都成为第一个数据节点。实现步骤是先申请一个新节点 s把数据写入 s-data再把 s 的 next 指向原来头节点后的第一个节点最后让头节点的 next 指向 sbool ListHeadInsert(LinkList L, int e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next L-next; L-next s; return true; }头插法最重要的作用是“逆序建表”。例如按顺序头插 1、2、3最终链表打印出来是head - 3 - 2 - 1 - NULL。这个规律在算法题里经常用到比如反转链表时就可以用头插法重建一条新链表。头插法的时间复杂度是 O(1)因为它永远操作头节点之后的位置。5.2 尾插法尾插法是把新节点追加到链表末尾保持输入顺序。实现时需要先遍历到尾节点然后把尾节点的 next 指向新节点。如果不维护尾指针时间复杂度是 O(n)bool ListTailInsert(LinkList L, int e) { LNode *p L; while (p-next ! NULL) { p p-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next NULL; p-next s; return true; }注意两个细节第一p 从 L 开始而不是从 L-next 开始目的是保持“p 停留在最后一个节点”的语义第二新节点 s-next 必须置为 NULL否则尾节点的 next 没有初始化打印链表时可能变成野指针严重时会崩溃。尾插法建表的结果是顺序保持的依次尾插 1、2、3打印出来是head - 1 - 2 - 3 - NULL。5.3 在指定位置插入指定位置插入比如把元素 e 插入到第 i 个位置。核心思路是先找到第 i-1 个节点然后在这个节点之后执行“后插”操作。如果第 i-1 个节点不存在说明插入位置不合法bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } 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; }这里的边界条件很值得展开。当i 1时我们要把新节点插入到头节点之后。此时循环条件j 0不成立p 停在 L 上等价于头插。当i len 1时p 会遍历到尾节点这时候插入在链表末尾等价于尾插。当i len 1时循环最后 p 变成 NULL直接返回 false。5.4 在已知节点之后插入如果你已经拿到了某个节点的指针 p想在 p 之后插入一个新节点不需要从头遍历。这个操作是 O(1) 的也是单链表的招牌能力。代码可以单独抽成一个辅助函数bool InsertNextNode(LNode *p, int e) { 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; }上一个ListInsert里的后插代码本质就是InsertNextNode(p, e)。抽出来之后代码复用性更好。5.5 在已知节点之前插入如果要求在已知节点 p 之前插入新节点正常情况下需要从头遍历找到 p 的前驱节点复杂度是 O(n)。但有一个非常经典的技巧可以做到 O(1)先把新节点插到 p 的后面然后把 p 的 data 和新节点的 data 交换。逻辑上等于新节点出现在了 p 之前实际物理位置在 p 之后bool InsertPriorNode(LNode *p, int e) { if (p NULL) { return false; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-next p-next; p-next s; s-data p-data; p-data e; return true; }到这里单链表的插入就有四种写法头插、尾插、指定位置插入、已知节点前后插入。建议不要死记代码而是记住一条主线只要是“在某个节点之后插”核心就是s-next p-next; p-next s;这两步其它插入方法都是在为这两步准备一个合适的 p。6. 单链表删除按位删除与删除指定节点6.1 按位删除按位删除是删除第 i 个数据节点。实现上需要找到第 i-1 个节点 p然后让 p 的 next 跨过待删除节点 q直接指向 q 的后继节点最后用free(q)释放 q 的内存bool ListDelete(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) { return false; } LNode *q p-next; e q-data; p-next q-next; free(q); return true; }这里用引用变量 e 把被删除节点的数据带出来方便调用方知道删掉的值。两个失败判断值得注意p NULL说明第 i-1 个节点不存在位置超出链表长度p-next NULL说明第 i-1 个节点是尾节点根本没有第 i 个节点可以删。这两种情况都要返回 false。删除头节点之后的第一个节点时p 就是 Lq 是 L-next执行L-next q-next后原来的第一个节点就从链表中断开了。6.2 删除指定节点如果已经拿到目标节点的指针 p想删除它能不能做到 O(1)可以但有一个关键限制p 不能是尾节点。思路是“偷梁换柱”先把 p 的后继节点 q 的数据拷贝到 p 上再删除 q。这样数据上是 p 被删除了实际释放的是 q 的内存bool DeleteNode(LNode *p) { if (p NULL || p-next NULL) { return false; } LNode *q p-next; p-data q-data; p-next q-next; free(q); return true; }这个函数为什么不能删除尾节点因为尾节点的p-next NULL它没有后继节点也就没有“偷”的对象。如果确实要删除尾节点必须从头遍历找到它的前驱节点再做常规删除。这是一个非常经典的边界题面试官很喜欢问“已知单链表节点的指针如何 O(1) 删除该节点”你如果能答出“非尾节点用后继覆盖尾节点需遍历前驱”就是合格的答案。6.3 清空整张链表删除操作还有一个常见场景销毁整张链表释放所有节点的内存。错误做法是只把L-next置为 NULL这样会造成大量内存泄漏。正确做法是从头节点开始逐节点 freevoid DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *q p-next; free(p); p q; } L NULL; }注意必须先用变量 q 保存 p 的后继节点再 free(p)。如果先 free 再取 p-next就会访问已经释放的内存属于未定义行为。7. 完整测试与效果验证这个主题不涉及网络接口 API也没有批量任务队列但我们可以用一组完整的本地测试用例来模拟“批量验证”的效果初始化链表依次做尾插、头插、指定位置插入、按位查找、按值查找、按位删除、删除指定节点、销毁链表每一步都打印链表结构验证结果是否符合预期。下面给出一份完整的可运行测试程序#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; bool InitList(LinkList L) { L (LNode *)malloc(sizeof(LNode)); if (L NULL) { return false; } L-next NULL; return true; } 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 e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; } bool ListHeadInsert(LinkList L, int e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next L-next; L-next s; return true; } bool ListTailInsert(LinkList L, int e) { LNode *p L; while (p-next ! NULL) { p p-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data e; s-next NULL; p-next s; return true; } bool ListInsert(LinkList L, int i, int e) { if (i 1) { return false; } LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } 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 L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL || p-next NULL) { return false; } LNode *q p-next; e q-data; p-next q-next; free(q); return true; } bool DeleteNode(LNode *p) { if (p NULL || p-next NULL) { return false; } LNode *q p-next; p-data q-data; p-next q-next; free(q); return true; } void PrintList(LinkList L) { LNode *p L-next; printf(head); while (p ! NULL) { printf( - %d, p-data); p p-next; } printf( - NULL\n); } int main() { LinkList L; InitList(L); ListTailInsert(L, 10); ListTailInsert(L, 20); ListTailInsert(L, 30); printf(尾插 10,20,30 后: ); PrintList(L); ListHeadInsert(L, 5); printf(头插 5 后: ); PrintList(L); ListInsert(L, 2, 15); printf(在位置 2 插入 15 后: ); PrintList(L); LNode *node GetElem(L, 3); printf(按位查找第 3 个节点: %d\n, node ? node-data : -1); LNode *find LocateElem(L, 20); printf(按值查找 20: %s\n, find ? 找到了 : 未找到); int e -1; if (ListDelete(L, 1, e)) { printf(删除第 1 个节点删除的值是 %d删除后: , e); PrintList(L); } LNode *p GetElem(L, 2); if (p ! NULL) { DeleteNode(p); printf(删除第 2 个节点后: ); PrintList(L); } DestroyList(L); printf(链表已销毁\n); return 0; }预期输出如下尾插 10,20,30 后: head - 10 - 20 - 30 - NULL 头插 5 后: head - 5 - 10 - 20 - 30 - NULL 在位置 2 插入 15 后: head - 5 - 15 - 10 - 20 - 30 - NULL 按位查找第 3 个节点: 10 按值查找 20: 找到了 删除第 1 个节点删除的值是 5删除后: head - 15 - 10 - 20 - 30 - NULL 删除第 2 个节点后: head - 15 - 20 - 30 - NULL 链表已销毁这份测试覆盖了单链表最核心的路径尾插、头插、指定位置插入、按位查找、按值查找、按位删除、指定节点删除、链销毁。建议你把它跑通后再手动改几个边界场景继续测试在空链表上删除第 1 个节点预期返回 false。在链表长度为 3 时删除第 4 个节点预期返回 false。删除越界节点时 e 不会被写入调用方应保持默认值。在所有测试之后手动检查内存分配和释放是否配对。判断测试是否成功的标准很简单链表打印结果符合预期删除带出的值正确越界操作没有让程序崩溃。如果程序中途段错误优先检查是不是有节点没有初始化 next或者访问了已经 free 的节点。8. 时间复杂度与空间复杂度分析单链表查、插、删的复杂度规律可以总结成一张表操作平均时间复杂度说明按位查找O(n)必须从头开始遍历按值查找O(n)最坏情况遍历完整条链表头插O(1)只操作头节点之后指定位置插入O(n)主要耗时在查找第 i-1 个节点已知节点后插入O(1)只改两个指针已知节点前插入O(1)用后插加交换数据实现按位删除O(n)主要耗时在查找第 i-1 个节点删除已知节点O(1)非尾节点时用后继覆盖实现空间复杂度方面单链表本身需要 O(n) 的空间存储 n 个节点数据。额外操作时每次插入会申请一个节点空间每次删除用 free 释放一个节点空间因此插入和删除的额外辅助空间是 O(1)。需要特别理解的是链表和数组的复杂度差异。数组按下标访问是 O(1)但插入删除要移动大量元素。链表反过来按位访问是 O(n)但一旦拿到目标节点插入删除可以做到 O(1)。所以面试里常见的“数组和链表有什么区别”核心答案就是数组擅长随机访问、内存连续、缓存友好链表擅长频繁插入删除、不要求连续内存、动态扩容更方便。没有绝对优势只有场景匹配。9. 常见错误与排查方法实践过程中最常见的报错和异常现象可以对照下面的表排查问题现象可能原因排查方式解决方案编译报错 expected ‘LNode **’ but argument is of type ‘LNode *’纯 C 编译器不支持引用传参检查编译器和函数参数使用 g 编译或把参数改成LNode **L调用时传L程序段错误 Segfault访问了空指针或已释放节点用调试器定位崩溃行访问前判空释放后不要再使用打印链表死循环尾节点 next 没有置 NULL或插入时形成环打印每个节点地址检查是否重复新节点 next 必须初始化检查尾节点指向插入位置总是差 1ListInsert 中 p 的初始位置或者 j 的起算没写对画指针移动轨迹打印中间节点从 pL、j0 开始先移动 i-1 次删除后无法找到链表头部误删了头节点或头指针被修改打印 L 的值不要 free(L)删除数据节点时 p 保留在 L内存持续增长删除节点时没有 free使用内存检测工具free(q)销毁链表时逐节点释放DeleteNode 删除尾节点失败尾节点没有后继可覆盖断点打印 p-next尾节点必须找到前驱再删除链表打印多出随机值新节点 next 没有初始化检查 malloc 后是否赋值s-next NULL;这里最值得深入的是一个常见错误插入和删除时“指针更新顺序写反”。插入时正确顺序是先把新节点的 next 指向 p 的 next再把 p 的 next 指向新节点。如果先执行p-next s就会让 p 原来的后继节点丢失新节点就无法接上原来的链。这两行代码的顺序在面试手写链表时经常被考一定要形成肌肉记忆s-next p-next; p-next s;另一个常见错误是删除操作时没有先把 q 的后继存下来就开始 free。正确写法是先用p-next q-next断开再free(q)。如果先 free(q) 再访问 q-next就是典型的“悬垂指针”问题。10. 最佳实践与学习建议单链表的查、插、删虽然简单但要写得稳还是需要一些方法。第一画图比写代码重要。你在纸上画出头节点、数据节点和箭头然后手动模拟一次插入或删除操作观察指针指向的变化。画完再写代码正确率会高很多。很多指针写错的根源是脑子里没有清晰的箭头模型。第二维护一套最小可运行模板。把初始化、打印、查找、后插、删除这几个核心函数整合到一个文件里当作以后写链表题的“工具箱”。面试或考试时很多链表算法题都可以调用这些基础操作来简化思路。第三测试不能只看正常路径。要专门测边界在第 1 个位置插入、在末尾插入、在越界位置插入、在空链表上删除、删除最后一个节点。边界能过说明你对链表的位置语义理解是准确的。第四内存管理要养成习惯。malloc和free要配对删除节点后及时 free。写正规项目时链表的销毁、异常分支的内存释放都要处理好。这个问题在 C/C 面试里是高频追问点。第五学完单链表后建议用同样的思路扩展循环链表、双向链表、双向循环链表栈和队列的链式存储这些都离不开今天的指针操作。算法刷题方面可以拿 LeetCode 的链表反转、合并两个有序链表、删除倒数第 N 个节点、判断链表是否有环等题目练手但要从自己实现的链表节点和函数开始写而不是只调用现成库。第六数据结构的代码有一定重复性适合用“教材模板 自己改写”的方式学习。但不要把别人的代码直接背下来而是理解每一步的语义。比如看到p-next q-next你要能说出它的含义是“让 p 跳过 q指向 q 的后继节点”。11. 总结单链表的查找、插入和删除核心内容可以用三条主线概括查找靠遍历插入靠改指针删除靠跳过节点。真正的难点不在算法思想而在边界处理头节点位置、越界位置、空链表、尾节点、内存释放这些细节才是区分“看懂了”和“写得对”的分水岭。这篇文章给出的所有代码都围绕带头节点的单链表实现完整测试程序可以直接编译运行。建议你拿到代码后先跑一遍观察每一步打印结果再手动构造几个边界用例测试失败路径。如果能把插入的两个关键行写对、能说清楚为什么 DeleteNode 无法删除尾节点、能画出头插和尾插建表的顺序差异说明这块基础已经过关了。单链表学会之后下一步可以试着用同样的思路写循环链表和双向链表也可以直接去刷几道链表章节的算法题。平时写代码时记得保留一份最小可运行模板考试或面试前快速过一遍比临时翻书高效得多。这篇内容建议收藏备用等真正动手写链表时再翻出来对照。
