玩转带头双向链表——【数据结构】

这篇具有很好参考价值的文章主要介绍了玩转带头双向链表——【数据结构】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

玩转带头双向链表——【数据结构】,数据结构,链表

W...Y的主页

今天我们接着来说数据结构——带头双向链表

目录

带头双向链表的实现

结构体的创建

初始化兵创建哨兵节点

释放链表所以内容 

打印链表函数

尾插

尾删

头插

​编辑

头删

计数函数实现

查找数据相应位置函数

在pos位置之前插入 

在pos位置删除 

顺序表与链表的差别


玩转带头双向链表——【数据结构】,数据结构,链表

带头双向链表(Doubly Linked List with Head)相对于普通的双向链表,添加了一个头节点(head node),头节点不存储任何实际的数据,仅用于指示链表的起始位置。下面是带头双向链表的一些优点:

  1. 链表操作方便:带头双向链表提供了直接访问链表头部和尾部的能力,使得链表的插入、删除等操作更加高效。你可以通过头节点快速插入第一个元素,也可以通过尾节点快速插入新元素。同时,由于链表的双向性,你可以轻松地在链表中的任意位置进行插入和删除操作。

  2. 遍历灵活性:带头双向链表可以从头到尾或从尾到头两个方向遍历。这意味着你可以根据需要选择合适的遍历方式,无论是从前向后还是从后向前遍历链表,都能方便地获取元素。

  3. 反向查找:带头双向链表的一个重要优点是可以通过后向链接(back link)从任意节点快速访问该节点的前一个节点。这使得在链表中进行反向查找变得高效。与单链表相比,带头双向链表的反向查找时间复杂度从O(n)降至O(1),这对某些应用程序可能非常重要。

  4. 方便的删除节点:在带头双向链表中,删除一个节点不需要访问其前一个节点,只需修改当前节点的前后链接即可。这样,节点的删除操作变得更为方便和高效。

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

带头双向链表的实现

结构体的创建

typedef int LTDataType;

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

创建结构体使用typedef将其改名LTNode方便使用,创建next和prev节点用来保存下一个节点与上一个节点。

初始化兵创建哨兵节点

我们创建哨兵位时,可以在data中间增加-1,创建好后将next与prev全部指向自己。但是这个功能与怎加节点函数内容及其相似,所以我们可以先创建节点函数,然后再初始化哨兵位时将其调用即可,防止冗余现象。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->prev = NULL;
	return node;
}
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

 我们再创建好两个函数时,让LTInit函数去调用BuyLTNode函数,将哨兵位初始化即可。

释放链表所以内容 

因为链表使用realloc开辟的空间全部在堆区,所以必须将链表开辟的空间全部释放,防止内存泄漏。

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

打印链表函数

在打印链表时,我们要将次链表与单链表区分。单链表只需找到尾NULL即可停止,而双向链表的尾部指向哨兵位,所以我们可以换一种方法进行检测。

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("phead<->");
	while (cur != phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
}

我们创建一个遍历指针cur,让cur = phead->next指向哨兵位下一个节点。然后进行遍历,如果遍历返回到哨兵位phead停止即可。

尾插

玩转带头双向链表——【数据结构】,数据结构,链表

尾插相对于单链表也非常方便,不用遍历找尾节点,只需要访问phead的prev即可找到尾节点。 

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

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

玩转带头双向链表——【数据结构】,数据结构,链表

尾删

我们首先得检测phead哨兵位是否为空,如果链表为空我们也不能正常进行删除,所以我们得继续判断phead->next != phead。自己的下一个节点不能指向自己。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);

}

删除就非常简单,访问最后一个节点记作tail,将phead连接尾节点的地址切换成尾节点的上一个节点,然后将尾节点上一个节点的next换成哨兵位地址,free掉tail尾节点即可。 

头插

头插与尾插原理基本相同,只需要将哨兵位的内容进行改变即可。

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	/*newnode->next = phead->next; 
	phead->next->prev = newhead;
	phead->next = newhead;
	newhead->prev = phead;*/
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	first->prev = newnode;
	newnode->next = first;
}

玩转带头双向链表——【数据结构】,数据结构,链表

 我们可以参照上述代码进行头插,分别有两种方法。第一种(已注释)是不创建任何指针变量进行交换替代,第二种(未注释)即创建变量进行交换。第一种方法再交换次序上必须严谨,先进行尾节点的交互,再进行首节点的交互,否则会交换失败出现错误数据。

头删

在删除时,务必检测链表是否为空,链表是否只有哨兵位方可进行删除操作。

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;
}

计数函数实现

当我们录入数据量过大时,为了方便计数所创建的函数。‘

int LTsize(LTNode* phead)
{
	assert(phead);
	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

这里只需遍历链表种的每一个节点直到返回到哨兵位即可。

查找数据相应位置函数

当操作人员想知道某个数据在链表中的位置并进行操作时,我们即可调用此函数来返回相应数据所在节点的地址。

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

这里我们使用暴力查找的算法进行整组链表搜索,找到对应数据即可返回。

在pos位置之前插入 

这里我们就需要与查找位置函数进行联动配合进行调用。

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

这里其实与头插尾插原理一样,所以我们也可以用此函数进行头插尾插,只需将pos参数传入正确,分别为phead->next(头插)、phead->prev(尾插)。

在pos位置删除 

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);
	posprev->next = posnext;
	posnext->prev = posprev;
}

这里也是与头删尾删原理相同,只需将参数传入正确即可变成头删和尾删。

顺序表与链表的差别

玩转带头双向链表——【数据结构】,数据结构,链表

所以在不同情况下选择不同的数据结构时是很关键的,我们需要足够了解其中的差别与优势,才能满足各种问题下不同的需求。文章来源地址https://www.toymoban.com/news/detail-634508.html

到了这里,关于玩转带头双向链表——【数据结构】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】链表:带头双向循环链表的增删查改

    本篇要分享的内容是带头双向链表,以下为本片目录 目录 一、链表的所有结构 二、带头双向链表 2.1尾部插入 2.2哨兵位的初始化 2.3头部插入 2.4 打印链表 2.5尾部删除 2.6头部删除  2.7查找结点 2.8任意位置插入 2.9任意位置删除  在刚开始接触链表的时候,我们所学仅仅所学的

    2024年02月05日
    浏览(91)
  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(45)
  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(78)
  • 数据结构:链表基础OJ练习+带头双向循环链表的实现

    目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口 3.链表的打

    2024年02月02日
    浏览(51)
  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(61)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

    2024年02月08日
    浏览(64)
  • 带头双向循环链表--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏:🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的 点赞 👍和 关注 💖,支持一

    2024年02月01日
    浏览(55)
  • 数据结构-带头双向循环链表

    前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用

    2023年04月09日
    浏览(49)
  • 数据结构——带头双向循环链表

    在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针,目的在与存储前一个节点的地址,便于将整个链表连在一起。 动态申请内存结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断

    2024年02月09日
    浏览(42)
  • 【数据结构】带头双向循环链表

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年01月16日
    浏览(78)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包