【C 语言数据结构】单链表基础操作详解（头插 / 尾插 / 头删 / 尾删 / 查找）
前言
单链表是 C 语言数据结构中最基础也最核心的线性表结构之一，相比顺序表，单链表的内存布局更灵活，无需连续内存空间，增删操作（非头尾）效率更高。本文将从设计思路、实现步骤、踩坑点三个维度，拆解单链表基础操作的完整思考过程，不仅告诉你代码怎么写，更讲清楚为什么这么写，以及写链表代码的通用思考方法。
一、单链表的结构体定义
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 数据类型重定义，方便后续修改（比如改成char/long等）
typedef int DaTy;
// 单链表节点结构体
typedef struct LinkList
{
DaTy a; // 节点存储的数据
struct LinkList* next; // 指向下一个节点的指针
}LL; // 重命名为LL，简化后续使用
设计思路与方法
二、核心辅助函数
辅助函数是链表操作的「地基」，所有增删查改都依赖它们，写好辅助函数能大幅减少重复代码和出错概率。
2.1 创建新节点（SLTBuyNode）
LL* SLTBuyNode(DaTy x)
{
// 申请节点内存
LL* newnode = (LL*)malloc(sizeof(LL));
// 内存申请失败处理（必做！）
if (newnode == NULL)
{
perror("malloc fall!"); // 打印错误原因
exit(1); // 终止程序，避免空指针操作
}
newnode->a = x; // 初始化节点数据
newnode->next = NULL; // 新节点默认指向NULL，避免野指针
return newnode;
}
设计思路与实现步骤
- 封装思路：把「申请内存 + 初始化 + 错误处理」封装成一个函数，后续所有插入操作都直接调用，不用每次重复写 malloc。这是代码复用的核心思想：重复逻辑抽离成函数。
- 实现三步法：
- 用malloc申请一块和节点大小相等的堆内存
- 判空兜底：内存申请失败直接报错退出，防止后续空指针解引用崩溃
- 初始化两个成员：数据赋值，指针域默认置空，杜绝野指针
- 思考方法：凡是申请动态内存，必做判空；凡是创建指针，必初始化。这是 C 语言工程编码的基本素养。
2.2 打印链表（Print）
void Print(LL* phead)
{
LL* pcur = phead; // 遍历指针，从表头开始
while (pcur) // 等价于pcur != NULL，遍历到尾节点结束
{
printf("%d->",pcur->a);
pcur = pcur -> next; // 移动到下一个节点
}
printf("NULL\\n"); // 链表尾标识，增强可读性
}
设计思路与遍历模板
- 核心思想：打印是链表最基础的「遍历操作」，所有链表操作（查找、计数、销毁）都基于这个遍历模板。
- 遍历通用四要素：
- 起点：用临时指针pcur从表头开始，绝不直接修改头指针（头指针一旦改了，链表就找不到了）
- 终止条件：pcur == NULL（走到尾节点之后停止）
- 每轮操作：打印当前节点的数据
- 指针移动：pcur = pcur->next，往后走一个节点
- 易错点提醒：终止条件不能写成pcur->next != NULL，否则最后一个节点会被漏掉。判断条件怎么选，取决于你要操作「当前节点」还是「下一个节点」。
2.3 查找节点（SLFin）
LL* SLFin(LL* phead, DaTy x)
{
LL* pcur = phead;
while (pcur)
{
if (pcur->a == x) // 找到目标值，返回节点地址
{
return pcur;
}
pcur = pcur->next;
}
return NULL; // 遍历完未找到，返回NULL
}
设计思路与方法
- 功能定位：查找是插入、删除的前置操作。单链表没有下标，想在某个值前后插入 / 删除，必须先按值找到节点地址，这是链表「按值操作」的必经之路。
- 模板复用思想：代码框架和打印函数完全一致，只是把「打印」换成了「数值比较 + 返回」。学会复用遍历模板，写链表代码速度会大幅提升。
- 接口设计原则：查找只返回节点地址，不打印、不修改。把打印逻辑留给调用方，函数职责单一，才能灵活复用。
三、核心基础操作
头尾操作是单链表的高频操作，也是理解指针、二级指针的最佳入口。
3.1 头插法（PushFront）
void PushFront(LL** pphead, DaTy x)
{
assert(pphead); // 检查pphead非空（避免传入NULL）
LL* newnode = SLTBuyNode(x);
newnode->next = *pphead; // 新节点指向原表头
*pphead = newnode; // 更新表头为新节点
}
设计思路与实现步骤
- 为什么用二级指针：这是链表第一个核心难点。C 语言函数传参是「值传递」，如果传一级指针LL* head，函数里只能修改节点的内容，不能修改head本身的指向。头插会改变头指针的指向（头节点换成新节点了），所以必须传头指针的地址（也就是二级指针LL**），才能通过解引用修改 main 函数里的head。
- 实现两步法：
- 新节点先接上原链表：newnode->next = *pphead
- 更新表头：*pphead = newnode
- 时间复杂度：O (1)，不需要遍历，是单链表效率最高的插入方式。
3.2 头删法（SLDeleteBack）
void SLDeleteBack(LL** pphead)
{
assert(*pphead && pphead); // 检查表头非空、pphead非空
LL* next = (*pphead)->next; // 保存下一个节点地址
free(*pphead); // 释放表头节点
*pphead = next; // 更新表头为下一个节点
}
设计思路与删除通用法则
- 核心矛盾：不能直接释放头节点 —— 直接 free 之后，后面的所有节点就都找不到了。
- 删除通用法则：先保存要保留的内容，再释放要删除的内容。这个法则适用于所有链表删除操作。
- 实现三步法：
- 先存下第二个节点的地址
- 释放原头节点
- 把第二个节点设为新的头节点
- 边界校验：assert(*pphead)确保链表非空，空链表执行删除属于非法操作，直接断言崩溃，方便定位 bug。
3.3 尾插法（PushBack）
void PushBack(LL **pphead, DaTy x)
{
assert(pphead);
LL *newnode = SLTBuyNode(x);
if (*pphead == NULL) // 空链表：新节点直接作为表头
{
*pphead = newnode;
}
else // 非空链表：遍历到尾节点
{
LL* pcurs = *pphead;
while (pcurs->next) // 遍历到倒数第二个节点（尾节点的next为NULL）
{
pcurs = pcurs->next;
}
pcurs->next = newnode; // 尾节点指向新节点
}
}
设计思路与边界思维
- 为什么要分情况：空链表没有尾节点，如果直接遍历pcurs->next，就是对 NULL 解引用，直接崩溃。所以必须单独处理空链表的情况。
- 边界思考法：写任何链表函数，都先想两种极端情况：空链表、只有一个节点，这两种情况能跑通，多节点一般就不会错。
- 遍历终止条件：这里用pcurs->next != NULL，因为我们要停在「尾节点本身」，而不是尾节点后面，这样才能修改尾节点的 next 指针。
- 时间复杂度：O (n)，必须遍历到尾部，这是单链表的天然缺陷。
3.4 尾删法（SLDeleteBehind）
void SLDeleteBehind(LL** pphead)
{
assert(* pphead && pphead);
if ((*pphead)->next == NULL) // 只有一个节点：释放后表头置NULL
{
free(*pphead);
*pphead = NULL;
}
else // 多个节点：找到尾节点的前驱
{
LL* ptail = *pphead;
LL* prev = *pphead;
while (ptail->next) // 遍历到尾节点
{
prev = ptail; // 保存前驱节点
ptail = ptail->next;
}
prev->next = NULL; // 前驱节点的next置NULL（成为新尾节点）
free(ptail); // 释放原尾节点
ptail = NULL;
}
}
设计思路与前驱思维
- 核心难点：尾删不能只找到尾节点就 free。因为尾节点的前驱节点的 next 还指向这块内存，会变成野指针。
- 前驱思维：单链表没有前驱指针，凡是要修改「前一个节点的指针」，都必须先找到前驱节点。尾删本质是修改倒数第二个节点的 next，所以必须找到倒数第二个节点。
- 双指针遍历法：用prev和ptail两个指针一起往后走，ptail永远比prev快一步，ptail到尾部时，prev刚好停在倒数第二个节点。
- 致命踩坑点：单节点删除时，必须写*pphead = NULL，不能写pphead = NULL—— 后者只是修改了函数形参，不会改变外部的头指针，会留下野指针，这是新手最容易犯的错误。
四、测试代码与运行结果
int main()
{
LL* head = NULL; // 表头指针初始化
printf("========== 1. 尾插 PushBack ==========\\n");
PushBack(&head, 1);
PushBack(&head, 2);
PushBack(&head, 3);
PushBack(&head, 4);
Print(head); // 预期：1->2->3->4->NULL
printf("========== 2. 头插 PushFront ==========\\n");
PushFront(&head, 0);
PushFront(&head, -1);
Print(head); // 预期：-1->0->1->2->3->4->NULL
printf("========== 3. 查找 SLFin ==========\\n");
LL* pos1 = SLFin(head, 2);
if (pos1)
printf("找到元素 2，地址：%p\\n", pos1);
else
printf("未找到元素 2\\n");
LL* pos2 = SLFin(head, 99);
if (pos2)
printf("找到元素 99，地址：%p\\n", pos2);
else
printf("未找到元素 99\\n");
printf("========== 4. 头删 SLDeleteBack ==========\\n");
SLDeleteBack(&head);
Print(head); // 删-1：0->1->2->3->4->NULL
SLDeleteBack(&head);
Print(head); // 删0：1->2->3->4->NULL
SLDestroy(&head);
return 0;
}
运行结果：
========== 1. 尾插 PushBack ==========
1->2->3->4->NULL
========== 2. 头插 PushFront ==========
-1->0->1->2->3->4->NULL
========== 3. 查找 SLFin ==========
找到元素 2，地址：000002207859C290
未找到元素 99
========== 4. 头删 SLDeleteBack ==========
0->1->2->3->4->NULL
1->2->3->4->NULL
五、基础篇通用思考方法总结
后续更新计划
- 下一篇：实际开发中，更多场景基于指定节点的插入 / 删除（比如有序链表插入、删除指定值节点），我将继续完成单链表的功能。
