在各类链表结构中单链表与带头双向循环链表是最具代表性的两种。深入剖析并掌握这两种核心结构便能触类旁通轻松推导并实现其他衍生类型。基于此本文将重点对双链表即带头双向循环链表展开详细解析。首先将结点类型和结点数据重命名typedef int itndate; typedef struct itnode { itndate val; struct itnode* prev; struct itnode* next; }itn;接下来进行节点的创建与初始化。由于双链表采用带头结构其哨兵节点可作为链表的固定操作入口因此无需像单链表那样传递二级指针来修改头指针的指向。我们只需动态创建一个节点作为哨兵位并使其前驱与后继指针均指向自身即可完成链表的初始化。1. 思路在堆区动态分配一个节点并将其前后指针指向自身构建一个最小的带头双向循环链表自环。2. 参数无。3. 返回值itnode*指向新创建并初始化完成的哨兵节点指针。4. 核心逻辑实现申请内存使用malloc为节点分配内存。初始化自环将prev和next指针均指向节点自身。返回指针将节点地址返回给调用方。5. 代码itnode* buynode() { itnode* phead (itnode*)malloc(sizeof(itnode)); assert(phead); phead-prev phead; phead-next phead; return phead; }再来分装打印函数1. 思路利用带头双向循环链表的“自环”特性将“当前节点的下一个节点是否为头节点”作为遍历的终止条件依次访问并输出有效数据节点。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现循环遍历当phead-next ! phead时说明还未绕回哨兵节点继续遍历。输出数据打印当前节点的值。指针后移将指针移动到下一个节点。换行遍历结束后打印换行符。5. 代码void print(itnode* phead) { assert(phead); while (phead-next ! phead) { printf(%d , phead-val); phead phead-next; } printf(\n); }好那么开始进行增删查改的接口的编写尾插1. 思路在带头双向循环链表中尾插操作本质上是在“哨兵节点头节点”与“当前尾节点即头节点的前驱节点”之间插入新节点。通过调整这四个节点的前后指针指向即可将新节点无缝接入链表尾部。2. 参数itnode* phead指向链表哨兵节点头节点的指针、新结点存储的数值。3. 返回值无void。4. 核心逻辑实现创建新节点调用buynode()动态分配并初始化新节点。设置新节点指针将新节点的prev指向原尾节点phead-prevnext指向头节点phead。更新原尾节点指针将原尾节点的next指向新节点。更新头节点指针将头节点的prev指向新节点使其成为新的尾节点。5. 代码void push_back(itnode* phead, itndate val) { assert(phead); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val val; // 2. 将新节点接入链表尾部 newnode-prev phead-prev; newnode-next phead; // 3. 更新原尾节点和头节点的指针 phead-prev-next newnode; phead-prev newnode; }头插1. 思路在带头双向循环链表中头插操作是在“哨兵节点头节点”与“当前第一个有效节点即头节点的后继节点”之间插入新节点。通过调整这四个节点的前后指针指向将新节点无缝接入链表头部。2. 参数itnode* phead指向链表哨兵节点头节点的指针。itndate x待插入节点的数据值。3. 返回值无void。4. 核心逻辑实现创建新节点调用buynode()动态分配并初始化新节点并将传入的数据x赋值给新节点。设置新节点指针将新节点的prev指向头节点pheadnext指向原首节点phead-next。更新原首节点指针将原首节点的prev指向新节点。更新头节点指针将头节点的next指向新节点使其成为新的首节点。5. 代码void push_front(itnode* phead, itndata x) { assert(phead); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val x; // 2. 将新节点接入链表头部 newnode-prev phead; newnode-next phead-next; // 3. 更新原首节点和头节点的指针 phead-next-prev newnode; phead-next newnode; }尾删1. 思路在带头双向循环链表中尾删操作需要摘除“当前尾节点即头节点的前驱节点”。通过调整头节点与新的尾节点之间的指针指向将原尾节点从链表中剥离最后释放其占用的堆区内存。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现定位待删节点通过phead-prev找到当前的尾节点并用临时指针del记录其地址。断开尾节点连接将头节点的prev指向原尾节点的前驱节点即新的尾节点。建立新循环将新的尾节点的next指针重新指向头节点维持循环结构。释放内存调用free释放原尾节点占用的内存并将临时指针置为NULL防止悬空指针。5. 代码补充说明若链表为空时调用尾删会导致哨兵节点被错误释放。应在代码中补充该防御性判断。void pop_back(itnode* phead) { assert(phead); // 1. 边界检查如果链表为空头节点自环则无需删除直接返回 if (phead-next phead) { return; } // 2. 定位待删除的尾节点 itnode* del phead-prev; // 3. 重新连接头节点与新的尾节点 phead-prev del-prev; del-prev-next phead; // 4. 释放原尾节点内存并将指针置空 free(del); del NULL; }头删 1. 思路在带头双向循环链表中头删操作需要摘除“当前首节点即头节点的后继节点”。通过调整头节点与新的首节点之间的指针指向将原首节点从链表中剥离最后释放其占用的堆区内存。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现边界检查判断链表是否为空即phead-next phead若为空则直接返回防止非法操作。定位待删节点通过phead-next找到当前的首节点并用临时指针del记录其地址。断开首节点连接将头节点的next指向原首节点的后继节点即新的首节点。建立新循环将新的首节点的prev指针重新指向头节点维持循环结构。释放内存调用free释放原首节点占用的内存并将临时指针置为NULL防止悬空指针。5. 代码void pop_front(itnode* phead) { // 1. 边界检查如果链表为空头节点自环则无需删除直接返回 if (phead-next phead) { return; } // 2. 定位待删除的首节点 itnode* del phead-next; // 3. 重新连接头节点与新的首节点 phead-next del-next; del-next-prev phead; // 4. 释放原首节点内存并将指针置空 free(del); del NULL; }find查找数据1. 思路在带头双向循环链表中查找操作需从哨兵节点的后继节点即第一个有效节点开始依次遍历。由于是循环结构遍历的终止条件应为“当前节点回到哨兵节点”而非单链表中的NULL。若遍历过程中找到目标值则直接返回该节点的指针若绕回哨兵节点仍未找到则返回NULL。2. 参数itnode* phead指向链表哨兵节点头节点的指针。itndate x待查找的目标数据值。3. 返回值itnode*若找到目标数据返回指向该节点的指针若未找到返回NULL。4. 核心逻辑实现边界断言使用assert确保传入的哨兵节点指针不为空。遍历链表将指针移动至phead-next在当前节点 ! phead的条件下进行循环。数据比对在循环中判断当前节点的val是否等于目标值x若相等则立即返回当前节点的指针。指针后移若当前节点不匹配则将指针向后移动。返回未找到若循环正常结束即已遍历完所有有效节点返回NULL。5. 代码。itnode* find(itnode* phead, itdata x) { assert(phead); // 从第一个有效节点开始遍历直到绕回哨兵节点为止 itnode* cur phead-next; while (cur ! phead) { if (cur-val x) { return cur; } cur cur-next; } return NULL; }指定位置删除1. 思路在带头双向循环链表中删除指定位置节点的操作本质上是将其从链表中“摘除”。通过修改该节点的前驱和后继节点的指针使它们互相指向从而将目标节点从双向链表中剥离最后释放该节点占用的堆区内存。2. 参数itnode* pos指向待删除节点的指针。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的待删除节点指针不为空。断开前驱连接将待删除节点的前驱节点的next指针指向待删除节点的后继节点。断开后继连接将待删除节点的后继节点的prev指针指向待删除节点的前驱节点。释放内存调用free释放待删除节点占用的内存并将临时指针置为NULL防止悬空指针。5. 代码void delect(itnode* pos) { assert(pos); // 1. 将 pos 从链表中摘除 pos-prev-next pos-next; pos-next-prev pos-prev; // 2. 释放节点内存并将指针置空 free(pos); pos NULL; }指定位置之前插入:1. 思路在带头双向循环链表中在指定节点pos之前插入新节点。该操作本质上是修改四个节点的指针指向将新节点无缝接入pos的前驱节点与pos之间。2. 参数itnode* pos指定插入位置的节点指针新节点将插入到该节点之前。itndate x待插入节点的数据值注原代码类型名itndate存在拼写错误已修正为itdata。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的指定位置节点指针不为空。创建新节点调用buynode()动态分配并初始化新节点并将传入的数据x赋值给新节点。设置新节点指针将新节点的next指向posprev指向pos的前驱节点。更新前后节点指针将pos的前驱节点的next指向新节点并将pos的prev指向新节点完成链表的重新链接。5. 代码void insert_front(itnode* pos, itndata x) { assert(pos); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val x; // 2. 将新节点接入 pos 之前 newnode-next pos; newnode-prev pos-prev; // 3. 更新 pos 的前驱节点和 pos 本身的指针 pos-prev-next newnode; pos-prev newnode; }指定位置之后插入:1. 思路在带头双向循环链表中在指定节点pos之后插入新节点。该操作本质上是修改四个节点的指针指向将新节点无缝接入pos与pos的后继节点之间。2. 参数itnode* pos指定插入位置的节点指针新节点将插入到该节点之后。itndate x待插入节点的数据值注原代码类型名itndate存在拼写错误已修正为itdata。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的指定位置节点指针不为空。创建新节点调用buynode()动态分配并初始化新节点并将传入的数据x赋值给新节点。设置新节点指针将新节点的next指向pos的后继节点prev指向pos。更新前后节点指针将pos的后继节点的prev指向新节点并将pos的next指向新节点完成链表的重新链接。5. 代码void insert_back(itnode* pos, itndata x) { assert(pos); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val x; // 2. 将新节点接入 pos 之后 newnode-next pos-next; newnode-prev pos; // 3. 更新 pos 的后继节点和 pos 本身的指针 pos-next-prev newnode; pos-next newnode; }销毁链表destroy:1. 思路销毁带头双向循环链表需要释放链表中所有的节点内存。首先通过循环遍历逐个摘除并释放有效数据节点当所有有效节点释放完毕后链表将退化为仅有哨兵节点头节点自环的状态最后释放哨兵节点本身完成整个链表的销毁。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的头节点指针不为空。循环释放有效节点当phead-next ! phead时说明链表中仍有有效数据节点。在循环中定位当前首节点pcur及其后继节点next将头节点的next指向next完成摘除随后释放pcur的内存。释放哨兵节点当循环结束时所有有效节点已被清空最后释放哨兵节点phead的内存。5. 代码void destroy(itnode* phead) { assert(phead); // 1. 循环遍历逐个摘除并释放有效数据节点 while (phead-next ! phead) { itnode* pcur phead-next; itnode* next pcur-next; phead-next next; free(pcur); pcur NULL; } // 2. 释放哨兵节点头节点本身 free(phead); phead NULL; }OK 那么到这里链表的学习先告一段落 写在最后代码写完了但我想对正在阅读这篇博客的你说几句心里话。最近身边有很多同学在迷茫、害怕大体原因是只能靠自己一个人在这个世界打拼无依无靠而世界又在不断变化进步不知道自己的出路在哪里。我把送给他们的话也送给正在屏幕前努力的你保持乐观悲观者正确乐观者前行。相信时间的力量就不必问何时才有回报。拥有坚持的毅力就不必在意暂时的苟且。保持每天的进步就不必对未来感到迷茫。愿你在代码的世界里披荆斩棘也在人生的道路上步履不停。
在各类链表结构中单链表与带头双向循环链表是最具代表性的两种。深入剖析并掌握这两种核心结构便能触类旁通轻松推导并实现其他衍生类型。基于此本文将重点对双链表即带头双向循环链表展开详细解析。首先将结点类型和结点数据重命名typedef int itndate; typedef struct itnode { itndate val; struct itnode* prev; struct itnode* next; }itn;接下来进行节点的创建与初始化。由于双链表采用带头结构其哨兵节点可作为链表的固定操作入口因此无需像单链表那样传递二级指针来修改头指针的指向。我们只需动态创建一个节点作为哨兵位并使其前驱与后继指针均指向自身即可完成链表的初始化。1. 思路在堆区动态分配一个节点并将其前后指针指向自身构建一个最小的带头双向循环链表自环。2. 参数无。3. 返回值itnode*指向新创建并初始化完成的哨兵节点指针。4. 核心逻辑实现申请内存使用malloc为节点分配内存。初始化自环将prev和next指针均指向节点自身。返回指针将节点地址返回给调用方。5. 代码itnode* buynode() { itnode* phead (itnode*)malloc(sizeof(itnode)); assert(phead); phead-prev phead; phead-next phead; return phead; }再来分装打印函数1. 思路利用带头双向循环链表的“自环”特性将“当前节点的下一个节点是否为头节点”作为遍历的终止条件依次访问并输出有效数据节点。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现循环遍历当phead-next ! phead时说明还未绕回哨兵节点继续遍历。输出数据打印当前节点的值。指针后移将指针移动到下一个节点。换行遍历结束后打印换行符。5. 代码void print(itnode* phead) { assert(phead); while (phead-next ! phead) { printf(%d , phead-val); phead phead-next; } printf(\n); }好那么开始进行增删查改的接口的编写尾插1. 思路在带头双向循环链表中尾插操作本质上是在“哨兵节点头节点”与“当前尾节点即头节点的前驱节点”之间插入新节点。通过调整这四个节点的前后指针指向即可将新节点无缝接入链表尾部。2. 参数itnode* phead指向链表哨兵节点头节点的指针、新结点存储的数值。3. 返回值无void。4. 核心逻辑实现创建新节点调用buynode()动态分配并初始化新节点。设置新节点指针将新节点的prev指向原尾节点phead-prevnext指向头节点phead。更新原尾节点指针将原尾节点的next指向新节点。更新头节点指针将头节点的prev指向新节点使其成为新的尾节点。5. 代码void push_back(itnode* phead, itndate val) { assert(phead); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val val; // 2. 将新节点接入链表尾部 newnode-prev phead-prev; newnode-next phead; // 3. 更新原尾节点和头节点的指针 phead-prev-next newnode; phead-prev newnode; }头插1. 思路在带头双向循环链表中头插操作是在“哨兵节点头节点”与“当前第一个有效节点即头节点的后继节点”之间插入新节点。通过调整这四个节点的前后指针指向将新节点无缝接入链表头部。2. 参数itnode* phead指向链表哨兵节点头节点的指针。itndate x待插入节点的数据值。3. 返回值无void。4. 核心逻辑实现创建新节点调用buynode()动态分配并初始化新节点并将传入的数据x赋值给新节点。设置新节点指针将新节点的prev指向头节点pheadnext指向原首节点phead-next。更新原首节点指针将原首节点的prev指向新节点。更新头节点指针将头节点的next指向新节点使其成为新的首节点。5. 代码void push_front(itnode* phead, itndata x) { assert(phead); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val x; // 2. 将新节点接入链表头部 newnode-prev phead; newnode-next phead-next; // 3. 更新原首节点和头节点的指针 phead-next-prev newnode; phead-next newnode; }尾删1. 思路在带头双向循环链表中尾删操作需要摘除“当前尾节点即头节点的前驱节点”。通过调整头节点与新的尾节点之间的指针指向将原尾节点从链表中剥离最后释放其占用的堆区内存。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现定位待删节点通过phead-prev找到当前的尾节点并用临时指针del记录其地址。断开尾节点连接将头节点的prev指向原尾节点的前驱节点即新的尾节点。建立新循环将新的尾节点的next指针重新指向头节点维持循环结构。释放内存调用free释放原尾节点占用的内存并将临时指针置为NULL防止悬空指针。5. 代码补充说明若链表为空时调用尾删会导致哨兵节点被错误释放。应在代码中补充该防御性判断。void pop_back(itnode* phead) { assert(phead); // 1. 边界检查如果链表为空头节点自环则无需删除直接返回 if (phead-next phead) { return; } // 2. 定位待删除的尾节点 itnode* del phead-prev; // 3. 重新连接头节点与新的尾节点 phead-prev del-prev; del-prev-next phead; // 4. 释放原尾节点内存并将指针置空 free(del); del NULL; }头删 1. 思路在带头双向循环链表中头删操作需要摘除“当前首节点即头节点的后继节点”。通过调整头节点与新的首节点之间的指针指向将原首节点从链表中剥离最后释放其占用的堆区内存。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现边界检查判断链表是否为空即phead-next phead若为空则直接返回防止非法操作。定位待删节点通过phead-next找到当前的首节点并用临时指针del记录其地址。断开首节点连接将头节点的next指向原首节点的后继节点即新的首节点。建立新循环将新的首节点的prev指针重新指向头节点维持循环结构。释放内存调用free释放原首节点占用的内存并将临时指针置为NULL防止悬空指针。5. 代码void pop_front(itnode* phead) { // 1. 边界检查如果链表为空头节点自环则无需删除直接返回 if (phead-next phead) { return; } // 2. 定位待删除的首节点 itnode* del phead-next; // 3. 重新连接头节点与新的首节点 phead-next del-next; del-next-prev phead; // 4. 释放原首节点内存并将指针置空 free(del); del NULL; }find查找数据1. 思路在带头双向循环链表中查找操作需从哨兵节点的后继节点即第一个有效节点开始依次遍历。由于是循环结构遍历的终止条件应为“当前节点回到哨兵节点”而非单链表中的NULL。若遍历过程中找到目标值则直接返回该节点的指针若绕回哨兵节点仍未找到则返回NULL。2. 参数itnode* phead指向链表哨兵节点头节点的指针。itndate x待查找的目标数据值。3. 返回值itnode*若找到目标数据返回指向该节点的指针若未找到返回NULL。4. 核心逻辑实现边界断言使用assert确保传入的哨兵节点指针不为空。遍历链表将指针移动至phead-next在当前节点 ! phead的条件下进行循环。数据比对在循环中判断当前节点的val是否等于目标值x若相等则立即返回当前节点的指针。指针后移若当前节点不匹配则将指针向后移动。返回未找到若循环正常结束即已遍历完所有有效节点返回NULL。5. 代码。itnode* find(itnode* phead, itdata x) { assert(phead); // 从第一个有效节点开始遍历直到绕回哨兵节点为止 itnode* cur phead-next; while (cur ! phead) { if (cur-val x) { return cur; } cur cur-next; } return NULL; }指定位置删除1. 思路在带头双向循环链表中删除指定位置节点的操作本质上是将其从链表中“摘除”。通过修改该节点的前驱和后继节点的指针使它们互相指向从而将目标节点从双向链表中剥离最后释放该节点占用的堆区内存。2. 参数itnode* pos指向待删除节点的指针。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的待删除节点指针不为空。断开前驱连接将待删除节点的前驱节点的next指针指向待删除节点的后继节点。断开后继连接将待删除节点的后继节点的prev指针指向待删除节点的前驱节点。释放内存调用free释放待删除节点占用的内存并将临时指针置为NULL防止悬空指针。5. 代码void delect(itnode* pos) { assert(pos); // 1. 将 pos 从链表中摘除 pos-prev-next pos-next; pos-next-prev pos-prev; // 2. 释放节点内存并将指针置空 free(pos); pos NULL; }指定位置之前插入:1. 思路在带头双向循环链表中在指定节点pos之前插入新节点。该操作本质上是修改四个节点的指针指向将新节点无缝接入pos的前驱节点与pos之间。2. 参数itnode* pos指定插入位置的节点指针新节点将插入到该节点之前。itndate x待插入节点的数据值注原代码类型名itndate存在拼写错误已修正为itdata。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的指定位置节点指针不为空。创建新节点调用buynode()动态分配并初始化新节点并将传入的数据x赋值给新节点。设置新节点指针将新节点的next指向posprev指向pos的前驱节点。更新前后节点指针将pos的前驱节点的next指向新节点并将pos的prev指向新节点完成链表的重新链接。5. 代码void insert_front(itnode* pos, itndata x) { assert(pos); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val x; // 2. 将新节点接入 pos 之前 newnode-next pos; newnode-prev pos-prev; // 3. 更新 pos 的前驱节点和 pos 本身的指针 pos-prev-next newnode; pos-prev newnode; }指定位置之后插入:1. 思路在带头双向循环链表中在指定节点pos之后插入新节点。该操作本质上是修改四个节点的指针指向将新节点无缝接入pos与pos的后继节点之间。2. 参数itnode* pos指定插入位置的节点指针新节点将插入到该节点之后。itndate x待插入节点的数据值注原代码类型名itndate存在拼写错误已修正为itdata。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的指定位置节点指针不为空。创建新节点调用buynode()动态分配并初始化新节点并将传入的数据x赋值给新节点。设置新节点指针将新节点的next指向pos的后继节点prev指向pos。更新前后节点指针将pos的后继节点的prev指向新节点并将pos的next指向新节点完成链表的重新链接。5. 代码void insert_back(itnode* pos, itndata x) { assert(pos); // 1. 创建新节点并赋值 itnode* newnode buynode(); newnode-val x; // 2. 将新节点接入 pos 之后 newnode-next pos-next; newnode-prev pos; // 3. 更新 pos 的后继节点和 pos 本身的指针 pos-next-prev newnode; pos-next newnode; }销毁链表destroy:1. 思路销毁带头双向循环链表需要释放链表中所有的节点内存。首先通过循环遍历逐个摘除并释放有效数据节点当所有有效节点释放完毕后链表将退化为仅有哨兵节点头节点自环的状态最后释放哨兵节点本身完成整个链表的销毁。2. 参数itnode* phead指向链表哨兵节点头节点的指针。3. 返回值无void。4. 核心逻辑实现边界断言使用assert确保传入的头节点指针不为空。循环释放有效节点当phead-next ! phead时说明链表中仍有有效数据节点。在循环中定位当前首节点pcur及其后继节点next将头节点的next指向next完成摘除随后释放pcur的内存。释放哨兵节点当循环结束时所有有效节点已被清空最后释放哨兵节点phead的内存。5. 代码void destroy(itnode* phead) { assert(phead); // 1. 循环遍历逐个摘除并释放有效数据节点 while (phead-next ! phead) { itnode* pcur phead-next; itnode* next pcur-next; phead-next next; free(pcur); pcur NULL; } // 2. 释放哨兵节点头节点本身 free(phead); phead NULL; }OK 那么到这里链表的学习先告一段落 写在最后代码写完了但我想对正在阅读这篇博客的你说几句心里话。最近身边有很多同学在迷茫、害怕大体原因是只能靠自己一个人在这个世界打拼无依无靠而世界又在不断变化进步不知道自己的出路在哪里。我把送给他们的话也送给正在屏幕前努力的你保持乐观悲观者正确乐观者前行。相信时间的力量就不必问何时才有回报。拥有坚持的毅力就不必在意暂时的苟且。保持每天的进步就不必对未来感到迷茫。愿你在代码的世界里披荆斩棘也在人生的道路上步履不停。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
