首页 > 其他分享 >数据结构入门 — 链表详解_双向链表

数据结构入门 — 链表详解_双向链表

时间:2023-11-10 13:05:16浏览次数:40  
标签:next 链表 LTNode phead 双向 数据结构 节点 详解


前言

数据结构入门 — 双向链表详解*
关注博主,后期持续更新系列文章
文章末尾有源码
*****感谢观看,希望对你有所帮助*****


系列文章

第一篇:数据结构入门 — 链表详解_单链表
第二篇:数据结构入门 — 链表详解_双向链表
第三篇:数据结构入门 — 链表详解_循环链表



文章目录

  • 前言
  • 系列文章
  • 什么是双向链表
  • 概念与结构(图文)
  • 双向链表与单链表的区别
  • 带头双向循环链表接口实现(代码演示)
  • 1. 动态存储结构
  • 双向链表打印
  • 增删查改接口
  • 双向链表销毁
  • 五、所有文件代码
  • 1. Gitee链接
  • 总结



什么是双向链表

双向链表(Doubly Linked List)是一种链表数据结构,它的每个节点都含有两个指针,一个指向前一个节点,一个指向后一个节点。相比较于单向链表,双向链表可以双向遍历,即可以从头到尾或从尾到头遍历链表。在双向链表中,每个节点包含两个指针域和一个数据域。其中,一个指针指向前驱节点,另一个指针指向后继节点。这两个指针使得双向链表的插入、删除等操作不需要像单向链表那样需要遍历整个链表来寻找前驱节点,提高了链表的操作效率。

概念与结构(图文)

数据结构入门 — 链表详解_双向链表_c++


带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

双向链表与单链表的区别

双向链表和单链表是两种不同的链表结构。

单向链表是一种链表,在每个节点中包含指向下一个节点的指针。这意味着在单向链表中,节点只能从头开始遍历到尾部。在单向链表中,每个节点只存储指向下一个节点的指针,而不存储指向前一个节点的指针。

双向链表是一种链表,在每个节点中包含指向下一个节点和前一个节点的指针。这意味着在双向链表中,节点可以被从头到尾或从尾到头遍历。在双向链表中,每个节点存储指向前一个节点和下一个节点的指针。

因此,双向链表可以更方便地进行双向遍历,但是需要更多的内存空间来存储每个节点的两个指针。相比之下,在单向链表中,只需要一个指针来指向下一个节点,因此内存占用量更小。

带头双向循环链表接口实现(代码演示)

带头+双向+循环链表增删查改实现

1. 动态存储结构

typedef int STDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	STDataType data;
}LTNode;

双向链表打印

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<->");
	//跳过哨兵位
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

增删查改接口

根据增删查改顺序编排双向链表头插:

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

}

双向链表尾插:

//尾插
void LTPushBack(LTNode* phead, STDataType x)
{
	assert(phead);
	
	LTNode* newnode = BuyLTNode(x);
	//找到最后一个
	LTNode* tail = phead->prev;
	
	
	newnode->prev = tail;
	tail->next = newnode;
	

	newnode->next = phead;
	phead->prev = newnode;
}

双向链表头删:

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;

}

双向链表尾删:

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;

	free(tail);
	
	phead->prev = tailprev;
	tailprev->next = phead;

}

查找:

LTNode* LTFind(LTNode* phead, STDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

在指点位置插入:

void LTInsert(LTNode* pos, STDataType x)
{
	LTNode* newnode = BuyLTNode(x);
	LTNode* posprev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	posprev->next = newnode;
	newnode->prev = posprev;

}

在指点位置删除:

// 把pos删除
void LTErase(LTNode* pos)
{
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);
	posprev->next = posnext;
	posnext->prev = posprev;
}

双向链表销毁

void LTDestory(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

五、所有文件代码

1. Gitee链接

***查看所有代码*** 点击右边蓝色文字 DuckBro Gitee 代码仓库


总结

带头双向循环链表的基本概念和常见操作。带头双向循环链表是一种特殊的双向链表,它多了一个头节点和一个尾节点,并且首尾相连形成一个环。

这样可以实现循环遍历链表。在带头双向循环链表中,插入、删除节点等操作都有特殊处理方式。带头双向循环链表在实际应用中比较常见,如操作系统中的进程管理、音乐播放器中的播放列表等。


如这篇博客对大家有帮助的话,希望 三连 支持一下 !!! 如果有错误感谢大佬的斧正 如有 其他见解发到评论区,一起学习 一起进步。


标签:next,链表,LTNode,phead,双向,数据结构,节点,详解
From: https://blog.51cto.com/u_16225555/8296010

相关文章

  • 利用快慢指针,求链表的中间结点,判断链表是否是环形链表
    前言(1)在学习数据结构链表部分的时候,老师给出了几个题目。其中两个题目采用了快慢指针的技术,感觉有意思,于是写一篇博客记录一下。快慢指针(1)我们先来介绍一下快慢指针技术。这个说起来其实很简单,就是龟兔赛跑问题。(2)兔子跑的比乌龟快,我们可以利用这个特性,来解决一些实际按理。求链表......
  • OpenGL 投光物详解
    1.投光物继续上一节的流程,到目前为止,我们介绍的都是点光源。但是现实世界中,光源的类型却要相对复杂一些。大概会有这么几种形式:定向光、点光源、聚光等等。 2.定向光当一个光源处于很远的地方时,来自光源的每条光线就会近似于互相平行。这点很好理解,生活中我们的太阳光,就可以......
  • 神经网络入门篇:详解计算一个神经网络的输出(Computing a Neural Network's output)
    一个神经网络的输出首先,回顾下只有一个隐藏层的简单两层神经网络结构:图1.3.1其中,\(x\)表示输入特征,\(a\)表示每个神经元的输出,\(W\)表示特征的权重,上标表示神经网络的层数(隐藏层为1),下标表示该层的第几个神经元。这是神经网络的符号惯例,下同。神经网络的计算关于神经网络是怎......
  • 【django框架】共4大模块50页md学习文档 第5篇:django的请求与响应详解
    当你考虑开发现代化、高效且可扩展的网站和Web应用时,Django是一个强大的选择。Django是一个流行的开源PythonWeb框架,它提供了一个坚实的基础,帮助开发者快速构建功能丰富且高度定制的Web应用整套Django笔记直接地址:请移步这里共10章,31子模块请求与响应学习目标掌握r......
  • mysql常用函数详解
    1.Mysql内置函数分类及使用范围数学函数:这类函数只要用于处理数字。这类函数包括绝对值函数、正弦函数、余弦函数、获取随机数函数等。字符串函数:这类函数主要用于处理字符串。其中包括字符串连接函数、字符串比较函数、将字符串的字母变成小写或大写字母的函数、获取子串的......
  • 自己写数据结构
    #include<iostream>#include<array>template<typenameT,size_tS>classArray{private: Tm_data[S];public: constexprintSize()const{ returnS; } T&operator[](intindex){returnm_data[index];} constT&operator[](in......
  • 链表
    链表单链表插入一个节点的伪代码算法:创建一个新节点newNode,将要插入的数据data存储在newNode中如果链表为空,则将newNode设为头节点,并将next指向NULL如果链表不为空,则将newNode插入到链表的末尾遍历链表,找到最后一个节点lastNode将lastNode的next指向newNode将newNode的n......
  • 一对多数据关系处理利器:JVS子表格组件详解
    在数字化时代,表单已经成为企业、机构和个人收集、整理、分析数据的重要工具。然而,随着数据复杂性的增长,传统的单一表单往往难以满足需求。JVS低代码表单引擎中子表格允许在主表单中嵌套另一个子表数据,使得数据的收集和组织更加有序、高效。尤其在处理多对一或多对多的关系数据时,如......
  • 高级数据结构学习笔记
    0.普适技巧动态开点:节省空间。标记永久化:分块的块标记本质就是这个。可以节省空间。1.区间最值&历史区间最值link2.二维线段树二维区间静态:二维ST表二维前缀动态:二维树状数组二维区间动态:二维线段树例题:LuckandLove、P3157[CQOI2011]动态逆序......
  • 云主机使用的硬盘类型及对应的存储类型详解
    本文分享自天翼云开发者社区《云主机使用的硬盘类型及对应的存储类型详解》,作者:不知不觉随着云计算的普及,云主机已成为企业和个人用户的重要选择。云主机为用户提供了灵活、可伸缩的计算资源,并且具有高可用性、高可扩展性以及易于管理的特点。在云主机的使用过程中,硬盘类型和存储......