当前位置: 首页 > news >正文

双向链表详解及实现

双向链表作为链表的重要形式,相比单链表增加了前驱指针,使得节点可以双向遍历,在插入、删除等操作上更加灵活。本文将详细讲解双向链表的结构、实现方法,并与顺序表进行对比分析,帮助大家深入理解双向链表。

1. 双向链表的结构

1.1 结构定义

双向链表中最常用的结构是带头双向循环链表。

  • 带头:这里的 “头” 是 “哨兵位”(头节点),不存储有效数据,仅用于简化边界条件处理。
  • 双向:每个节点包含prev(前驱指针)和next(后继指针),分别指向前后节点。
  • 循环:尾节点的next指向哨兵位,哨兵位的prev指向尾节点,形成闭环。

其结构如下:

1.2 组成结构

链表:由节点组成。

节点:由数据+指向下一个节点的指针+指向前一个节点的指针组成。

1.3 哨兵位的意义

哨兵位(头节点)是双向链表的关键设计,其意义在于:

  • 避免遍历或操作时出现死循环(循环结构中通过哨兵位判断边界)。
  • 简化空链表和非空链表的操作逻辑(无需单独处理头 / 尾节点为NULL的情况)。

注意:此处的 “带头” 与单链表中 “头节点”(第一个有效节点)不同。单链表的 “头节点” 是有效数据的第一个节点,而双向链表的 “哨兵位” 不存储有效数据,仅作为边界标记。

1.4 单链表和双向链表为空时的区别

2. 双向链表的实现

2.1 节点结构定义

首先定义双向链表的节点结构,包含前驱指针、后继指针和数据域:

//定义
typedef int LTDataType; 
// 数据类型typedef struct ListNode {// 存储的数据LTDataType data;// 指向后一个节点struct ListNode* next; // 指向前一个节点struct ListNode* prev;      
} LTNode;

2.2 核心操作实现

双向链表的核心操作包括初始化、销毁、增删查改等,以下是具体实现:

2.2.1 初始化(LTInit)

初始化函数用于创建哨兵位,并构建循环结构:

//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail"); // 内存分配失败exit(1); // 异常退出}node->data = x;node->next = node->prev = node;// 初始化哨兵位:自己指向自己(空链表状态)// 无效数据,仅占位return node;
}//初始化
LTNode* LTInit(LTNode** pphead)
{// 创建哨兵位*pphead = LTBuyNode(-1); 
}

 初始化哨兵位:自己指向自己(空链表状态),自循环。

初始化时,不可以将哨兵位的next 指针以及prev 指针初始化为NULL。

测试一下:

void ListTest01()
{LTNode* plist = NULL;//初始化测试LTInit(&plist);
}
int main()
{return 0;
}

调试:

2.2.2 尾插(LTPushBack)

在链表尾部插入新节点:

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//注意在插入前,要将链表初始化至只有一个头结点的情况assert(phead);// 创建新节点LTNode* newnode = LTBuyNode(x);// 找到尾节点(哨兵位的prev)LTNode* tail = phead->prev;//需要改 头节点phead 尾节点phead->prev 插入节点newnode// newnodenewnode->prev = phead->prev;newnode->next = phead;//phead->nextphead->prev->next = newnode;//pheadphead->prev = newnode;
}

注意在插入前,要将链表初始化至只有一个头结点的情况。 

对比一下:

哨兵位节点不能被删除,节点的地址也不发生变化,所以传一级指针即可: 

 于是进行以下修改:

不可以改变位置。

2.2.3 打印(LTPrint)

打印函数用于输出链表中的有效数据:

//打印
void LTPrint(LTNode* phead) 
{assert(phead);printf("哨兵位 <-> ");LTNode* pcur = phead->next;while (pcur != phead) { // 遍历到哨兵位停止printf("%d <-> ", pcur->data);pcur = pcur->next;}printf("哨兵位\n"); // 打印闭环标志
}

测试一下:

	//打印插入数据(尾插)测试LTPushBack(plist, 1);LTPrint(plist);LTPushBack(plist, 2);LTPrint(plist);LTPushBack(plist, 3);LTPrint(plist);

 

2.2.4 头插(LTPushFront)

在链表头部(哨兵位后)插入新节点:

//头插
void LTPushFront(LTNode* phead, LTDataType x) 
{assert(phead);LTNode* newnode = LTBuyNode(x);// 需要修改phead newnode phead->next// newnodenewnode->next = phead->next;newnode->prev = phead;// phead->nextphead->next->prev = newnode;phead->next = newnode;
}

 这里不可完全交换:

如果要交换,则 phead->next 节点不可以通过哨兵位找,而是 newnode 找。

测试一下:

	//头插测试LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);

http://www.lryc.cn/news/595900.html

相关文章:

  • C++_Hello算法_队列
  • 基于Java+MySQL实现(Web)文件共享管理系统(仿照百度文库)
  • 188粉福
  • Spring快速整合Mybatis
  • 技术与情感交织的一生 (十)
  • nodejs:告别全局安装,npx 命令详解及其与 npm 的区别
  • 从零开始学CTF(第二十五期)
  • Gitlab-CI实现组件自动推送
  • n8n - 为技术团队提供安全的自动化工作流
  • 基于Kubernetes的微服务CI/CD:Jenkins Pipeline全流程实践
  • 知识库搭建之Meilisearch‘s 搜索引擎 测评-东方仙盟测评师
  • STL学习(一、string容器)
  • 暑假算法训练.6
  • 深入浅出Python函数:参数传递、作用域与案例详解
  • 根据数据,判断神经网络所需的最小参数量
  • 设计模式七:抽象工厂模式(Abstract Factory Pattern)
  • 【Linux内核模块】模块声明与描述
  • 【RK3576】【Android14】MIC开发调试
  • 杭州网站建设选哪家?派迪科技项目实力展示
  • Python 正则表达式在数据分析中的应用:实战指南
  • OpenCV基本的图像处理
  • AI助力临床医学科研创新与效率双提升丨临床医学日常工作、论文高效撰写与项目申报、数据分析与可视化、机器学习建模等
  • 深入解析 Pandas:Python 数据分析的强大工具
  • AWE2026启动:加码AI科技,双展区联动开启产业新格局
  • 小玩 Lifecycle
  • ESP32-Cam三脚架机器人:DIY你的智能移动监控平台
  • 单一职责原则(SRP):构建高质量软件的基石
  • 【接口自动化】掌握接口自动化:核心概念讲解(理论知识)
  • Java 大视界 -- Java 大数据在智能医疗医疗设备维护与管理中的应用(358)
  • 阁楼式货架:垂直空间革命下的仓储效率升级方案