很多朋友在初学数据结构时第一个“劝退点”往往不是顺序表而是单链表。明明数组用得好好的为什么非要搞一个带指针的链表更头疼的是单链表的“查、插、删”三个操作教材上写得逻辑清晰自己一写代码就段错误或者插入后链表变成死循环。这篇文章就把单链表的查找、插入、删除三个核心操作拆开揉碎从原理推导到代码实现再结合常见考题和易错场景帮你一次性理清。本文适合正在学习数据结构的大学生、准备考研复试的考生、以及需要手写链表面试题的开发者。读完你不仅能写出正确的单链表增删改查代码还能理解每个操作背后的指针变化过程遇到类似的链表问题也不会慌。1. 为什么单链表要单独学“查插删”1.1 单链表和数组的本质区别数组在内存中是连续存储的访问第 i 个元素可以直接通过下标计算地址时间复杂度是 O(1)。但数组的插入和删除平均需要移动一半的元素时间复杂度是 O(n)。单链表则相反。链表中的每个节点在内存中是分散存放的节点之间通过指针连接。它牺牲了“随机访问”的能力——想找第 i 个节点必须从头开始走时间复杂度是 O(n)。但换来的是插入和删除的灵活性只要找到目标位置修改指针就能完成操作不需要移动数据。这就是为什么数据结构课程一定会把“单链表的查、插、删”单独拿出来讲——它是理解指针操作、内存管理、算法复杂度分析的最佳入门案例。1.2 单链表的基本结构一个单链表节点通常包含两部分数据域存储实际数据。指针域存储下一个节点的地址。用 C 语言定义如下// 文件路径linklist.h #include stdio.h #include stdlib.h #include stdbool.h typedef struct LNode { int data; // 数据域这里以 int 为例 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这里有两个关键概念需要区分LNode表示节点类型。LinkList表示链表类型本质上是指向头节点的指针。也就是LinkList L等价于LNode *L但在阅读代码时用LinkList声明变量能更明确地表达“这是一个链表”用LNode *声明变量则更强调“这是一个节点指针”。这种写法在王道、严蔚敏等教材中很常见建议保持。1.3 本章节要解决的核心问题单链表的操作远不止“查插删”但“查插删”是所有其他操作的基础。比如链表反转本质上是反复使用“头插法”插入节点。链表排序本质上是“查找合适位置 插入节点”。链表去重本质上是“遍历查找 删除重复节点”。所以如果你能把查、插、删的代码写得行云流水后面很多复杂算法题都会轻松很多。2. 环境准备与测试框架2.1 开发环境说明本文示例代码使用 C 语言编写主要原因是数据结构教材和考研大纲都以 C/C 为主。如果你的环境是 VS Code、Dev-C、Code::Blocks、CLion或者在线编译器都可以直接运行。以下是推荐环境参考操作系统Windows / Linux / macOS 均可编译器GCC 或 MSVC代码标准C99 及以上因为使用了stdbool.h构建方式单文件编译命令如下gcc -o linklist_demo linklist_demo.c ./linklist_demo如果你的编译器较老不支持stdbool.h可以把bool改成inttrue/false改成1/0。版本需要根据你的项目实际情况调整本文示例以常见环境为例重点演示代码思路。2.2 统一的测试辅助函数为了方便验证每一步操作我们需要几个基础辅助函数初始化空链表打印链表销毁链表完整代码如下// 文件路径linklist_demo.c #include linklist.h // 初始化一个带头节点的空链表 bool InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) { return false; // 内存分配失败 } (*L)-next NULL; return true; } // 判断链表是否为空 bool Empty(LinkList L) { return L-next NULL; } // 打印链表所有节点 void PrintList(LinkList L) { if (L NULL || L-next NULL) { printf([空链表]\n); return; } LNode *p L-next; printf(链表内容: ); while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 销毁链表释放所有节点内存 void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *next p-next; free(p); p next; } printf(链表已销毁\n); }这里的InitList使用二级指针LinkList *L是因为我们需要在函数内部修改主调函数中的头指针。如果不用二级指针头指针的修改无法传回主调函数这是初学者最容易犯的错误。2.3 测试主函数设计后面每实现一个操作我都会在main函数中补上对应的测试代码。你也可以把每段测试单独写成函数方便调试。3. 单链表查找操作详解查找操作分为两种按位查找返回第 i 个节点。按值查找返回第一个值为 value 的节点。两者的时间复杂度都是 O(n)因为链表不支持随机访问。3.1 按位查找按位查找的思想很简单从头节点开始工作指针p依次后移用一个计数器j记录当前是第几个节点。当j i时p指向的就是要找的节点。// 按位查找返回第 i 个节点带头节点i 从 1 开始 LNode *GetElem(LinkList L, int i) { if (i 1) { return NULL; // 位置不合法 } LNode *p L; // p 从头节点开始 int j 0; // 头节点记为第 0 个节点 while (p ! NULL j i) { p p-next; j; } return p; }这里有个容易混淆的地方头节点不算有效数据节点。所以GetElem(L, 1)返回的是第一个数据节点而不是头节点。循环条件中p ! NULL用于防止越界如果 i 超过链表长度函数返回NULL。测试代码如下void TestGetElem() { LinkList L; InitList(L); // 创建 3 个节点 LNode *a (LNode *)malloc(sizeof(LNode)); a-data 10; a-next NULL; L-next a; LNode *b (LNode *)malloc(sizeof(LNode)); b-data 20; b-next NULL; a-next b; LNode *c (LNode *)malloc(sizeof(LNode)); c-data 30; c-next NULL; b-next c; PrintList(L); LNode *p GetElem(L, 2); if (p ! NULL) { printf(第2个节点值为: %d\n, p-data); } else { printf(未找到第2个节点\n); } }运行结果链表内容: 10 20 30 第2个节点值为: 203.2 按值查找按值查找需要遍历链表依次比较节点的数据域。找到第一个相等的节点就返回找不到返回NULL。// 按值查找返回第一个 data value 的节点 LNode *LocateElem(LinkList L, int value) { LNode *p L-next; while (p ! NULL p-data ! value) { p p-next; } return p; }这个实现很直观p从第一个数据节点开始只要没到链表末尾就判断当前节点数据是否等于目标值。循环结束有两种可能p NULL链表遍历完了没找到。p-data value找到了p指向目标节点。3.3 查找操作的复杂度分析操作最好情况最坏情况平均情况按位查找O(1)i1O(n)inO(n)按值查找O(1)首节点命中O(n)末节点命中O(n)需要注意的是在单链表中“查找”永远需要从头遍历这是链表的先天限制。面试中如果要求优化查找效率通常需要借助其他数据结构比如跳表、哈希表辅助索引等这属于进阶内容本文暂不展开。4. 单链表插入操作详解插入操作是单链表最核心的操作也是很多同学写错的重灾区。先理解一个基本结论在单链表中已知某节点 p可以很方便地在 p 之后插入新节点但想在 p 之前插入需要从头遍历找到 p 的前驱节点。4.1 后插操作在指定节点之后插入后插的思路创建新节点s。将s的 next 指向p的 next。将p的 next 指向s。// 在节点 p 之后插入值为 value 的节点 bool InsertNextNode(LNode *p, int value) { if (p NULL) { return false; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-data value; s-next p-next; p-next s; return true; }这里的指针修改顺序非常关键。一定要先让s-next p-next再让p-next s。如果顺序反了先执行p-next s那么原链表在 p 之后的部分就会丢失因为没有任何指针指向它们了。用图示表示修改过程初始p - q - ... 第1步s-next q s 指向 q 第2步p-next s p 指向 s 结果p - s - q - ...4.2 前插操作在指定节点之前插入前插最直观的方法是从头遍历链表找到 p 的前驱节点 pre然后在 pre 之后插入新节点。这样需要 O(n) 的时间。但有一个经典技巧可以做到 O(1) 前插在 p 之后插入一个新节点 s。把 p 的 data 复制到 s。把新值写入 p 的 data。这样实际上是把“新节点”放在了 p 的位置而原来的 p 节点被“挤”到了后面逻辑效果等同于在 p 之前插入。// 在节点 p 之前插入值为 value 的节点O(1) 技巧 bool InsertPriorNode(LNode *p, int value) { if (p NULL) { return false; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return false; } s-next p-next; p-next s; // 新节点 s 链接到 p 之后 s-data p-data; // p 原数据复制给 s p-data value; // p 放入新值 return true; }这种方法的优点是时间复杂度是 O(1)缺点是交换了数据而不是真正改变节点位置。在大多数场景下这种数据交换是允许的但在某些严格要求“节点地址稳定”的场景比如外部持有节点指针需要谨慎使用。4.3 头插法建立链表头插法每次把新节点插入到头节点之后。它的特点是最终链表顺序和输入顺序相反。// 头插法创建链表 LinkList List_HeadInsert(LinkList *L, int data[], int len) { InitList(L); for (int i 0; i len; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data data[i]; s-next (*L)-next; // 新节点指向原第一个节点 (*L)-next s; // 头节点指向新节点 } return *L; }4.4 尾插法建立链表尾插法需要维护一个尾指针r每次把新节点接到尾部然后更新尾指针。// 尾插法创建链表 LinkList List_TailInsert(LinkList *L, int data[], int len) { InitList(L); LNode *r *L; // 尾指针 for (int i 0; i len; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data data[i]; s-next NULL; r-next s; // 尾节点指向新节点 r s; // 更新尾指针 } return *L; }尾插法的关键在于保持r始终指向链表最后一个节点。如果不维护尾指针每次插入都需要遍历到链表尾部时间复杂度会退化为 O(n²)。4.5 按位插入有了GetElem和InsertNextNode按位插入就很简单了先找到第 i-1 个节点然后执行后插操作。// 在第 i 个位置插入值为 value 的节点带头节点i 从 1 开始 bool ListInsert(LinkList L, int i, int value) { if (i 1) { return false; } LNode *p GetElem(L, i - 1); // 找到第 i-1 个节点 return InsertNextNode(p, value); }这里需要注意GetElem(L, 0)返回的是头节点因为我们的GetElem从j 0开始计数头节点的位置是 0。因此ListInsert(L, 1, value)表示在第一个数据节点之前插入代码上等价于在头节点之后插入。4.6 插入操作完整测试void TestInsert() { LinkList L; int arr[] {10, 20, 30}; List_TailInsert(L, arr, 3); PrintList(L); // 链表内容: 10 20 30 // 在第 2 个位置插入 99 ListInsert(L, 2, 99); PrintList(L); // 链表内容: 10 99 20 30 // 在第一个节点之前前插 77 LNode *first L-next; InsertPriorNode(first, 77); PrintList(L); // 链表内容: 77 10 99 20 30 }运行结果链表内容: 10 20 30 链表内容: 10 99 20 30 链表内容: 77 10 99 20 305. 单链表删除操作详解删除操作的核心是找到要删除节点的前驱节点然后修改前驱节点的 next 指针跳过待删除节点。5.1 按位删除按位删除需要两个步骤找到第 i-1 个节点也就是待删除节点的前驱。修改前驱的 next指向待删除节点的下一个节点。释放待删除节点的内存。// 删除第 i 个节点并用 result 返回被删除节点的数据 bool ListDelete(LinkList L, int i, int *result) { if (i 1) { return false; } LNode *p GetElem(L, i - 1); // 找到前驱节点 if (p NULL || p-next NULL) { return false; // 第 i 个节点不存在 } LNode *q p-next; // q 指向待删除节点 *result q-data; // 保存数据 p-next q-next; // 跳过 q free(q); // 释放内存 return true; }注意p NULL || p-next NULL的检查顺序先判断前驱是否存在再判断待删除节点是否存在。如果前驱为空访问p-next会段错误。5.2 删除指定节点O(1) 技巧与插入类似删除指定节点也可以有 O(1) 的实现把后继节点的数据复制到当前节点然后删除后继节点。这同样是一种数据搬移技巧。// 删除指定节点 pO(1) 技巧 bool DeleteNode(LNode *p) { if (p NULL || p-next NULL) { return false; // 最后一个节点不能用此方法 } LNode *q p-next; // q 是 p 的后继 p-data q-data; // 复制数据 p-next q-next; // 跳过 q free(q); // 释放 q return true; }需要注意的是这种方法只能删除非末尾节点。如果 p 是最后一个节点p-next NULL我们找不到后继去搬移数据此时只能从头遍历找到 p 的前驱再按常规方式删除。这也是考研和面试中常考的一个小坑。5.3 删除整个链表删除整个链表时需要从第一个节点开始逐个free。注意一定要保存下一个节点的指针否则free当前节点后就找不到后续节点了。void FreeList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *next p-next; free(p); p next; } }5.4 删除操作完整测试void TestDelete() { LinkList L; int arr[] {10, 20, 30, 40}; List_TailInsert(L, arr, 4); PrintList(L); // 链表内容: 10 20 30 40 int value 0; bool ok ListDelete(L, 3, value); if (ok) { printf(删除第3个节点值为: %d\n, value); // 删除 30 } PrintList(L); // 链表内容: 10 20 40 }6. 完整可运行的示例代码把以上所有操作整合到一个完整的示例程序中// 文件路径linklist_demo.c #include stdio.h #include stdlib.h #include stdbool.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; } void PrintList(LinkList L) { if (L NULL || L-next NULL) { printf([空链表]\n); return; } LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } LNode *GetElem(LinkList L, int i) { if (i 1) return NULL; LNode *p L; int j 0; while (p ! NULL j i) { p p-next; j; } return p; } LNode *LocateElem(LinkList L, int value) { LNode *p L-next; while (p ! NULL p-data ! value) { p p-next; } return p; } bool InsertNextNode(LNode *p, int value) { if (p NULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return false; s-data value; s-next p-next; p-next s; return true; } bool ListInsert(LinkList L, int i, int value) { if (i 1) return false; LNode *p GetElem(L, i - 1); return InsertNextNode(p, value); } bool ListDelete(LinkList L, int i, int *result) { if (i 1) return false; LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) return false; LNode *q p-next; *result q-data; p-next q-next; free(q); return true; } void List_TailInsert(LinkList *L, int data[], int len) { InitList(L); LNode *r *L; for (int i 0; i len; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data data[i]; s-next NULL; r-next s; r s; } } void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *next p-next; free(p); p next; } } int main() { LinkList L; int arr[] {10, 20, 30, 40, 50}; List_TailInsert(L, arr, 5); printf(初始链表:\n); PrintList(L); printf(\n查找测试:\n); LNode *p GetElem(L, 3); printf(第3个节点: %d\n, p ? p-data : -1); p LocateElem(L, 40); printf(值为40的节点: %s\n, p ? 找到 : 未找到); printf(\n插入测试:\n); ListInsert(L, 2, 25); PrintList(L); printf(\n删除测试:\n); int deleted; if (ListDelete(L, 4, deleted)) { printf(删除了节点值: %d\n, deleted); } PrintList(L); DestroyList(L); return 0; }预期运行结果初始链表: 10 20 30 40 50 查找测试: 第3个节点: 30 值为40的节点: 找到 插入测试: 10 25 20 30 40 50 删除测试: 删除了节点值: 30 10 25 20 40 50这份代码可以直接保存为linklist_demo.c用 GCC 编译运行。7. 常见错误与排查思路写链表代码最常见的报错就是段错误Segmentation Fault其次是死循环。下面整理了几类高频问题。问题现象常见原因解决思路程序崩溃段错误访问了 NULL 指针或野指针检查是否在p NULL时访问了p-next插入后链表丢失后半部分指针修改顺序错误先让新节点指向后继再让前驱指向新节点链表打印出现死循环节点 next 指向了自身或前驱画图检查每个节点 next 的指向删除节点后无法访问链表没有修改前驱的 next删除时必须让前驱跳过待删除节点InitList后链表仍为空没有使用二级指针需要修改头指针本身时必须传LinkList *free 后程序崩溃还持有被释放节点的指针并访问free 后立即将指针置为 NULL7.1 指针修改顺序错误这是最典型的问题。在后插操作中以下两种写法的区别非常关键错误写法p-next s; // 先让 p 指向 s s-next q; // 再让 s 指向 q此时 q 找不到了正确写法s-next q; // 先让 s 指向 q p-next s; // 再让 p 指向 s判断标准很简单在执行第一步操作前要确保后面需要的指针仍然可以通过已有路径访问到。7.2 避免段错误的排查清单如果你在写链表代码时遇到段错误按以下顺序排查检查所有malloc的返回值是否为NULL。检查GetElem返回的p在使用前是否为NULL。检查头节点是否初始化L-next是否指向了合法内存。检查free之后是否还访问了被释放的节点。在关键节点打印指针地址确认链表结构是否和预期一致。推荐在调试时打印指针地址类似printf(p %p, p-next %p\n, p, p-next);这样可以直观看到指针的跳转关系比单纯看逻辑更容易发现问题。8. 经典考题与进阶讨论8.1 合并两个升序单链表相关热搜中有一个经典问题“已知两个长度为 m 和 n 的升序单链表”。这类题最常见的考法是合并两个升序链表为一个新的升序链表。思路如下设置两个指针pa和pb分别指向两个链表的第一个节点。比较pa-data和pb-data把较小者接入新链表。被选中的指针后移一位。如果某个链表先走到末尾直接把另一个链表剩余部分接入新链表。示例代码使用原有节点不额外申请空间LinkList MergeList(LinkList La, LinkList Lb) { LinkList Lc (LNode *)malloc(sizeof(LNode)); LNode *pa La-next; LNode *pb Lb-next; LNode *r Lc; // 尾指针 while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { r-next pa; r pa; pa pa-next; } else { r-next pb; r pb; pb pb-next; } } r-next (pa ! NULL) ? pa : pb; free(La); free(Lb); return Lc; }注意这里最后直接把剩余链表接上不需要逐个拷贝节点时间复杂度是 O(mn)。8.2 其他高频单链表面试题单链表反转递归法和迭代法都要会。迭代法核心是逐个摘节点并头插到新链表。检测链表是否有环快慢指针法慢指针每次走一步快指针每次走两步相遇则有环。查找链表中间节点同样用快慢指针快指针到末尾时慢指针正好在中间。删除链表倒数第 k 个节点先让快指针走 k 步然后两个指针一起走快指针到末尾时慢指针指向倒数第 k 个节点。判断两个链表是否相交先各自遍历一次得到长度让长链表先走长度差再同步走。这些题目都是本文“查插删”操作的延伸建议在掌握基础操作后逐个刷一遍。9. 最佳实践与工程建议9.1 关于头节点在工程中强烈建议使用带头节点的链表。头节点的好处是插入和删除第一个数据节点时不需要单独修改头指针。空表和非空表的处理逻辑统一代码更简洁。查找位置时i 从 1 开始计数的语义更自然。如果不带头节点首节点的插入和删除需要修改头指针本身必须使用二级指针且代码分支更多容易出错。9.2 关于内存管理每次malloc都要检查返回值不能假设内存一定分配成功。每次free之后建议把指针置为NULL避免悬空指针。删除链表时必须先保存下一个节点的地址再释放当前节点。程序退出前确认所有动态分配的节点都已释放避免内存泄漏。9.3 关于代码可读性命名要清晰p、q、s、r等指针变量在教材中广泛使用但阅读代码时建议配合注释。每个函数只做一件事。例如“找前驱”和“插入”分开“插入”和“创建节点”也分开。把打印链表、初始化链表等辅助函数抽离出来方便调试和复用。重要操作如插入、删除的返回值用bool类型表达成功或失败不要只看指针是否为空。9.4 关于算法复杂度写链表题时一定要能清晰说出每个操作的时间复杂度操作时间复杂度说明按位查找O(n)需要从头遍历按值查找O(n)需要逐个比较尾插法建立链表O(n)维护尾指针头插法建立链表O(n)每次插入 O(1)后插操作O(1)已知前驱节点前插操作数据搬移法O(1)已知目标节点按位插入O(n)主要花费在查找按位删除O(n)主要花费在查找删除指定节点非尾节点O(1)数据搬移法面试手写代码时能主动分析复杂度并在代码注释中用自然语言解释思路会是不错的加分项。9.5 关于测试每个操作都要测试边界情况空链表、只有一个节点、操作第一个节点、操作最后一个节点、位置超界。建议用多条不同长度的链表分别测试不要只测一条 happy path。在编写链表代码时可以借助 ValgrindLinux或地址消毒器检测内存泄漏。10. 总结单链表的查、插、删是数据结构学习中绕不开的核心内容。这篇文章从节点定义、环境准备开始详细分析了查找、插入、删除三类操作的基本原理、代码实现和复杂度最后给出了完整的可运行示例、常见错误排查清单和经典面试题思路。回顾一下关键收获链表通过指针连接分散的内存节点牺牲随机访问换取插入删除的灵活性。插入的核心是“先链接新节点的后继再修改前驱的 next”。删除的核心是“找到前驱跳过待删除节点释放内存”。前插和删除指定节点都有 O(1) 的数据搬移技巧但要注意边界条件。画图理解指针变化永远比死记代码更有效。如果这篇文章对你有帮助可以收藏备用。下一步建议练习单链表反转和有序链表合并这两道题能帮你把查插删操作融会贯通。动手把代码敲一遍遇到问题再看文章印象会深得多。