【数据结构】双向带头循环链表的实现

前言：在前面我们学习了顺序表、单向链表，今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！
在这里插入图片描述

双向链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表(如下图所示)。通常我们会使用一个头节点head其并不存储数据只是作为一个哨兵位的作用负责指向下一个元素。在这里插入图片描述
双向链表的基本功能:

  1. 双向链表的初始化
  2. 双链表的销毁
  3. 创建一个新的节点
  4. 打印链表中的元素
  5. 双向链表尾插
  6. 双向链表尾删
  7. 双向链表头插
  8. 双向链表的头删
  9. 双链表元素查找
  10. 双向链表在pos的前面进行插入
  11. 双向链表删除pos位置的节点

双向链表的定义

//双向链表的定义
typedef int LTDatatype;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDatatype val;
}LTNode;

双向链表-创建新的节点

因为我们是动态开辟的链表，因此我们在对链表进行操作的时候，每插入一个节点时都要开辟一个节点，因此我们一样写一个接口函数来实现。
代码思路:我们只需要直接和前面单链表一样开辟思路即可，无非我们需要多管理一个prev指针，这里我们让其置为空即可。
代码实现：

LTNode* ListCreate(LTDatatype x)//创建一个新的节点
{
	LTNode* newnode = malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;
	newnode->prev = NULL;
	return newnode;
}

双向链表-初始化

代码思路：因为双向链表中，我们需要一个哨兵位(头节点)来管理，因此我们在初始化的时候，需要开辟一个节点作为哨兵位，然后将其的pre和next指针置为空即可。
代码实现:

LTNode* ListInit()//双链表的初始化
{
	LTNode* phead = ListCreate(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

双向链表-打印链表中的元素

代码思路：由于我们是一个循环双向链表，在前面的图可以知道，我们不能够直接通过判断尾指针是否为空指针来判定是否是链表中的尾部元素，但是我们可以知道的是：链表中的最后一个节点的下一个节点，是该链表的头部，所以我们通过判定链表中当前节点的下一个节点是不是头节点，就可以知道是否是链表的尾部了。
代码实现:

void ListPrint(LTNode* pHead)//打印链表中的元素
{
	assert(pHead);
	LTNode* cur = pHead;
	printf("哨兵位-> ");
	while (pHead != cur->next)
	{
		printf("%d->", cur->next->val);
		cur = cur->next;
	}
	printf("\n");

双向链表-尾插

代码思路:由于双向循环链表的特性，我们可以知道哨兵位的pre指向的是尾部节点，因此我们在尾插的时候不用特意的去寻找尾节点，我们只需要，用哨兵位的前驱指针找到尾部节点，让其指向新开辟的空间。因此：

  1. 通过哨兵位的前驱指针找到尾部节点
  2. 让尾部节点指向新开辟的空间。
  3. 让新开辟的空间的前驱指针指向原理的尾部节点，再让其尾指针指向头节点，即可完成双向链表的尾插。(如下图所示)
    在这里插入图片描述

函数实现：

void ListPushBack(LTNode* pHead, LTDatatype x)//双向链表尾插
{
	assert(pHead);
	LTNode* newnode = ListCreate(x);
	LTNode* cur = pHead->prev;//尾结点
	pHead->prev = newnode;
	newnode->next = pHead;
	newnode->prev = cur;
	cur->next = newnode;
}

函数测试:

void Test_ListPushBack()
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-尾删

代码思路:这里我们依然要重复利用刚刚说到的循环双链表的性质，我们直接通过哨兵位的前驱指针来找到尾结点，来帮助我们进行尾删。

  1. 通过哨兵位前驱指针找到尾节点
  2. 找到尾结点的前驱指针，即倒数第二个节点，让其指向头节的前驱指针指向倒数第二个节点。
  3. 此时在将倒数第二个节点的尾部节点指向头节点，即可完成尾删，此时在释放掉原本的尾部节点即可。(如下图所示)
    在这里插入图片描述

代码实现:

void ListPopBack(LTNode* pHead)//双向链表尾删
{
	assert(pHead);
	assert(pHead->next);
	LTNode* tail = pHead->prev;//尾部节点
	pHead->prev = tail->prev;//让头节点指向倒数第二个节点
	tail->prev->next = pHead;//尾部节点指向头节点
	free(tail);
	tail = NULL;
}

函数测试:


void Test_ListPopBack()//双向链表尾删
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	printf("删除前\n");
	ListPrint(sl);
	ListPopBack(sl);
	printf("删除后\n");
	ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-头插

代码思路:

  1. 我们将哨兵位的next指针指向新开辟的节点。
  2. 将新节点的前驱指针指向原本的哨兵位
  3. 将新节点的next指向原本的第二个节点
  4. 将原本的第二个节点的前驱指针指向新节点，即可完成头插。(如下图)在这里插入图片描述

代码实现:

void ListPushFront(LTNode* pHead, LTDatatype x)//双向链表头插
{
	assert(pHead);
	LTNode* newnode = ListCreate(x);
	LTNode* tail = pHead->next;//记录头节点的下一个节点的位置
	pHead->next = newnode;//让头节点的下一个节点指向新节点
	newnode->prev = pHead;//让新节点的前驱指针指向头节点
	tail->prev = newnode;//让原本的第二个节点的前驱指针指向newnode
	newnode->next = tail;//新节点的尾部节点指针原本的第二个节点
}

函数测试:

void Test_ListPushFront()//双向链表头插
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	printf("头插前\n");
	ListPrint(sl);
	printf("头插后\n");
	ListPushFront(sl, 10);
	ListPrint(sl);
}

运行结果：
在这里插入图片描述

双向链表-头删

代码思路:

  1. 我们直接通过哨兵位找到头节点，然后将哨兵位的后驱指针指向头节点的下一个节点。
  2. 将头节点的下一个节点的前驱指针指向哨兵位
  3. 在将原本的头节点释放掉即可完成头删（如下图）
    在这里插入图片描述

代码实现:

void ListPopFront(LTNode* pHead)//双向链表的头删
{
	assert(pHead);
	assert(pHead->next);
	LTNode* tail = pHead->next;
	pHead->next = tail->next;//找到第二个节点指向哨兵位后驱指针
	tail->next->prev = pHead;//让次节点指向哨兵位
	free(tail);
	tail = NULL;
}

函数测试:

void Test_ListPopFront()//双向链表的头删
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	printf("头删前\n");
	ListPrint(sl);
	printf("头删后\n");
	ListPopFront(sl);
	ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-元素查找

代码思路:

  1. 这里我们依然通过双向链表的性质来帮助我们判断是否走到了链表尾部。
  2. 我们定义一个cur指针去帮助我们查找
  3. 当cur碰到了尾部的时候说明查找完了，如果此时还没找到就返回空即可
  4. 在查找的过程中碰到了要查找的值直接返回此时cur的地址即可。(如下图)
    请添加图片描述

代码实现:

LTNode* ListFind(LTNode* pHead, LTDatatype x)//双链表查找
{
	assert(pHead);
	LTNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

函数测试：


void Test_ListFind()//双向链表的查找
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	printf("%p\n", ListFind(sl, 2));
	printf("%p\n", ListFind(sl, 999));
}

运行结果:
在这里插入图片描述

双向链表-在pos的前面进行插入

代码思路:

  1. 我们找到要插入的pos的前一个节点，让其的next指向新开辟的节点
  2. 在让此时pos前驱指针所在的位置指向新开辟的节点
  3. 再让原本插入的节点的next指向新开辟的节点
  4. 再让新开辟的节点的前驱指针和next分别指向原本pos的前一个节点和指向pos。（如下图）

在这里插入图片描述
代码实现:

void ListInsert(LTNode* pos, LTDatatype x)// 双向链表在pos的前面进行插入
{
	LTNode* newnode = ListCreate(x);
	LTNode* cur = pos->prev;//找到pos前的一个节点
	pos->prev = newnode;//让其前一个结点指向新结点
	cur->next = newnode;
	newnode->prev = cur;
	newnode->next = pos;
}

函数测试:

void Test_ListInsert()
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	printf("插入前\n");
	ListPrint(sl);
	ListInsert(ListFind(sl, 2), 99);
	printf("插入后\n");
	ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-删除pos所在的位置

代码思路:

  1. 我们找到pos所在位置的下个一个节点让其指向pos所在位置的前一个结点
  2. 此时在释放掉pos所在的位置即可完成删除

代码实现:

void ListErase(LTNode* pos)// 双向链表删除pos位置的节点
{
	assert(pos);
	LTNode* tail = pos->next;
	tail->prev = pos->prev;
	pos->prev->next = tail;
	free(pos);
	pos = NULL;
}

函数测试:

void Test_ListErase()
{
	LTNode* sl = ListInit();
	ListPushBack(sl, 5);
	ListPushBack(sl, 2);
	ListPushBack(sl, 1);
	ListPushBack(sl, 8);
	printf("删除前\n");
	ListPrint(sl);
	printf("删除后\n");
	ListErase(ListFind(sl, 2));
	ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-链表的销毁

关于双向链表的销毁这里就不做过多的总结了，这个和前面的打印元素有比较像，因此不懂的可以参考一下即可。
代码实现:

void ListDestory(LTNode* pHead)//双链表的销毁
{
	assert(pHead);
	LTNode* cur = pHead->next;
	
	while (pHead != cur)
	{
		LTNode* tail = cur->next;
		free(cur);
		cur = tail;
	}
	free(pHead);

}

总结

到这里我们可以发现，当我们写了一个插入之后会发现，那双向链表的头插和尾插，我们可以直接用我们刚刚写的插入的函数直接来实现，就完全没必要单独写尾插和头插了，至于为什么放在最后才说，是因为作者想和大家一起锻炼一下自己的思维能力，这里直接放代码就不演示了。

void ListPushBack(LTNode* pHead, LTDatatype x)//双向链表尾插
{
	assert(pHead);
	ListInsert(pHead,x);//直接再phead之前插入即可
}

void ListPushFront(LTNode* pHead, LTDatatype x)//双向链表头插
{
	assert(pHead);
	ListInsert(pHead->next, x);
}

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

🫵🫵🫵 这里提前祝各位新年快乐呀！ 💞

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/280042.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

50. Pow(x, n)(Leetcode) C++递归实现（超详细）

50. Pow(x, n)(Leetcode) C++递归实现（超详细）

文章目录 前言一、题目分析二、算法原理1.递归分析2.递归实现 三、代码实现复杂度分析总结 前言 在本文章中，我们将要详细介绍一下Leetcode中第50题， Pow(x, n)的内容 一、题目分析 题目要求很简单：我们模拟实现一个pow函数。 二、算法原理…
阅读更多...
IP地址的四大类型：动态IP、固定IP、实体IP、虚拟IP的区别与应用

IP地址的四大类型：动态IP、固定IP、实体IP、虚拟IP的区别与应用

在网络通信中，IP地址是设备在互联网上唯一标识的关键元素。动态IP、固定IP、实体IP和虚拟IP是四种不同类型的IP地址，它们各自具有独特的特点和应用场景。 1. 动态IP地址： 动态IP地址是由Internet Service Provider（ISP&#xff…
阅读更多...
JavaScript使用教程（二）：类型、值和变量

JavaScript使用教程（二）：类型、值和变量

计算机程序通过操作值（如数值3.14）或文本（如“Hello World”）来工作。编程语言中这些可以表示和操作的值被称为类型，而一门语言支持的类型集也是这门语言最基本的特征。程序在需要把某个值保存下来以便将来使用时&…
阅读更多...
Halcon纹理分析texture_laws/trans_from_rgb

Halcon纹理分析texture_laws/trans_from_rgb

Halcon纹理分析 文章目录 Halcon纹理分析1. 纹理滤波器2. 织物折痕检测 纹理是图像表面的一种灰度变化。有的纹理很规则，会以局部小区域为单元重复出现，而有的纹理则呈现出随机性。对于规则的纹理，可以很容易地从中分辨出重复的区域&#xff…
阅读更多...
Unity坦克大战开发全流程——开始场景——开始界面

Unity坦克大战开发全流程——开始场景——开始界面

开始场景——开始界面 step1：设置UI 反正按照这张图拼就行了 step2：写脚本 前面的拼UI都是些比较机械化的工作，直到这里写代码的时候才真正开始有点意思了，从这里开始，我们就要利用面向对象的思路来进行分析&#xff1…
阅读更多...
基于Java图书借阅管理系统设计与实现（源码+部署文档）

基于Java图书借阅管理系统设计与实现（源码+部署文档）

博主介绍： ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ 🍅 文末获取源码联系 🍅 👇🏻 精彩专栏 推荐订阅 👇🏻 不然下次找不到 Java项目精品实…
阅读更多...
这儿有一道SPSS回归分析考试题，大家学会了吗？

这儿有一道SPSS回归分析考试题，大家学会了吗？

为研究某地区房地产市场的价格与相关影响因素之间的关系，现从该地区采集了 20 份样本，数据如下表，请给出销售价格与相关影响因素之间的函数表达式，并从统计学角度分析这些因素之间的关系，最后预测 X 小区的平均销售价格…
阅读更多...
集群部署篇--Redis 主从模式

集群部署篇--Redis 主从模式

文章目录 前言Redis 主从部署：1.1 主从架构 介绍：1.2 主从架构 实现：1.2.1 redis 安装： 1.3 主从架构优缺点：1.4 故障转移： 总结 前言 显然在线上环境中 Redis 服务不能以单机的方式运行，必须有…
阅读更多...
基于Java学生成绩管理系统设计与实现（源码+部署文档+报告）

基于Java学生成绩管理系统设计与实现（源码+部署文档+报告）

博主介绍： ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ 🍅 文末获取源码联系 🍅 👇🏻 精彩专栏 推荐订阅 👇🏻 不然下次找不到 Java项目精品实…
阅读更多...
Python-地图可视化

Python-地图可视化

地图可视化 1.基础地图使用1.1基础地图演示1.2视觉映射器 2.全国疫情地图2.1数据整理2.2创建地图并添加数据2.3设置全局配置 3.省级疫情图 1.基础地图使用 1.1基础地图演示 # 导入模块 from pyecharts.charts import Map # 绘图 map Map() # 构建数据 data [("北京市&…
阅读更多...
hyperf console 执行

hyperf console 执行

一、原理描述 hyperf中，不难发现比如自定义控制器中获取参数，hyperf.php中容器获取，传入的都是接口，而不是实体类。 这是因为框架中的配置文件有设置对应抽象类的子类，框架加载的时候将其作为数组，使用的…
阅读更多...
数据之光：乡镇企业的发展利器——数据可视化

数据之光：乡镇企业的发展利器——数据可视化

数据可视化是一项强大的工具，它不仅在大型企业中发挥关键作用，而且在乡镇企业中也能作出显著贡献。那么，数据可视化究竟能为乡镇企业做出什么样的贡献呢？ 首先，数据可视化为乡镇企业提供了更清晰的业务洞察。通过将庞大…
阅读更多...
《基础教育研究》期刊杂志投稿方式

《基础教育研究》期刊杂志投稿方式

《基础教育研究》是国家新闻出版总署批准的正规教育类学术期刊。本刊以研究基础教育的理论和实践问题、为基础教育改革和发展服务为宗旨，以广大中小学、幼儿园教师、校长、教研员和管理人员为主要读者对象，及时宣传贯彻党的教育方针、政策、交流全国各地…
阅读更多...
C++图论之强连通图

C++图论之强连通图

1. 连通性 什么是连通性？ 连通，字面而言，类似于自来水管道中的水流，如果水能从某一个地点畅通流到另一个地点，说明两点之间是连通的。也说明水管具有连通性，图中即如此。 无向图和有向图的连通概念稍有差…
阅读更多...
Pandas教程（一）—— 数据结构

Pandas教程（一）—— 数据结构

前言 Pandas是贯穿数据分析的主要工具之一，它经常和其他数值计算工具一起使用（例如：Numpy、SciPy和matplotlib）。尽管pandas采用了很多NumPy的代码风格，但二者最大的区别是：pandas主要用于处理表格型或异质…
阅读更多...
Typora快捷键设置详细教程

Typora快捷键设置详细教程

文章目录 一、快捷键设置步骤二、设置快捷键简单案例参考资料 一、快捷键设置步骤 在typora软件中，快捷键的设置步骤主要为： 打开【文件】–>【偏好设置】，找到【通用】–>【打开高级设置】，找到 conf.user.json 文件。 然…
阅读更多...
系统启动流程 - 理解modules加载流程

系统启动流程 - 理解modules加载流程

​编辑 Hacker_Albert    202 linux 启动流程module加载 1.启动过程分为三个部分 BIOS 上电自检（POST）引导装载程序 (GRUB2)内核初始化启动 systemd，其是所有进程之父。 1.1.BIOS 上电自检（POST） BIOS stands for…
阅读更多...
HTML5+CSS3②——图像、超链接、音频、视频

HTML5+CSS3②——图像、超链接、音频、视频

目录 图像 超链接 音频 视频 图像 作用&#xff1a;在网页中插入图片 单标签&#xff1a; 标签名&#xff1a;<img src"图片的URL"> <img src"图片的URL" alt"替换文本" title"提示文本"> 属性写在尖括号里面&#xff0c;…
阅读更多...
使用SpringBoot AOP记录操作日志和异常日志

使用SpringBoot AOP记录操作日志和异常日志

使用SpringBoot AOP记录操作日志和异常日志 平时我们在做项目时经常需要对一些重要功能操作记录日志&#xff0c;方便以后跟踪是谁在操作此功能&#xff1b;我们在操作某些功 能时也有可能会发生异常&#xff0c;但是每次发生异常要定位原因我们都要到服务器去查询日志才能找…
阅读更多...
Stable Diffusion 系列教程 - 5 ControlNet

Stable Diffusion 系列教程 - 5 ControlNet

ControlNet和LORA的定位都是对大模型做微调的额外网络。作为入门SD的最后一块拼图是必须要去了解和开发的。为什么ControlNet的影响力如此的大&#xff1f;在它之前&#xff0c;基于扩散模型的AIGC是非常难以控制的&#xff0c;扩散整张图像的过程充满了随机性。这种随机性并不…
阅读更多...
最新文章

Copyright @ 2022~2023