数据结构 - 单链表第一篇：单链表基础操作

【C 语言数据结构】单链表基础操作详解头插 / 尾插 / 头删 / 尾删 / 查找前言单链表是 C 语言数据结构中最基础也最核心的线性表结构之一相比顺序表单链表的内存布局更灵活无需连续内存空间增删操作非头尾效率更高。本文将从设计思路、实现步骤、踩坑点三个维度拆解单链表基础操作的完整思考过程不仅告诉你代码怎么写更讲清楚为什么这么写以及写链表代码的通用思考方法。一、单链表的结构体定义#pragma once #includestdio.h #includestdlib.h #includeassert.h // 数据类型重定义方便后续修改比如改成char/long等 typedef int DaTy; // 单链表节点结构体 typedef struct LinkList { DaTy a; // 节点存储的数据 struct LinkList* next; // 指向下一个节点的指针 }LL; // 重命名为LL简化后续使用设计思路与方法结构设计逻辑单链表的核心是「节点串联」每个节点只需要两部分数据域存数据指针域存下一个节点的地址。和顺序表用数组连续存储不同链表节点在内存中是分散的靠指针维系逻辑上的连续。类型重命名的工程意义用DaTy封装数据类型后续想存字符、结构体、指针只改一行即可无需全局替换这是数据结构「通用性设计」的基础思维。结构体自引用注意指针域必须写struct LinkList* next不能直接写LL* next—— 因为LL是 typedef 的别名结构体内部定义时别名还未生效这是 C 语言语法的硬性规则。二、核心辅助函数辅助函数是链表操作的「地基」所有增删查改都依赖它们写好辅助函数能大幅减少重复代码和出错概率。2.1 创建新节点SLTBuyNodeLL* 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 打印链表Printvoid 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 查找节点SLFinLL* SLFin(LL* phead, DaTy x) { LL* pcur phead; while (pcur) { if (pcur-a x) // 找到目标值返回节点地址 { return pcur; } pcur pcur-next; } return NULL; // 遍历完未找到返回NULL }设计思路与方法功能定位查找是插入、删除的前置操作。单链表没有下标想在某个值前后插入 / 删除必须先按值找到节点地址这是链表「按值操作」的必经之路。模板复用思想代码框架和打印函数完全一致只是把「打印」换成了「数值比较 返回」。学会复用遍历模板写链表代码速度会大幅提升。接口设计原则查找只返回节点地址不打印、不修改。把打印逻辑留给调用方函数职责单一才能灵活复用。三、核心基础操作头尾操作是单链表的高频操作也是理解指针、二级指针的最佳入口。3.1 头插法PushFrontvoid 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 头删法SLDeleteBackvoid SLDeleteBack(LL** pphead) { assert(*pphead pphead); // 检查表头非空、pphead非空 LL* next (*pphead)-next; // 保存下一个节点地址 free(*pphead); // 释放表头节点 *pphead next; // 更新表头为下一个节点 }设计思路与删除通用法则核心矛盾不能直接释放头节点 —— 直接 free 之后后面的所有节点就都找不到了。删除通用法则先保存要保留的内容再释放要删除的内容。这个法则适用于所有链表删除操作。实现三步法先存下第二个节点的地址释放原头节点把第二个节点设为新的头节点边界校验assert(*pphead)确保链表非空空链表执行删除属于非法操作直接断言崩溃方便定位 bug。3.3 尾插法PushBackvoid 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 尾删法SLDeleteBehindvoid 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); // 删-10-1-2-3-4-NULL SLDeleteBack(head); Print(head); // 删01-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五、基础篇通用思考方法总结二级指针判断法则函数会不会修改头指针的指向会 → 用二级指针不会 → 用一级指针。遍历不动头所有遍历操作都用临时指针绝不直接修改传入的头指针否则链表会丢失。删除先保留释放节点前一定先保存好后续节点的地址防止断链。边界优先法写函数先考虑空链表、单节点两种边界再处理多节点的一般情况。断言防护所有指针解引用前用assert判空出问题直接定位比程序莫名崩溃好调试百倍。后续更新计划下一篇实际开发中更多场景基于指定节点的插入 / 删除比如有序链表插入、删除指定值节点我将继续完成单链表的功能。