单链表查插删操作详解：从原理到代码实现

很多朋友在初学数据结构时，第一个“劝退点”往往不是顺序表，而是单链表。明明数组用得好好的，为什么非要搞一个带指针的链表？更头疼的是，单链表的“查、插、删”三个操作，教材上写得逻辑清晰，自己一写代码就段错误，或者插入后链表变成死循环。这篇文章就把单链表的查找、插入、删除三个核心操作拆开揉碎，从原理推导到代码实现，再结合常见考题和易错场景，帮你一次性理清。

本文适合正在学习数据结构的大学生、准备考研复试的考生、以及需要手写链表面试题的开发者。读完你不仅能写出正确的单链表增删改查代码，还能理解每个操作背后的指针变化过程，遇到类似的链表问题也不会慌。

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改成int，true/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个节点值为: 20

3.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从第一个数据节点开始，只要没到链表末尾，就判断当前节点数据是否等于目标值。循环结束有两种可能：

1. p == NULL：链表遍历完了，没找到。
2. p->data == value：找到了，p指向目标节点。

3.3 查找操作的复杂度分析

需要注意的是，在单链表中“查找”永远需要从头遍历，这是链表的先天限制。面试中如果要求优化查找效率，通常需要借助其他数据结构，比如跳表、哈希表辅助索引等，这属于进阶内容，本文暂不展开。

4. 单链表插入操作详解

插入操作是单链表最核心的操作，也是很多同学写错的重灾区。先理解一个基本结论：

在单链表中，已知某节点 p，可以很方便地在 p 之后插入新节点；但想在 p 之前插入，需要从头遍历找到 p 的前驱节点。

4.1 后插操作（在指定节点之后插入）

后插的思路：

1. 创建新节点s。
2. 将s的 next 指向p的 next。
3. 将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) 前插：

1. 在 p 之后插入一个新节点 s。
2. 把 p 的 data 复制到 s。
3. 把新值写入 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 30

5. 单链表删除操作详解

删除操作的核心是：找到要删除节点的前驱节点，然后修改前驱节点的 next 指针，跳过待删除节点。

5.1 按位删除

按位删除需要两个步骤：

1. 找到第 i-1 个节点，也就是待删除节点的前驱。
2. 修改前驱的 next，指向待删除节点的下一个节点。
3. 释放待删除节点的内存。

// 删除第 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) 的实现：把后继节点的数据复制到当前节点，然后删除后继节点。这同样是一种数据搬移技巧。

// 删除指定节点 p（O(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），其次是死循环。下面整理了几类高频问题。

7.1 指针修改顺序错误

这是最典型的问题。在后插操作中，以下两种写法的区别非常关键：

错误写法：

p->next = s; // 先让 p 指向 s s->next = q; // 再让 s 指向 q，此时 q 找不到了

正确写法：

s->next = q; // 先让 s 指向 q p->next = s; // 再让 p 指向 s

判断标准很简单：在执行第一步操作前，要确保后面需要的指针仍然可以通过已有路径访问到。

7.2 避免段错误的排查清单

如果你在写链表代码时遇到段错误，按以下顺序排查：

1. 检查所有malloc的返回值是否为NULL。
2. 检查GetElem返回的p在使用前是否为NULL。
3. 检查头节点是否初始化，L->next是否指向了合法内存。
4. 检查free之后是否还访问了被释放的节点。
5. 在关键节点打印指针地址，确认链表结构是否和预期一致。

推荐在调试时打印指针地址，类似：

printf("p = %p, p->next = %p\n", p, p->next);

这样可以直观看到指针的跳转关系，比单纯看逻辑更容易发现问题。

8. 经典考题与进阶讨论

8.1 合并两个升序单链表

相关热搜中有一个经典问题：“已知两个长度为 m 和 n 的升序单链表”。这类题最常见的考法是合并两个升序链表为一个新的升序链表。

思路如下：

1. 设置两个指针pa和pb分别指向两个链表的第一个节点。
2. 比较pa->data和pb->data，把较小者接入新链表。
3. 被选中的指针后移一位。
4. 如果某个链表先走到末尾，直接把另一个链表剩余部分接入新链表。

示例代码（使用原有节点，不额外申请空间）：

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(m+n)。

8.2 其他高频单链表面试题

• 单链表反转：递归法和迭代法都要会。迭代法核心是逐个摘节点并头插到新链表。
• 检测链表是否有环：快慢指针法，慢指针每次走一步，快指针每次走两步，相遇则有环。
• 查找链表中间节点：同样用快慢指针，快指针到末尾时，慢指针正好在中间。
• 删除链表倒数第 k 个节点：先让快指针走 k 步，然后两个指针一起走，快指针到末尾时，慢指针指向倒数第 k 个节点。
• 判断两个链表是否相交：先各自遍历一次得到长度，让长链表先走长度差，再同步走。

这些题目都是本文“查插删”操作的延伸，建议在掌握基础操作后逐个刷一遍。

9. 最佳实践与工程建议

9.1 关于头节点

在工程中，强烈建议使用带头节点的链表。头节点的好处是：

• 插入和删除第一个数据节点时，不需要单独修改头指针。
• 空表和非空表的处理逻辑统一，代码更简洁。
• 查找位置时，i 从 1 开始计数的语义更自然。

如果不带头节点，首节点的插入和删除需要修改头指针本身，必须使用二级指针，且代码分支更多，容易出错。

9.2 关于内存管理

• 每次malloc都要检查返回值，不能假设内存一定分配成功。
• 每次free之后，建议把指针置为NULL，避免悬空指针。
• 删除链表时，必须先保存下一个节点的地址，再释放当前节点。
• 程序退出前，确认所有动态分配的节点都已释放，避免内存泄漏。

9.3 关于代码可读性

• 命名要清晰，p、q、s、r等指针变量在教材中广泛使用，但阅读代码时建议配合注释。
• 每个函数只做一件事。例如“找前驱”和“插入”分开，“插入”和“创建节点”也分开。
• 把打印链表、初始化链表等辅助函数抽离出来，方便调试和复用。
• 重要操作（如插入、删除）的返回值用bool类型表达成功或失败，不要只看指针是否为空。

9.4 关于算法复杂度

写链表题时，一定要能清晰说出每个操作的时间复杂度：

面试手写代码时，能主动分析复杂度，并在代码注释中用自然语言解释思路，会是不错的加分项。

9.5 关于测试

• 每个操作都要测试边界情况：空链表、只有一个节点、操作第一个节点、操作最后一个节点、位置超界。
• 建议用多条不同长度的链表分别测试，不要只测一条 happy path。
• 在编写链表代码时，可以借助 Valgrind（Linux）或地址消毒器检测内存泄漏。

10. 总结

单链表的查、插、删是数据结构学习中绕不开的核心内容。这篇文章从节点定义、环境准备开始，详细分析了查找、插入、删除三类操作的基本原理、代码实现和复杂度，最后给出了完整的可运行示例、常见错误排查清单和经典面试题思路。

回顾一下关键收获：

• 链表通过指针连接分散的内存节点，牺牲随机访问换取插入删除的灵活性。
• 插入的核心是“先链接新节点的后继，再修改前驱的 next”。
• 删除的核心是“找到前驱，跳过待删除节点，释放内存”。
• 前插和删除指定节点都有 O(1) 的数据搬移技巧，但要注意边界条件。
• 画图理解指针变化，永远比死记代码更有效。

如果这篇文章对你有帮助，可以收藏备用。下一步建议练习单链表反转和有序链表合并，这两道题能帮你把查插删操作融会贯通。动手把代码敲一遍，遇到问题再看文章，印象会深得多。