深入剖析带头循环双向链表的实现与应用

devtools/2025/3/30 14:22:41/

引言

场景描述

想象一个 环形地铁线路（如深圳地铁11号线），这条线路首尾相连，列车可以顺时针或逆时针循环行驶。为了方便管理，地铁系统设置了一个 “虚拟调度中心”（头节点），它不承载乘客，但作为整个环线的逻辑起点和终点，用于监控和协调所有站点的运行。

映射关系
双向循环链表结构地铁环线系统
头节点（不存储数据）虚拟调度中心（无乘客上下车）
数据节点地铁站点（如“沙井站”、“马安山站”）
next 指针顺时针方向的下一个站点
prev 指针逆时针方向的上一个站点
循环结构线路首尾相连，列车可双向循环行驶

一、数据结构定义

typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
} LTNode;
  • 节点结构：
    • data：存储节点数据
    • next：指向下一个节点
    • prev：指向前一个节点
  • 循环特性：
    • 头节点的next指向第一个有效节点
    • 头节点的prev指向最后一个节点
    • 形成闭环结构（头节点自环表示空链表）

二、核心函数实现详解

1. 节点创建函数 LTBuyNode
LTNode* LTBuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc fail！");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode; // 初始自环return newnode;
}

  • 功能：动态分配内存创建新节点。

  • 细节：

    • 数据域初始化为 x。

    • next 和 prev 指针初始指向自身，形成自环结构。

    • 若内存分配失败，程序直接终止（exit(1)）。

2. 链表初始化 LTInit
LTNode* LTInit() {LTNode* phead = LTBuyNode(-1); // 头节点数据为-1return phead;
}

  • 功能：创建带头节点的空链表。

  • 细节：

    • 头节点数据为 -1，next 和 prev 均指向自身。

    • 空链表仅含头节点，逻辑上表示链表为空。

3. 打印链表 LTPrint
void LTPrint(LTNode* phead) {LTNode* pcur = phead->next;while (pcur != phead) {printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}

  • 功能：遍历链表并打印所有数据节点（不打印头节点）。

  • 细节：

    • 从头节点的下一个节点开始遍历，直到回到头节点结束。

    • 输出格式为 1 -> 2 -> 3 -> ...，末尾换行。

4. 尾插法 LTPushBack
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev; // 新节点prev指向原尾节点newnode->next = phead;       // 新节点next指向头节点phead->prev->next = newnode; // 原尾节点的next指向新节点phead->prev = newnode;       // 头节点的prev指向新节点
}

  • 功能：在链表尾部插入新节点。

  • 指针调整步骤：

    1. 新节点的 prev 指向原尾节点。

    2. 新节点的 next 指向头节点。

    3. 原尾节点的 next 指向新节点。

    4. 头节点的 prev 指向新节点。

5. 头插法 LTPushFront
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next; // 新节点next指向原首节点newnode->prev = phead;       // 新节点prev指向头节点phead->next->prev = newnode; // 原首节点的prev指向新节点phead->next = newnode;       // 头节点的next指向新节点
}

  • 功能：在链表头部插入新节点。

  • 指针调整步骤：

    1. 新节点的 next 指向原首节点。

    2. 新节点的 prev 指向头节点。

    3. 原首节点的 prev 指向新节点。

    4. 头节点的 next 指向新节点。

6. 链表判空 LTEmpty
bool LTEmpty(LTNode* phead) {assert(phead);return phead->next == phead; // 仅头节点自环时为空
}

  • 功能：判断链表是否为空。

  • 返回值：

    • true：链表为空（仅头节点存在）。

    • false：链表至少有一个数据节点。

7. 尾删法 LTPopBack
void LTPopBack(LTNode* phead) {assert(!LTEmpty(phead));     // 链表非空才能删除LTNode* del = phead->prev;   // 待删除的尾节点del->prev->next = phead;     // 尾节点前驱的next指向头节点phead->prev = del->prev;     // 头节点的prev指向尾节点前驱free(del);del = NULL;                  // 局部指针置空（不影响外部）
}

  • 功能：删除链表尾节点。

  • 细节：

    • 断言确保链表非空。

    • 调整尾节点前驱的指针，跳过尾节点。

    • 释放尾节点内存，局部指针 del 置空。

8. 头删法 LTPopFront
void LTPopFront(LTNode* phead) {assert(!LTEmpty(phead));LTNode* del = phead->next;   // 待删除的首节点del->next->prev = phead;     // 首节点后继的prev指向头节点phead->next = del->next;     // 头节点的next指向首节点后继free(del);del = NULL;
}

  • 功能：删除链表首节点。

  • 操作步骤：类似尾删法，调整指针后释放内存。

9. 查找节点 LTFind
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {      // 遍历数据节点if (pcur->data == x) return pcur;pcur = pcur->next;}return NULL;                 // 未找到返回NULL
}

  • 功能：查找第一个值为 x 的节点。

  • 返回值：找到返回节点指针，否则返回 NULL。

10. 在指定位置后插入 LTInsert
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;   // 新节点next指向pos的后继newnode->prev = pos;         // 新节点prev指向pospos->next->prev = newnode;   // pos后继的prev指向新节点pos->next = newnode;         // pos的next指向新节点
}

  • 功能：在 pos 节点后插入新节点。

  • 应用场景：结合 LTFind 实现任意位置插入。

11. 在指定位置前插入 LTInsertFront
void LTInsertFront(LTNode* pos, LTDataType x) { assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;         // 新节点next指向posnewnode->prev = pos->prev;   // 新节点prev指向pos的前驱pos->prev->next = newnode;   // pos前驱的next指向新节点pos->prev = newnode;         // pos的prev指向新节点
}

  • 功能：在 pos 节点前插入新节点。

12. 删除指定节点 LTErase
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next; // pos前驱的next指向pos的后继pos->next->prev = pos->prev; // pos后继的prev指向pos的前驱free(pos);pos = NULL; // 局部指针置空（外部指针需手动置空）
}

  • 功能：删除 pos 节点。

  • 注意事项：

    • pos 不能是头节点，否则链表结构被破坏。

    • 调用后，外部指向 pos 的指针变为野指针，需手动置空。

13. 销毁链表 LTDesTroy
void LTDesTroy(LTNode** phead) {LTNode* pcur = (*phead)->next;while (pcur != *phead) {     // 遍历释放所有数据节点LTNode* next = pcur->next;free(pcur);pcur = next;}free(*phead);                // 释放头节点*phead = NULL;               // 头指针置空
}

  • 功能：销毁整个链表，释放所有内存。

  • 设计：

    • 使用二级指针确保外部头指针被置空。

    • 避免内存泄漏和野指针问题。

测试用例解析 test01

void test01() {LTNode* plist = LTInit();            // 初始化空链表LTPushBack(plist, 1);                // 尾插1LTPushBack(plist, 2);                // 尾插2 → 链表: 1 -> 2LTPushBack(plist, 3);                // 尾插3 → 链表: 1 -> 2 -> 3LTPushBack(plist, 4);                // 尾插4 → 链表: 1 -> 2 -> 3 -> 4LTPrint(plist);                      // 输出: 1 -> 2 -> 3 -> 4LTPushFront(plist, 0);               // 头插0 → 链表: 0 -> 1 -> 2 -> 3 -> 4LTPrint(plist);LTPopBack(plist);                    // 尾删4 → 链表: 0 -> 1 -> 2 -> 3LTPrint(plist);LTPopFront(plist);                   // 头删0 → 链表: 1 -> 2 -> 3LTPrint(plist);LTNode* pos = LTFind(plist, 2);      // 查找值为2的节点if (pos) {LTInsert(pos, 5);                // 在2后插入5 → 链表: 1 -> 2 -> 5 -> 3LTPrint(plist);}LTDesTroy(&plist);                   // 销毁链表，plist置NULL
}

  • 验证操作：

    • 初始化、尾插、头插、尾删、头删、查找、指定位置插入、销毁。

    • 通过打印验证每一步操作的正确性

四、关键技术点总结

技术点说明
头节点设计简化边界条件处理，统一头插尾插操作
循环链表特性通过头节点的 prev 指针快速访问尾节点
指针操作技巧插入需修改 4 个指针，删除需修改 2 个指针
内存管理使用LTBuyNode统一分配内存，LTDesTroy彻底释放内存
安全性设计assert参数校验，内存释放后置 NULL

五、典型应用场景

  1. LRU 缓存：
    • 通过头尾指针快速访问最近使用和最久未使用的节点
  2. 双端队列：
    • 支持 O (1) 时间复杂度的头尾操作
  3. 文件系统 inode 管理：
    • 快速定位文件的前后节点
  4. 哈希表冲突处理：
    • 双向链表便于删除操作

六、扩展学习建议

  1. 实现链表逆序操作
  2. 尝试合并两个有序链表
  3. 研究跳表（Skip List）数据结构
  4. 了解 Linux 内核中的链表实现

最后附上全部代码：

代码List.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//双向链表的结构
typedef int LTDataType;
typedef struct  ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//打印链表
void LTPrint(LTNode* phead);//双向链表但初始化
LTNode* LTInit();//销毁数据表
void LTDesTroy(LTNode** phead);
//void LTDataTroy(LTNode* phead); //也可也传一级指针不过，最后得自己NULL一下，// 尾插
void LTPushBack(LTNode* phead, LTDataType x);// 头插
void LTPushFront(LTNode* phead, LTDataType x);//只有一个头结点的情况下，双向链表为空
bool LTEmpty(LTNode* phead);//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//在pos位置之前插入数据
void LTInsertFront(LTNode* pos, LTDataType x);//删除pos位置的结点
void LTErase(LTNode* pos);

代码List.c

#include"List.h"//创建新的结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//判断新结点是否创建成功if (newnode == NULL){perror("malloc fail！");exit(1);}//成功就把值赋上和指针指向newnode->data = x;newnode->next = newnode->prev = newnode;//返回一级指针指向的地址return newnode;
}void LTPrint(LTNode* phead)
{//把头结点的下一个指向的地址赋给新创建的临时指针LTNode* pcur = phead->next;//遍历链表的数据，遍历到头结点结束while (pcur != phead){printf("%d -> ", pcur->data);//把pcur下一个地址赋给自己pcur = pcur->next;}printf("\n");
}LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//断言phead不为空assert(phead);//创建新的结点LTNode* newnode = LTBuyNode(x);//把新的结点prev指向头结点的prevnewnode->prev = phead->prev;//把新的next指向phead的地址newnode->next = phead;//把头结点的prev的结点的next结点指向新的结点phead->prev->next = newnode;//把头结点prev指向新的结点phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//只有一个头结点的情况下，双向链表为空
bool LTEmpty(LTNode* phead)
{assert(phead);//判断 phead->next 是否等于 phead 来确定链表是否为空，若相等则返回 true，表示链表为空；否则返回 false。return phead->next == phead;
}//尾删
void LTPopBack(LTNode* phead)
{//对LTEmpty函数取反assert(!(LTEmpty(phead)));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{//对LTEmpty函数取反assert(!(LTEmpty(phead)));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}
//在pos位置之前插入数据
void LTInsertFront(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;}//删除pos位置的结点
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//销毁数据表
void LTDesTroy(LTNode** phead)
{LTNode* pcur = (*phead)->next;while (pcur != *phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(*phead);*phead = NULL;
}//void LTDataTroy(LTNode* phead)
//{
//    LTNode* pcur = phead->next;
//    while (pcur != phead)
//    {
//        LTNode* next = pcur->next;
//        free(pcur);
//        pcur = next;
//    }
//    free(phead);
//    phead = NULL;
//
//}

代码test.c

#include"List.h"void test01()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPushFront(plist, 0);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* pos = LTFind(plist, 2);if (pos){LTInsert(pos, 5);LTPrint(plist);}LTDesTroy(&plist);
}int main()
{test01();return 0;
}


http://www.ppmy.cn/devtools/171569.html

相关文章

OpenAI放出大招！GPT-4o图像生成功能上线

OpenAI放出大招！GPT-4o图像生成功能上线

3月25日凌晨&#xff0c;OpenAI终于放出了憋了一年的大招——GPT-4o图像生成功能正式上线了&#xff0c;目前正开始在ChatGPT和Sora中向所有Plus、Pro、Team和Free用户推出。 本次升级&#xff0c;除了基本的图像生成能力很强以外&#xff0c;还有些值得一提的特性&#xff1a;…
阅读更多...
详解 WAL 质押奖励

详解 WAL 质押奖励

链上存储与传统的智能合约平台有根本不同的定价结构和商业模型&#xff0c;后者主要专注于执行交易。虽然在高吞吐量区块链中&#xff0c;固定成本占验证节点总体运营成本的很大一部分&#xff0c;但在存储基础设施中&#xff0c;变动成本占据了相当大的比例。增加存储的数据量…
阅读更多...
网络安全可以考取哪些证书？

网络安全可以考取哪些证书？

考证是提升自我的最快捷径之一&#xff0c;虽然证书≠能力&#xff0c;但是有证可是职业晋升和评职称的“敲门砖”。 网络安全行业也有许多证书&#xff0c;你可以针对个人需求考取&#xff1a; 一、国内权威认证 1、CISP CISP&#xff0c;全称是注册信息安全专业人员&…
阅读更多...
VUE项目初始化

VUE项目初始化

node webpack 淘宝镜像 node_modules文件夹:项目依赖文件夹 public文件夹:一般放置一些静态资源(图片)&#xff0c;需要注意&#xff0c;放在public文件夹中的静态资源&#xff0c;webpack进行打包的时候,会原封不动打包到dist文件夹中。 src文件夹(程序员源代码文件夹): ass…
阅读更多...
从零基础到 Java 网站项目开发学习规划​

从零基础到 Java 网站项目开发学习规划​

在数字化时代&#xff0c;Java 凭借其卓越的跨平台性、强大的功能和丰富的类库&#xff0c;成为开发各类网站的主流编程语言。对于想要踏入 Java 网站开发领域的初学者而言&#xff0c;一份系统、科学的学习规划至关重要。它不仅能帮助我们有条不紊地掌握知识和技能&#xff0c…
阅读更多...
鸿蒙第三方解析（一）

鸿蒙第三方解析（一）

鸿蒙官方第三方资源地址&#xff1a;https://ohpm.openharmony.cn/#/cn/result?sortedTypelikes&page1&q 以某一个第三方的主页为示例&#xff1a; popularity和下载量意味着这个控件的稳定性 仓库地址可以下载源码&#xff0c;进行修改。 本系列的目的是分析第三方源…
阅读更多...
蓝桥杯C++基础算法-0-1背包（优化为一维）

蓝桥杯C++基础算法-0-1背包（优化为一维）

这段代码实现了0-1 背包问题的动态规划解法&#xff0c;并且使用了滚动数组来优化空间复杂度。以下是代码的详细思路解析&#xff1a; 1. 问题背景 给定 n 个物品&#xff0c;每个物品有其体积 v[i] 和价值 w[i]&#xff0c;以及一个容量为 m 的背包。目标是选择物品使得总价值…
阅读更多...
深入解析 DeepSpeed 日志：OVERFLOW和Skipping step是什么，mom是什么？

深入解析 DeepSpeed 日志：OVERFLOW和Skipping step是什么，mom是什么？

深入解析 DeepSpeed 日志&#xff1a;理解训练过程中的关键指标 在分布式深度学习训练中&#xff0c;DeepSpeed 是一个广受欢迎的优化工具&#xff0c;尤其是在大模型训练中。它的日志输出包含了大量信息&#xff0c;帮助研究者监控训练过程、诊断问题并优化性能。本文将以一条…
阅读更多...
最新文章

Copyright @ 2022~2023