双向链表 -- 详细理解和实现

                                                                                         欢迎光顾我的homepage                                                              

前言

        双向链表是一种带头双向循环的链表。在双向链表中，首先存在着一个头结点；其次每个节点有指向下一个节点的指针next 和指向上一个节点的指针prev ；最后，双向链表的头结点中存放上一个节点的指针指向链表的尾节点，尾节点中存放下一个节点的指针指向链表的头结点，形成一个闭环。这样双向链表既可以从前遍历，也可以从后遍历，直到回到起点。

一、链表的分类

        链表的结构多种多样，链表呢可以是带头（不带头）、双向（单向）、循环（不循环）的，我们之前实现的单链表其实就是不带头，单向，不循环的链表。

而这些有什么区别呢？

        带头和不带头

这里带头和不带头指的是有没有头结点，这单链表的实现过程中，是直接创建一个指针变量指向链表的第一个节点（这是没有头结点的情况），而存在头结点呢，就是一个哨兵位，里面没有存放数据，存放了指向第一个节点的指针。

        可以看到，带头的链表多了一个节点（head），这个节点中没有存放任何数据，这样做可以方便对链表的节点进行统一操作。

        单向和双向

    单向是可以通过一个节点找到它的后一个节点，而双向是可以通过一个节点找到它前后的节点。

        循环和不循环

    这实现单链表的时候，我们将链表的最后一个节点next指针置位了空指针（NULL），而循环的链表中，我们会将最后一个节点的next指针指向链表的头结点，对于双向链表，将头节点的prev(上一个节点）指针指向链表的尾节点。

二、双向链表的实现

这里实现的双向链表，先来看一下双向链表的节点结构

双向链表节点

typedef int LTDataType;
//双向链表
typedef struct ListNode
{
	struct ListNode* prev;  //指向上一个节点
	struct ListNode* next;  //指向下一个节点
	LTDataType data;
}LTNode;

双向链表的功能预览

//初始化并创建头结点
void LTInit(LTNode** phead);
//LTNode* LTInit();
//输出
void LTPrint(LTNode* phead);
//创建新的节点
LTNode* LTBuyNode(LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType find);
//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x);
//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x);
//删除pos节点
void LTPop(LTNode* pos);
//链表销毁
void LTDesTroy(LTNode* phead);

2.1、创建新的节点

        创建节点，和单链表一样，都是动态开辟的空间。

//创建新的节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* ptail = (LTNode*)malloc(sizeof(LTNode));
	if (ptail == NULL)
	{
		perror("LTBuyNode--malloc filed!");
		exit(1);
	}
	ptail->data = x;
	ptail->prev = ptail->next = NULL;
	return ptail;
}

2.2、双向链表初始化并创建头结点

        链表初始化，其实就是创建一个头节点（也叫哨兵位）；因为这里是双向链表，创建完头节点之后，让头节点的prev和next指针都指向它自己。

//初始化并创建头结点
void LTInit(LTNode** phead)
{
	*phead = LTBuyNode(-1);
	(*phead)->prev = (*phead)->next = *phead;
}

2.3、输出链表

        遍历链表并输出有效数据，这里双向链表可以从前开始遍历也可以从后开始遍历。

//输出
void LTPrint(LTNode* phead)
{
	LTNode* ptail = phead->next;
	//遍历双向链表 -- 从前开始遍历
	while (ptail != phead)
	{
		printf("%d -> ", ptail->data);
		ptail = ptail->next;
	}
	printf("\n");
}

2.4、双向链表头插数据

        从链表的头部插入数据，创建新的节点，然后将新的节点prev指针指向头节点，将next指针指向头节点的下一个节点；然后修改头节点的next指针和头节点下一个节点的prev指针即可。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = phead;
	newnode->next = phead->next;

	//修改前后节点的指针指向
	phead->next->prev = newnode;
	phead->next = newnode;
}

2.5、双向链表尾插数据

        从链表尾部插入到尾节点的后面，创建新的节点，将新节点的prev指针指向头节点的上一个节点，将next指针指向头节点，然后修改尾节点的next指针和头节点的prev指针即可。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

	//修改前后节点指针指向
	phead->prev->next = newnode;
	phead->prev = newnode;
}

2.6、双向链表头删数据

        头删是删除头节点的后一个节点，因为是动态开辟的内存，需要内存释放；删除后，让头节点的next指针 指向下一个数据的节点。

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead != phead->next); //链表为空的话就不能进行删除
	LTNode* del = phead->next;  
	phead->next->next->prev = phead;
	phead->next = phead->next->next;
	free(del);
	del = NULL;
}

2.7、双向链表尾删数据

        尾插是删除链表的尾节点，释放内存之后，让尾节点的上一个节点next指针指向头节点，头节点的prev指针指向删除节点的上一个节点。

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead); //链表为空不能进行删除
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

2.8、双向链表查找数据

        这里如果找到了，就返回该节点的指针，如果没有就返回NULL；方便对其进行前后插入数据和删除。

//查找
LTNode* LTFind(LTNode* phead, LTDataType find)
{
	assert(phead);
	LTNode* ptail = phead->next;
	while (ptail != phead) //遍历链表
	{
		if (ptail->data == find) {
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}

2.9、在指定节点pos之前插入数据

        根据我们查找到的节点，在其之前插入数据，首先创建新节点，将新节点的prev指针指向pos的前一个节点，新节点的next指针指向pos；再修改pos的上一个节点的next指针指向和pos的prev指针指向即可；

//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;

	//修改pos前后节点指针的指向
	pos->prev->next = newnode;
	pos->prev = newnode;
}

        这里就可以发现双向链表的一个好处，不用像单向链表那样遍历链表来寻找pos的上一个节点。

2.10、在指定节点pos之后插入数据

        根据查找到的节点，在其之后插入数据；首先创建节点，将新节点的prev指针指向pos，新节点的next指针指向pos的下一个节点；然后修改pos的next指针指向和pos下一个节点的prev指针指向即可。

//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

	//修改pos前后节点指针的指向
	pos->next->prev = newnode;
	pos->next = newnode;
}

2.11、删除指定节点pos

        根据查找到的节点，然后将其删除，这里需要修改pos前后节点的指针指向。

//删除pos节点
void LTPop(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

2.12、双向链表的销毁

        及时对动态开辟的内存进行释放，养成好习惯

        现在，动态开辟的链表需要进行销毁（也就是动态内存释放），这里就需要遍历链表了。

//链表销毁
void LTDesTroy(LTNode* phead)
{
	assert(phead);
	LTNode* ptail = phead->next;
	while (ptail != phead)
	{
		LTNode* del = ptail->next;
		free(ptail);
		ptail = del;
	}
	free(ptail);
	ptail = NULL;
}


代码总览

List.h

#define _CRT_SECURE_NO_WARNINGS

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

typedef int LTDataType;
//双向链表
typedef struct ListNode
{
	struct ListNode* prev;  //指向上一个节点
	struct ListNode* next;  //指向下一个节点
	LTDataType data;
}LTNode;

//初始化并创建头结点
void LTInit(LTNode** phead);
//LTNode* LTInit();
//输出
void LTPrint(LTNode* phead);
//创建新的节点
LTNode* LTBuyNode(LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType find);
//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x);
//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x);
//删除pos节点
void LTPop(LTNode* pos);
//链表销毁
void LTDesTroy(LTNode* phead);

List.c

#include"List.h"

//创建新的节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* ptail = (LTNode*)malloc(sizeof(LTNode));
	if (ptail == NULL)
	{
		perror("malloc filed!");
		exit(1);
	}
	ptail->data = x;
	ptail->prev = ptail->next = NULL;
	return ptail;
}
//初始化并创建头结点
void LTInit(LTNode** phead)
{
	*phead = LTBuyNode(-1);
	(*phead)->prev = (*phead)->next = *phead;
}
//输出
void LTPrint(LTNode* phead)
{
	LTNode* ptail = phead->next;
	//遍历双向链表 -- 从前开始遍历
	while (ptail != phead)
	{
		printf("%d -> ", ptail->data);
		ptail = ptail->next;
	}
	printf("\n");
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = phead;
	newnode->next = phead->next;

	//修改前后节点的指针指向
	phead->next->prev = newnode;
	phead->next = newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

	//修改前后节点指针指向
	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead != phead->next); //链表为空的话就不能进行删除
	LTNode* del = phead->next;  
	phead->next->next->prev = phead;
	phead->next = phead->next->next;
	free(del);
	del = NULL;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead); //链表为空不能进行删除
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType find)
{
	assert(phead);
	LTNode* ptail = phead->next;
	while (ptail != phead) //遍历链表
	{
		if (ptail->data == find) {
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}
//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;

	//修改pos前后节点指针的指向
	pos->prev->next = newnode;
	pos->prev = newnode;
}
//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

	//修改pos前后节点指针的指向
	pos->next->prev = newnode;
	pos->next = newnode;
}

感谢各位大佬支持并指出问题，

                如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！

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

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

相关文章

什么是业务架构、数据架构、应用架构和技术架构

什么是业务架构、数据架构、应用架构和技术架构

TOGAF(The Open Group Architecture Framework)是一个广泛应用的企业架构框架&#xff0c;旨在帮助组织高效地进行架构设计和管理。而TOGAF的核心就是由我们熟知的四大架构领域组成&#xff1a;业务架构、数据架构、应用架构和技术架构。 所以今天我们就来聊聊&#xff0c;企业…
阅读更多...
邮局服务器推荐需要考虑的因素？如何选择？

邮局服务器推荐需要考虑的因素？如何选择？

邮局服务器推荐时如何考量&#xff1f;怎么使用服务器提升效率&#xff1f; 在选择邮局服务器时&#xff0c;有许多重要因素需要考虑。这些因素将直接影响到邮件服务的质量、稳定性和安全性。AokSend将详细探讨选择邮局服务器时需要注意的各个方面。 邮局服务器推荐&#xff…
阅读更多...
专属大学生的创作活动，你在CSDN坚持创作，虚竹哥带你成长，带你涨粉

专属大学生的创作活动，你在CSDN坚持创作，虚竹哥带你成长，带你涨粉

❤️作者主页&#xff1a;小虚竹 ❤️作者简介&#xff1a;大家好,我是小虚竹。2022年度博客之星评选TOP 10&#x1f3c6;&#xff0c;Java领域优质创作者&#x1f3c6;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;掘金年度人气作…
阅读更多...
x264 编码器 AArch64 汇编函数模块关系分析

x264 编码器 AArch64 汇编函数模块关系分析

x264 编码器 AArch64 汇编介绍 x264 是一个流行的开源视频编码器，它实现了 H.264/MPEG-4 AVC 标准。x264 项目致力于提供一个高性能、高质量的编码器，支持多种平台和架构。对于 AArch64（即 64 位 ARM 架构），x264 编码器利用该架构的特性来优化编码过程。在 x264 编码器中，…
阅读更多...
[论文精读]BrainLM: A foundation model for brain activity recordings

[论文精读]BrainLM: A foundation model for brain activity recordings

论文网址&#xff1a;pdf (openreview.net) 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 省流版 1.1. 心得 1.2…
阅读更多...
经验分享：征信查询多了会不会影响大数据综合评分?

经验分享：征信查询多了会不会影响大数据综合评分?

很多人在申请贷款的时候&#xff0c;会有一个疑问&#xff0c;就是自己的征信没逾期&#xff0c;就是查询偏多一点&#xff0c;但能达到申贷要求&#xff0c;为什么还会被拒贷?其实就是大数据花了的原因&#xff0c;那征信查询多了会不会影响大数据综合评分呢?接下来本文就为…
阅读更多...
从零开始学习嵌入式----Linux系统中shell脚本

从零开始学习嵌入式----Linux系统中shell脚本

目录 Shell脚本入门&#xff1a;玩转功能语句和数组&#xff0c;提升你的效率&#xff01; 一、功能语句&#xff1a;让你的脚本更灵活 1. 条件语句&#xff1a;if、else、elif 2. 循环语句&#xff1a;for、while 二、数组&#xff1a;处理多项数据的好帮手 1. 声明数组…
阅读更多...
【CSS in Depth 2精译】2.5 无单位的数值与行高

【CSS in Depth 2精译】2.5 无单位的数值与行高

当前内容所在位置 第一章 层叠、优先级与继承第二章 相对单位 2.1 相对单位的威力2.2 em 与 rem2.3 告别像素思维2.4 视口的相对单位2.5 无单位的数值与行高 ✔️2.6 自定义属性2.7 本章小结 2.5 无单位的数值与行高 有些属性允许使用无单位的数值&#xff08;unitless value…
阅读更多...
《信息技术时代》是什么级别的期刊？是正规期刊吗？能评职称吗？

《信息技术时代》是什么级别的期刊？是正规期刊吗？能评职称吗？

​问题解答 问&#xff1a;《信息技术时代》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是万方维普收录的正规学术期刊。 问&#xff1a;《信息技术时代》级别&#xff1f; 答&#xff1a;省级。主管单位&#xff1a;深圳湾科技发展有限公司 主办单位&am…
阅读更多...
【Pytorch实用教程】transformer中创建嵌入层的模块nn.Embedding的用法

【Pytorch实用教程】transformer中创建嵌入层的模块nn.Embedding的用法

文章目录 1. nn.Embedding的简单介绍1.1 基本用法1.2 示例代码1.3 注意事项2. 通俗的理解num_embeddings和embedding_dim2.1 num_embeddings2.2 embedding_dim2.3 使用场景举例结合示例1. nn.Embedding的简单介绍 nn.Embedding 是 PyTorch 中的一个模块，用于创建一个嵌入层。…
阅读更多...
cdr捕捉点怎么设置---模大狮模型网

cdr捕捉点怎么设置---模大狮模型网

在 CorelDRAW 中&#xff0c;捕捉点(Snap Points)是一种非常有用的功能&#xff0c;它可以帮助你在绘制和编辑图形时对齐、定位和调整对象。以下是关于如何设置捕捉点的简要步骤&#xff1a; 打开和设置捕捉点&#xff1a; 打开捕捉点控制器&#xff1a; 在 CorelDRAW 的顶部菜…
阅读更多...
AI算力发展现状与趋势分析

AI算力发展现状与趋势分析

综合算力发展现状与趋势分析 在数字经济的疾速推动下&#xff0c;综合算力作为驱动各类应用和服务的新型生产力&#xff0c;其价值日益凸显。我们深入探讨了综合算力的定义、重要性以及当前发展状况&#xff1b;并从算力形态、运力性能和存储技术等角度&#xff0c;预见了其发展…
阅读更多...
斐讯N1盒子刷入Armbian并安装Docker拉取网络下行流量教程

斐讯N1盒子刷入Armbian并安装Docker拉取网络下行流量教程

一直在跑PCDN&#xff0c;目前主推八米云跟点心云&#xff0c;八米单价比点心更高&#xff0c;业务都一样&#xff0c;直播业务。 两种刷机教程我也发下。 八米云&#xff1a;点此跳转 点心云&#xff1a;点此跳转 最近各运营商对PCDN打击力度加大&#xff0c;需求拉取下行流量…
阅读更多...
活动策划秘籍：如何让企业活动引爆市场？

活动策划秘籍：如何让企业活动引爆市场？

作为一个活动策划&#xff0c;我的经验是&#xff0c;活动策划是一场精心编排的交响乐&#xff0c;每一个音符都要恰到好处。 想要做好企业活动策划工作的关键在于综合考虑多个方面&#xff0c;并确保每个环节的顺畅执行。 以下是7个关键要素&#xff0c;只要用心体会&#x…
阅读更多...
【C++】类中的六个默认成员函数(构造函数、析构函数、拷贝构造函数、复制重载函数等)

【C++】类中的六个默认成员函数(构造函数、析构函数、拷贝构造函数、复制重载函数等)

类中的六个默认成员函数 默认成员函数为了解决C语言存在的一些问题而诞生&#xff0c;默认存在于类中&#xff0c;进行某种操作时会自动调用默认成员函数&#xff0c;如想在此种操作中自动实现某种操作&#xff0c;可以手动定义此默认成员函数&#xff0c;如果手动定义则取代默…
阅读更多...
强化学习驱动的狼人游戏语言智能体战略玩法

强化学习驱动的狼人游戏语言智能体战略玩法

Language Agents with Reinforcement Learning for Strategic Play in the Werewolf Game 论文地址： https://arxiv.org/abs/2310.18940https://arxiv.org/abs/2310.18940 1.概述 在AI领域，构建具备逻辑推理、战略决策以及人类沟通能力的智能体一直被视为长远追求。大规模语…
阅读更多...
Echarts 取消或改变鼠标移上效果

Echarts 取消或改变鼠标移上效果

文章目录 问题分析解决补充：去掉鼠标移上去变小手问题 鼠标移动前 鼠标移动后 分析 鼠标一移上去老闪（显示浮框信息和图变大了） 解决 hoverAnimation:false即可解决 series: [{hoverAnimation:false,name:
阅读更多...
从微分方程组构建 bbr 模型

从微分方程组构建 bbr 模型

描述分析 bbr 的文字自 2016 年底起至今从空白到泛滥&#xff0c;我自己在期间贡献了不少&#xff0c;本文又是一篇&#xff0c;但不同的是&#xff0c;本文尝试用闭环的数学模型给出一个 bbr 的全貌&#xff0c;顺便和 aimd 做对比。 先看带宽特性 bw(t)&#xff0c;设瓶颈带…
阅读更多...
力扣 hot100 -- 动态规划（下）

力扣 hot100 -- 动态规划（下）

目录 &#x1f4bb;最长递增子序列 AC 动态规划 AC 动态规划(贪心) 二分 &#x1f3e0;乘积最大子数组 AC 动规 AC 用 0 分割 &#x1f42c;分割等和子集 AC 二维DP AC 一维DP ⚾最长有效括号 AC 栈 哨兵 &#x1f4bb;最长递增子序列 300. 最长递增子序列…
阅读更多...
数据结构JAVA

数据结构JAVA

1.数据结构之栈和队列 栈结构 先进后出 队列结构 先进先出 队列 2.数据结构之数组和链表 数组结构 查询快、增删慢 队列结构 查询慢、增删快 链表的每一个元素我们叫结点 每一个结点都是独立的对象
阅读更多...
最新文章

Copyright @ 2022~2023