双向链表（数据结构与算法）

请添加图片描述

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋双向链表

  • 🍌双向链表的定义与结构
  • 🍌双向链表增删查改（有头+双向+循环链表增删查改实现）
    • 🍍其它接口
    • 🍍创建返回链表的头结点
    • 🍍双向链表销毁
    • 🍍双向链表打印
    • 🍍双向链表尾插
    • 🍍双向链表尾删
    • 🍍双向链表头插
    • 🍍双向链表头删
    • 🍍双向链表查找
    • 🍍双向链表在pos的前面进行插入
    • 🍍双向链表删除pos位置的节点
  • 🍌双向链表整体代码的实现

🍌双向链表的定义与结构

在这里插入图片描述
双向链表：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。（两个指针就是一个指向下一个数据，另一个指针指向上一个数据。如图中head头指针和tail尾指针）

在这里插入图片描述
在双向链表中还有一个特殊点，就是头指针，双向链表是带头的。在上次我们说的单链表中是不带头的，一旦涉及到头，我们就是先判断是不是为空，而在双向链表中就是不会涉及到这个问题了，不用再去一个一个的判断，就会省去很多的麻烦。

带头的双向链表嘴尾常用，所以我们这里就介绍带头的双向链表

🍌双向链表增删查改（有头+双向+循环链表增删查改实现）

🍍其它接口

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int LTdatetype;

typedef struct ListNode
{
	LTdatetype date;
	struct ListNode* next;
	struct ListNode* tail;
}ListNode;

定义一些接口

🍍创建返回链表的头结点

//创建返回链表的头结点
ListNode* Create(LTdatetype x)
{
	ListNode* cur =(ListNode*)malloc(sizeof(ListNode));
	if (cur == NULL)
	{
		perror("malloc  faild");
		exit(-1);
	}
	cur->next = NULL;
	cur->tail = NULL;
	cur->date = x;
	return cur;
}

ListNode* Inia()
{
	ListNode* node = Create(0);
	node->next = node;
	node->tail = node;

	return node;
}

Create函数就是创建一个节点。而Inia函数本来是进行初始化，而想要变成循环的链表，形参改变实参那就要用到二级指针，因为这里是双向链表，涉及头指针的时候不需要考虑二级指针，所以在这里就只有初始化需要用到头指针，所以我们就干脆用返回值，这样就不看起来违和了，当然用二级指针也没有什么问题，看自己习惯即可。

🍍双向链表销毁

// 双向链表销毁
void Destreoy(ListNode* ps)
{
	assert(ps);
	ListNode* cur = ps->next;
	while (cur != ps)
	{
		cur = cur->next;
		free(cur->tail);
	}
	free(ps);
}

🍍双向链表打印

// 双向链表打印
void Print(ListNode* ps)
{
	assert(ps);
	ListNode* cur = ps->next;
	while (cur != ps)
	{
		printf("%d<=>", cur->date);
		cur = cur->next;
	}
}

在这里插入图片描述

在这里打印，我们就不能使用和单链表打印的方法了，因为我们这里是循环链表，并且我们的ps里面没有存有数据，所以我们要从ps的下个数据开始，也就是图中cur的位置，然后在cur到ps的时候跳出循环就可以了。

🍍双向链表尾插

// 双向链表尾插
void LTpushbake(ListNode* ps, LTdatetype x)
{
	assert(ps);
	ListNode* cur = Create(x);
	ListNode *node = ps->tail ;
	
	//ps的头要指向cur
	node->next = cur;
	//cur的尾要指向ps
	cur->tail = node;

	//ps的尾要指向cur
	ps->tail = cur;
	//cur的头要指向ps
	cur->next = ps;
}

在这里插入图片描述

之所以要这样的指向，是因为这是一个循环的双向链表。

🍍双向链表尾删

// 双向链表尾删
void LTpopbake(ListNode* ps)
{
	assert(ps);
	assert(ps->next != ps);
	ListNode* cur = ps->tail;
	ListNode* curtail = cur->tail;

	free(cur);
	cur->next = cur->tail = NULL;

	curtail->next = ps;
	ps->tail = curtail;

}

在这里插入图片描述
在这里因为这是循环链表所以不用遍历去找尾结点，当然用遍历也是可以的

🍍双向链表头插

// 双向链表头插
void LTpushfront(ListNode* ps, LTdatetype x)
{
	assert(ps);
	ListNode* node = Create(x);

	ListNode* cur = ps->next;

	ps->next = node;
	node->tail = ps;

	node->next = cur;
	cur->tail = node;

}

在这里插入图片描述
在带头的链表中，头插是最方便的，不用像不带头的单链表中一个一个去判断，大大的节省了我们的时间

🍍双向链表头删

// 双向链表头删
void LTpopfront(ListNode* ps)
{
	assert(ps);
	assert(ps->next != ps);
	ListNode* node = ps->next;
	ListNode* node_next = node->next;

	free(node);

	ps->next = node_next;
	node_next->tail = ps;
}

在这里插入图片描述
在带头的链表中，头删也很方便了。

🍍双向链表查找

// 双向链表查找
ListNode * LTfind(ListNode* ps, LTdatetype x)
{
	assert(ps);
	ListNode* cur = ps->next;
	while (cur != ps)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

关于这个查找还是要注意下，因为我们这里是循环链表，所以要注意记得要设置跳出循环的条件。

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

// 双向链表在pos的前面进行插入
void LTinsert(ListNode *pos, LTdatetype x)
{
	assert(pos);
	ListNode* node = Create(x);
	ListNode* pos_tail = pos->tail;

	pos_tail->next = node;
	node->tail = pos_tail;

	node->next = pos;
	pos->tail = node;

}

在这里插入图片描述
在pos前插入和头插，尾插差不多的意思

🍍双向链表删除pos位置的节点

// 双向链表删除pos位置的节点
void LTdelete(ListNode* pos)
{
	assert(pos);
	ListNode* pos_tail = pos->tail;
	ListNode* pos_next = pos->next;

	free(pos);

	pos_tail->next = pos_next;
	pos_next->tail = pos_tail;
}

在这里插入图片描述

删除pos位置，也差不多和前面意思都差不多

🍌双向链表整体代码的实现

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int LTdatetype;


//创建返回链表的头结点
typedef struct ListNode
{
	LTdatetype date;
	struct ListNode* next;
	struct ListNode* tail;
}ListNode;

ListNode* Create(LTdatetype x)
{
	ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
	if (cur == NULL)
	{
		perror("malloc  faild");
		exit(-1);
	}
	cur->next = NULL;
	cur->tail = NULL;
	cur->date = x;
	return cur;
}

ListNode* Inia()
{
	ListNode* node = Create(0);
	node->next = node;
	node->tail = node;

	return node;
}


// 双向链表销毁
void Destreoy(ListNode* ps)
{
	assert(ps);
	ListNode* cur = ps->next;
	while (cur != ps)
	{
		cur = cur->next;
		free(cur->tail);
	}
	free(ps);
}

// 双向链表打印
void LTprint(ListNode* ps)
{
	assert(ps);
	ListNode* cur = ps->next;
	printf("ps<=>");
	while (cur != ps)
	{
		printf("%d<=>", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

// 双向链表尾插
void LTpushbake(ListNode* ps, LTdatetype x)
{
	assert(ps);
	ListNode* cur = Create(x);
	ListNode* node = ps->tail;

	node->next = cur;
	cur->tail = node;

	ps->tail = cur;
	cur->next = ps;
}

// 双向链表尾删
void LTpopbake(ListNode* ps)
{
	assert(ps);
	assert(ps->next != ps);
	ListNode* cur = ps->tail;
	ListNode* curtail = cur->tail;

	free(cur);

	curtail->next = ps;
	ps->tail = curtail;

}

// 双向链表头插
void LTpushfront(ListNode* ps, LTdatetype x)
{
	assert(ps);
	ListNode* node = Create(x);

	ListNode* cur = ps->next;

	ps->next = node;
	node->tail = ps;

	node->next = cur;
	cur->tail = node;

}


// 双向链表头删
void LTpopfront(ListNode* ps)
{
	assert(ps);
	assert(ps->next != ps);
	ListNode* node = ps->next;
	ListNode* node_next = node->next;

	free(node);

	ps->next = node_next;
	node_next->tail = ps;
}

// 双向链表查找
ListNode * LTfind(ListNode* ps, LTdatetype x)
{
	assert(ps);
	ListNode* cur = ps->next;
	while (cur != ps)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


// 双向链表在pos的前面进行插入
void LTinsert(ListNode *pos, LTdatetype x)
{
	assert(pos);
	ListNode* node = Create(x);
	ListNode* pos_tail = pos->tail;

	pos_tail->next = node;
	node->tail = pos_tail;

	node->next = pos;
	pos->tail = node;

}

// 双向链表删除pos位置的节点
void LTdelete(ListNode* pos)
{
	assert(pos);
	ListNode* pos_tail = pos->tail;
	ListNode* pos_next = pos->next;

	free(pos);

	pos_tail->next = pos_next;
	pos_next->tail = pos_tail;
}


void test1()//测试
{
	ListNode* ps = Inia();
	LTpushbake(ps, 1);//尾插
	LTpushbake(ps, 2);//尾插
	LTpushbake(ps, 3);//尾插
	LTpushbake(ps, 4);//尾插
	LTprint(ps);//打印

	LTpopbake(ps);//尾删
	LTprint(ps);//打印

	LTpushfront(ps, 10);//头插
	LTpushfront(ps, 11);//头插
	LTpushfront(ps, 12);//头插
	LTpushfront(ps, 13);//头插
	LTprint(ps);//打印

	LTpopfront(ps);//头删
	LTprint(ps);//打印

	ListNode *pos = LTfind(ps, 11);//双向链表查找
	if (pos == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了，为：%d\n", pos->date);
	}

	LTinsert(pos, 100);// 双向链表在pos的前面进行插入
	LTprint(ps);//打印

	LTdelete(pos);//双向链表删除pos位置的节点
	LTprint(ps);//打印

	Destreoy(ps);//双向链表销毁
}

int main()
{
	test1();//测试
	return 0;
}

带头的双向链表实现起来还是非常简单的，大家如果对于文章中的某一个点有问题，欢迎私聊我。

请添加图片描述

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

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

相关文章

香港身份（户口）大放水！23年香港优才计划、高才通计划申请数据公开！24年冲！

香港身份（户口）大放水！23年香港优才计划、高才通计划申请数据公开！24年冲！

香港身份&#xff08;户口&#xff09;大放水&#xff01;23年香港优才计划、高才通计划申请数据公开&#xff01;24年冲&#xff01; 近期香港入境处公布了各项人才入境计划申请及审批数字&#xff0c;: 截止今年10月31日一共有18.4万宗申请各类人才输入计划&#xff0c;获批人…
阅读更多...
IntelliJ IDEA无公网远程连接Windows本地Mysql数据库提高开发效率

IntelliJ IDEA无公网远程连接Windows本地Mysql数据库提高开发效率

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;…
阅读更多...
智能优化算法应用：基于蝴蝶算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于蝴蝶算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蝴蝶算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蝴蝶算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蝴蝶算法4.实验参数设定5.算法结果6.参考文献7.MA…
阅读更多...
【深度学习】注意力机制（三）

【深度学习】注意力机制（三）

本文介绍一些注意力机制的实现&#xff0c;包括EMHSA/SA/SGE/AFT/Outlook Attention。 【深度学习】注意力机制&#xff08;一&#xff09; 【深度学习】注意力机制&#xff08;二&#xff09; 目录 一、EMHSA&#xff08;Efficient Multi-Head Self-Attention&#xff09;…
阅读更多...
logstash插件简单介绍

logstash插件简单介绍

logstash插件 输入插件(input) Input&#xff1a;输入插件。 Input plugins | Logstash Reference [8.11] | Elastic 所有输入插件都支持的配置选项 SettingInput typeRequiredDefaultDescriptionadd_fieldhashNo{}添加一个字段到一个事件codeccodecNoplain用于输入数据的…
阅读更多...
可学习超图拉普拉斯算子代码

可学习超图拉普拉斯算子代码

python版本&#xff1a;3.6。sklearn版本&#xff1a;scikit-learn0.19 问题1&#xff1a;ERROR: Could not build wheels for ecos, scs, which is required to install pyproject.toml-based projects| 解决办法&#xff1a;cvxpy安装过程中遇到的坑_ecos 2.0.7.post1 cp37 …
阅读更多...
Terraform实战(二)-terraform创建阿里云资源

Terraform实战(二)-terraform创建阿里云资源

1 初始化环境 1.1 创建初始文件夹 $ cd /data $ mkdir terraform $ mkdir aliyun terraform作为terraform的配置文件夹&#xff0c;内部的每一个.tf&#xff0c;.tfvars文件都会被加载。 1.2 配置provider 创建providers.tf文件&#xff0c;配置provider依赖。 provider…
阅读更多...
LeetCode 每日一题 Day 9 ||简单dp

LeetCode 每日一题 Day 9 ||简单dp

70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&#xff1a;有两种方法可以爬到楼顶。 1 阶 1 阶2 阶 示例 2&am…
阅读更多...
智能井盖传感器怎么有效监测井盖位移

智能井盖传感器怎么有效监测井盖位移

随着城市化进程的加速推进&#xff0c;城市基础设施的安全与维护问题日益凸显&#xff0c;引发了社会的广泛关注。其中井盖作为城市地下设施的重要一环&#xff0c;其安全问题时刻影响着市民的幸福生活。近年来智能井盖传感器的发展与应用为实时监测井盖位移提供了全新的解决方…
阅读更多...
嵌入式开发按怎样的路线学习较好？

嵌入式开发按怎样的路线学习较好？

嵌入式开发按怎样的路线学习较好&#xff1f; 在开始前我有一些资料&#xff0c;是我根据自己从业十年经验&#xff0c;熬夜搞了几个通宵&#xff0c;精心整理了一份「嵌入式从专业入门到高级教程工具包」&#xff0c;点个关注&#xff0c;全部无偿共享给大家&#xff01;&…
阅读更多...
BigData之Google Hadoop中间件安装

BigData之Google Hadoop中间件安装

前言 Hadoop / Zookeeper / Hbase 因资源有限 这三个都是安装在同一台Centos7.9的机器上 但通过配置 所以在逻辑上是distributed模式 1 Java安装 1.1 下载java11 tar/opt/java/jdk-11.0.5/ 1.2 环境配置修改 文件/etc/profile export JAVA_HOME/opt/java/jdk-11.0.5/ e…
阅读更多...
网络层重点协议——IP协议详解

网络层重点协议——IP协议详解

✏️✏️✏️今天给大家分享的是网络层的重点协议——IP协议。 清风的CSDN博客 &#x1f6e9;️&#x1f6e9;️&#x1f6e9;️希望我的文章能对你有所帮助&#xff0c;有不足的地方还请各位看官多多指教&#xff0c;大家一起学习交流&#xff01; ✈️✈️✈️动动你们发财的…
阅读更多...
解决vue3 动态引入报错问题

解决vue3 动态引入报错问题

之前这样写的&#xff0c;能使用&#xff0c;但是有警告 警告&#xff0c;查了下&#xff0c;是动态引入的问题&#xff0c;看到说要用glob 然后再我的基础上&#xff0c;稍微 改了下&#xff0c;就可以了&#xff1a; 最后打印了下&#xff0c;modules[../../components/flowc…
阅读更多...
每日一练【无重复字符的最长子串】

每日一练【无重复字符的最长子串】

一、题目描述 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 二、题目解析 算法思想&#xff1a;移动窗口的思想去解决。 那为什么要用这个方法解决呢&#xff1f; 我们首先用暴力的思路去遍历一遍&#xff0c;我们遍历到deabc后&#xff…
阅读更多...
外包干了3个月，技术退步明显.......

外包干了3个月，技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…
阅读更多...
图文教程：从0开始安装stable-diffusion

图文教程：从0开始安装stable-diffusion

现在AI绘画还是挺火&#xff0c;Midjourney虽然不错&#xff0c;但是对于我来说还是挺贵的。今天我就来安一下开源的AI绘画stable-diffusion,它的缺点就是对电脑的要求比较高&#xff0c;尤其是显卡。 话不多说开搞。 访问sd的github&#xff0c;https://github.com/AUTOMATIC…
阅读更多...
AIGC报告专题：计算机Pika-AIGC新秀-视频生成产业或迎来GPT时刻

AIGC报告专题：计算机Pika-AIGC新秀-视频生成产业或迎来GPT时刻

今天分享的AIGC系列深度研究报告&#xff1a;《AIGC报告专题&#xff1a;计算机Pika-AIGC新秀-视频生成产业或迎来GPT时刻》。 &#xff08;报告出品方&#xff1a;中泰证券&#xff09; 报告共计&#xff1a;11页 Pika&#xff1a;专注Text to Video生成场景&#xff0c;支持…
阅读更多...
创投课程第四期 | Web3一级市场投资框架的演变及投资人能力框架的构成

创投课程第四期 | Web3一级市场投资框架的演变及投资人能力框架的构成

协会邀请了来自Zonff Partners的合伙人——Colin&#xff0c;作为VC创投课程第4期的嘉宾&#xff0c;在北京时间12月9日(周六)下午14:00 PM-15:00 PM于蚂蚁链科技产业创新中心进行线下分享&#xff0c;届时将与所有对Web3投资、创业心怀热忱的朋友们共同探讨《WEB3一级市场投资…
阅读更多...
Java面试题（每天10题）-------连载（46）

Java面试题（每天10题）-------连载（46）

目录 Dubbo篇 1、Dubbo的默认集群容错方案 2、Dubbo支持哪些序列化方式&#xff1f; 3、Dubbo超时时间怎样设置&#xff1f; 4、服务调用超时问题怎么解决&#xff1f; 5、Dubbo在安全机制方面是如何解决的&#xff1f; 6、Dubbo和Dubbox之间的区别 7、Dubbo和Spring C…
阅读更多...
mybatis多表映射-对一关联

mybatis多表映射-对一关联

1、建库建表 create database mybatis-example; use mybatis-example; create table t_book (bid varchar(20) primary key,bname varchar(20),stuid varchar(20) ); insert into t_book values(b001,Java,s001); insert into t_book values(b002,Python,s002); insert into …
阅读更多...
最新文章

Copyright @ 2022~2023