C语言单链表学习笔记头插/尾插创建、反转、删除/插入/更新一、学习目标本次学习聚焦C语言单链表的核心基础操作重点掌握单链表节点的结构体定义方式头插法、尾插法两种创建单链表的思路与实现迭代法实现单链表反转单链表指定节点的插入、删除、数据更新操作链表操作中的内存管理malloc/free与内存泄漏规避。二、核心知识点拆解1. 单链表的基础结构定义单链表的核心是节点Node每个节点包含数据域存储数据和指针域指向下一个节点通过typedef简化结构体调用代码定义如下#includestdio.h#includestdlib.htypedefstructNode{intval;// 数据域存储整型数据structNode*next;// 指针域指向链表下一个节点}N;// 重命名结构体为N简化后续使用2. 头插法创建单链表原理头插法是将新节点始终插入到链表的“头部”第一个节点之前新节点的next指向当前链表的头节点再将链表头指针更新为新节点。特点插入效率高无需遍历链表生成的链表顺序与原数据逆序如原数组1-10头插后链表为10→9→…→1。核心代码实现intarr[10]{1,2,3,4,5,6,7,8,9,10};N*linkNULL;// 链表头指针初始化为空inti;for(i0;i10;i){N*x(N*)malloc(sizeof(N));// 为新节点分配内存x-valarr[i];// 赋值x-nextlink;// 新节点指向当前头节点linkx;// 更新头指针为新节点}3. 尾插法创建单链表原理尾插法是将新节点插入到链表的“尾部”需要借助尾指针flag跟踪链表最后一个节点新节点接在尾指针后再更新尾指针为新节点。特点生成的链表顺序与原数据顺序原数组1-10尾插后链表为1→2→…→10需借助“哑节点”哨兵节点简化边界处理避免空链表判断用完需释放哑节点避免内存泄漏。核心代码实现N*link2(N*)malloc(sizeof(N));// 创建哑节点哨兵节点N*flaglink2;// 尾指针初始指向哑节点inti1;for(i10;i110;i1){N*x(N*)malloc(sizeof(N));x-valarr[i1];flag-nextx;// 新节点接在尾指针后flagx;// 更新尾指针为新节点}flag-nextNULL;// 链表最后一个节点的next置空N*flag_oldlink2;// 保存哑节点地址用于后续释放link2link2-next;// 跳过哑节点指向真正的链表头free(flag_old);// 释放哑节点避免内存泄漏4. 迭代法实现链表反转原理通过迭代逐个改变节点的指向核心是“保存当前节点→修改指向→移动指针”最终将原链表的尾节点变为新链表的头节点。核心代码实现N*link1NULL;// 反转后的新链表头指针N*xNULL;while(link2!NULL){xlink2;// 保存当前节点link2link2-next;// 移动原链表指针避免断链x-nextlink1;// 当前节点指向新链表的头节点link1x;// 更新新链表头指针为当前节点}5. 链表操作的内存管理节点创建必须通过malloc分配堆内存栈内存会随函数结束释放导致链表失效内存释放尾插法的哑节点需手动free不再使用的链表节点需释放避免内存泄漏注意释放节点前需确认指针指向避免释放后继续访问野指针问题。6. 单链表的节点删除、插入、更新操作1指定位置插入节点在指定值节点后插入原理遍历链表找到目标节点新建节点的next指向目标节点的下一个节点再将目标节点的next指向新建节点。若目标节点不存在可选择插入到链表尾部或提示错误。核心代码实现// 在值为target的节点后插入新值new_valvoidinsertNode(N*head,inttarget,intnew_val){N*curhead;// 遍历找目标节点while(cur!NULLcur-val!target){curcur-next;}if(curNULL){// 目标节点不存在插入到尾部N*new_node(N*)malloc(sizeof(N));new_node-valnew_val;new_node-nextNULL;// 重新遍历找尾部N*tailhead;while(tail-next!NULL){tailtail-next;}tail-nextnew_node;return;}// 目标节点存在插入新节点N*new_node(N*)malloc(sizeof(N));new_node-valnew_val;new_node-nextcur-next;// 新节点指向目标节点的下一个节点cur-nextnew_node;// 目标节点指向新节点}2指定值删除节点原理遍历链表找到目标节点的前驱节点避免删除后断链将前驱节点的next指向目标节点的下一个节点再释放目标节点的内存。若删除头节点需单独处理更新头指针。核心代码实现// 删除值为target的第一个节点voiddeleteNode(N**head,inttarget){if(*headNULL)return;// 空链表直接返回// 处理头节点是目标节点的情况if((*head)-valtarget){N*temp*head;*head(*head)-next;// 更新头指针free(temp);// 释放原头节点return;}// 找目标节点的前驱节点N*cur*head;while(cur-next!NULLcur-next-val!target){curcur-next;}if(cur-nextNULL)return;// 未找到目标节点// 删除目标节点N*tempcur-next;cur-nextcur-next-next;// 前驱节点指向目标节点的下一个节点free(temp);// 释放目标节点内存}3指定值更新节点数据原理遍历链表找到值为old_val的节点将其数据域修改为new_val可选择更新第一个匹配节点或所有匹配节点。核心代码实现// 更新第一个值为old_val的节点为new_valvoidupdateNode(N*head,intold_val,intnew_val){N*curhead;while(cur!NULL){if(cur-valold_val){cur-valnew_val;// 修改数据域return;// 只更新第一个匹配节点退出}curcur-next;}printf(未找到值为%d的节点\n,old_val);}// 拓展更新所有值为old_val的节点为new_valvoidupdateAllNode(N*head,intold_val,intnew_val){N*curhead;while(cur!NULL){if(cur-valold_val){cur-valnew_val;}curcur-next;}}三、代码整体逻辑梳理本次代码的核心流程定义单链表节点结构体封装view函数遍历打印链表头插法创建链表逆序尾插法创建链表顺序迭代法反转尾插法创建的顺序链表得到逆序链表基于已有链表实现指定位置插入、指定值删除、数据更新操作全程关注malloc/free的使用规避内存泄漏与野指针。四、学习总结头插vs尾插头插效率高但逆序尾插顺序但需处理尾指针和哑节点需根据场景选择链表反转核心迭代法的关键是“先保存下一个节点再修改当前节点指向”避免链表断链内存管理是C语言链表的重点堆内存需手动分配/释放遗漏free会导致内存泄漏错误释放会引发野指针哑节点的价值简化尾插法的边界处理无需判断链表是否为空是链表编程的常用技巧插入/删除操作核心插入需保证“先连后断”避免断链删除需找到前驱节点头节点需单独处理操作后务必释放无用节点内存更新操作核心遍历找到目标节点后直接修改数据域无需调整指针是最简易的链表操作。五、踩坑与解决尾插法忘记将最后节点的next置空会导致遍历链表时出现随机值访问非法内存需手动flag-nextNULL反转链表后直接释放新头指针释放后访问link2link1会触发野指针需确认释放时机头插法初始头指针未置空会导致指针指向随机地址初始必须N* linkNULL删除节点时未找前驱节点直接修改当前节点指针会导致链表断链需先定位前驱节点头节点除外插入节点时“先断后连”先修改目标节点的next再赋值新节点的next会导致后续节点丢失需遵循“先连新节点的next再改目标节点的next”释放节点后未置空指针释放节点内存后指针仍指向原地址野指针释放后需将指针置NULL如tempNULL。
C语言链表练习
C语言单链表学习笔记头插/尾插创建、反转、删除/插入/更新一、学习目标本次学习聚焦C语言单链表的核心基础操作重点掌握单链表节点的结构体定义方式头插法、尾插法两种创建单链表的思路与实现迭代法实现单链表反转单链表指定节点的插入、删除、数据更新操作链表操作中的内存管理malloc/free与内存泄漏规避。二、核心知识点拆解1. 单链表的基础结构定义单链表的核心是节点Node每个节点包含数据域存储数据和指针域指向下一个节点通过typedef简化结构体调用代码定义如下#includestdio.h#includestdlib.htypedefstructNode{intval;// 数据域存储整型数据structNode*next;// 指针域指向链表下一个节点}N;// 重命名结构体为N简化后续使用2. 头插法创建单链表原理头插法是将新节点始终插入到链表的“头部”第一个节点之前新节点的next指向当前链表的头节点再将链表头指针更新为新节点。特点插入效率高无需遍历链表生成的链表顺序与原数据逆序如原数组1-10头插后链表为10→9→…→1。核心代码实现intarr[10]{1,2,3,4,5,6,7,8,9,10};N*linkNULL;// 链表头指针初始化为空inti;for(i0;i10;i){N*x(N*)malloc(sizeof(N));// 为新节点分配内存x-valarr[i];// 赋值x-nextlink;// 新节点指向当前头节点linkx;// 更新头指针为新节点}3. 尾插法创建单链表原理尾插法是将新节点插入到链表的“尾部”需要借助尾指针flag跟踪链表最后一个节点新节点接在尾指针后再更新尾指针为新节点。特点生成的链表顺序与原数据顺序原数组1-10尾插后链表为1→2→…→10需借助“哑节点”哨兵节点简化边界处理避免空链表判断用完需释放哑节点避免内存泄漏。核心代码实现N*link2(N*)malloc(sizeof(N));// 创建哑节点哨兵节点N*flaglink2;// 尾指针初始指向哑节点inti1;for(i10;i110;i1){N*x(N*)malloc(sizeof(N));x-valarr[i1];flag-nextx;// 新节点接在尾指针后flagx;// 更新尾指针为新节点}flag-nextNULL;// 链表最后一个节点的next置空N*flag_oldlink2;// 保存哑节点地址用于后续释放link2link2-next;// 跳过哑节点指向真正的链表头free(flag_old);// 释放哑节点避免内存泄漏4. 迭代法实现链表反转原理通过迭代逐个改变节点的指向核心是“保存当前节点→修改指向→移动指针”最终将原链表的尾节点变为新链表的头节点。核心代码实现N*link1NULL;// 反转后的新链表头指针N*xNULL;while(link2!NULL){xlink2;// 保存当前节点link2link2-next;// 移动原链表指针避免断链x-nextlink1;// 当前节点指向新链表的头节点link1x;// 更新新链表头指针为当前节点}5. 链表操作的内存管理节点创建必须通过malloc分配堆内存栈内存会随函数结束释放导致链表失效内存释放尾插法的哑节点需手动free不再使用的链表节点需释放避免内存泄漏注意释放节点前需确认指针指向避免释放后继续访问野指针问题。6. 单链表的节点删除、插入、更新操作1指定位置插入节点在指定值节点后插入原理遍历链表找到目标节点新建节点的next指向目标节点的下一个节点再将目标节点的next指向新建节点。若目标节点不存在可选择插入到链表尾部或提示错误。核心代码实现// 在值为target的节点后插入新值new_valvoidinsertNode(N*head,inttarget,intnew_val){N*curhead;// 遍历找目标节点while(cur!NULLcur-val!target){curcur-next;}if(curNULL){// 目标节点不存在插入到尾部N*new_node(N*)malloc(sizeof(N));new_node-valnew_val;new_node-nextNULL;// 重新遍历找尾部N*tailhead;while(tail-next!NULL){tailtail-next;}tail-nextnew_node;return;}// 目标节点存在插入新节点N*new_node(N*)malloc(sizeof(N));new_node-valnew_val;new_node-nextcur-next;// 新节点指向目标节点的下一个节点cur-nextnew_node;// 目标节点指向新节点}2指定值删除节点原理遍历链表找到目标节点的前驱节点避免删除后断链将前驱节点的next指向目标节点的下一个节点再释放目标节点的内存。若删除头节点需单独处理更新头指针。核心代码实现// 删除值为target的第一个节点voiddeleteNode(N**head,inttarget){if(*headNULL)return;// 空链表直接返回// 处理头节点是目标节点的情况if((*head)-valtarget){N*temp*head;*head(*head)-next;// 更新头指针free(temp);// 释放原头节点return;}// 找目标节点的前驱节点N*cur*head;while(cur-next!NULLcur-next-val!target){curcur-next;}if(cur-nextNULL)return;// 未找到目标节点// 删除目标节点N*tempcur-next;cur-nextcur-next-next;// 前驱节点指向目标节点的下一个节点free(temp);// 释放目标节点内存}3指定值更新节点数据原理遍历链表找到值为old_val的节点将其数据域修改为new_val可选择更新第一个匹配节点或所有匹配节点。核心代码实现// 更新第一个值为old_val的节点为new_valvoidupdateNode(N*head,intold_val,intnew_val){N*curhead;while(cur!NULL){if(cur-valold_val){cur-valnew_val;// 修改数据域return;// 只更新第一个匹配节点退出}curcur-next;}printf(未找到值为%d的节点\n,old_val);}// 拓展更新所有值为old_val的节点为new_valvoidupdateAllNode(N*head,intold_val,intnew_val){N*curhead;while(cur!NULL){if(cur-valold_val){cur-valnew_val;}curcur-next;}}三、代码整体逻辑梳理本次代码的核心流程定义单链表节点结构体封装view函数遍历打印链表头插法创建链表逆序尾插法创建链表顺序迭代法反转尾插法创建的顺序链表得到逆序链表基于已有链表实现指定位置插入、指定值删除、数据更新操作全程关注malloc/free的使用规避内存泄漏与野指针。四、学习总结头插vs尾插头插效率高但逆序尾插顺序但需处理尾指针和哑节点需根据场景选择链表反转核心迭代法的关键是“先保存下一个节点再修改当前节点指向”避免链表断链内存管理是C语言链表的重点堆内存需手动分配/释放遗漏free会导致内存泄漏错误释放会引发野指针哑节点的价值简化尾插法的边界处理无需判断链表是否为空是链表编程的常用技巧插入/删除操作核心插入需保证“先连后断”避免断链删除需找到前驱节点头节点需单独处理操作后务必释放无用节点内存更新操作核心遍历找到目标节点后直接修改数据域无需调整指针是最简易的链表操作。五、踩坑与解决尾插法忘记将最后节点的next置空会导致遍历链表时出现随机值访问非法内存需手动flag-nextNULL反转链表后直接释放新头指针释放后访问link2link1会触发野指针需确认释放时机头插法初始头指针未置空会导致指针指向随机地址初始必须N* linkNULL删除节点时未找前驱节点直接修改当前节点指针会导致链表断链需先定位前驱节点头节点除外插入节点时“先断后连”先修改目标节点的next再赋值新节点的next会导致后续节点丢失需遵循“先连新节点的next再改目标节点的next”释放节点后未置空指针释放节点内存后指针仍指向原地址野指针释放后需将指针置NULL如tempNULL。
