【数据结构】—带头双向循环链表的实现(完美链表)

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

前言

链表结构一共有八种形式,在前面的文章里已经讲完了不带头单向非循环链表的实现,但是我们发现该链表实现尾插与尾删时比较麻烦,要先从头节点进行遍历,找到尾节点,时间复杂度为O(N),而本次所讲的带头双向循环单链表,则可以直接找到尾节点。

【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言
虽然该链表看起来特别复杂,但实际上真正实现起来很简单,并且用起来真的超爽,还能拿来吹吹牛皮。唬一唬一知半解的外行人。

链表的实现

typedef int LTDataType;//类型重命名
typedef struct ListNode
{
	LTDataType _data;//数据
	struct ListNode* _next;//指向下一个节点的指针
	struct ListNode* _prev;//指向前一个节点的指针
}ListNode;

新节点的创建

这里由于后面的插入都需要进行创建新节点,所以我们把它写成一个函数,后面进行插入操作的时候,直接调用即可。这里没什么技术含量。直接malloc即可

ListNode* BuyListNode(LTDataType x)
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	phead->_data = x;
	phead->_next = NULL;
	phead->_prev = NULL;
	return phead;
}

链表初始化

空表状态下应该是如下图这样的,因为它是带头的循环链表,所以第一个节点不用来存储有效数据。它的next与prev都指向自己就说明该链表是空表。
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言

ListNode* InitListNode()
{
	ListNode* phead = BuyListNode(-1);//这里的-1不是有效数据
	phead->_next = phead;
	phead->_prev = phead;
	return phead;
}

尾插与尾删

尾插

尾插首先要找到尾节点,这里的尾节点很容易找到,就是头节点的prev指向的节点。如下:
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言
这里的尾插也满足空表情况下进行尾插。所以该代码没问题

代码

void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);//新节点创建
	ListNode* tail = pHead->_prev;//找到尾节点
	tail->_next = newnode;//尾节点连接新节点
	newnode->_prev = tail;//新节点的prev与尾节点连接
	pHead->_prev = newnode;//头节点的prev指向新节点
	newnode->_next = pHead;//新节点的next指向头节点,至此,新节点成了为节点
}

尾删

尾删的实现也很简单,找到尾节点即可,再让尾节点的前一个节点与头节点连接,最后释放尾节点即可。如下:
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言
这里要注意的就是空表情况下是不可以继续删除的。

代码

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next!=pHead);//空表情况下不能继续删
	//找尾
	ListNode* tail = pHead->_prev;
	//记录尾部前一个节点
	ListNode* tailprev = tail->_prev;
	tailprev->_next = pHead;
	pHead->_prev = tailprev;
	//释放尾部
	free(tail);
}

测试

//链表初始化+尾插尾删
void ListNodeTest1()
{
	//初始化
	ListNode* phead=InitListNode();
	//尾插
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPushBack(phead, 5);
	ListPrint(phead);//1 2 3 4 5
	//尾删
	ListPopBack(phead);
	ListPopBack(phead);
	ListPopBack(phead);
	ListPrint(phead);//1 2
	//ListPopBack(phead);
	//ListPopBack(phead);
	//ListPopBack(phead);
	//ListPrint(phead);//error
}

头插与头删

头插

头插的实现在这里也很简单,先找到有效节点的头节点(即PHead的next指向的第一个节点),然后将新节点的next指向该节点,该节点的prev指向新节点,再让PHead的next指向新节点,新节点的prev指向PHead即可。(看起来可能有些乱,但是画图就特别容易理解)
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言

代码

//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//找到头节点
	ListNode* first = pHead->_next;
	ListNode* newnode = BuyListNode(x);//新节点创建
	//连接
	newnode->_next = first;
	first->_prev = newnode;
	pHead->_next = newnode;
	newnode->_prev = pHead;
}

头删

头删的实现与尾删异曲同工,找到有效节点的头节点,保存下一个节点,将PHead与之连接,然后再释放有效节点的头节点即可。
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言
这里依然要注意,空表情况不能进行删除

代码

void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next != pHead);//
	//找到头节点以及头节点后面的节点
	ListNode* first = pHead->_next;
	ListNode* second = first->_next;
	//进行连接
	pHead->_next = second;
	second->_prev = pHead;
	free(first);//释放
}

测试

void ListNodeTest2()
{
	//初始化
	ListNode* phead = InitListNode();
	//头插
	ListPushFront(phead, 1);
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);
	ListPrint(phead);//5 4 3 2 1
	//头删
	ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPrint(phead);// 2 1
	//ListPopFront(phead);
	//ListPopFront(phead);
	//ListPopFront(phead);
	//ListPrint(phead);// error
}

查找数据

这里进行查找数据,依然还是遍历整个链表即可。没啥可说的,如下:

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	//遍历
	while (cur != pHead)
	{
		if (cur->_data == x)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

在任意位置的插入与删除

pos位置插入

这里与头插的操作相比,两者其实也没啥区别。头插是找有效节点的头节点,在这里我们把pos看作该节点,把pos的prev指向的节点看作是PHead节点,这样的话,原理就与头插相同了。
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	//pos前面的节点
	ListNode* posprev = pos->_prev;
	//新节点
	ListNode* newnode = BuyListNode(x);
	//连接即可
	posprev->_next = newnode;
	newnode->_prev = posprev;
	newnode->_next = pos;
	pos->_prev = newnode;
}

pos位置删除
原理也是与头删相似,只要画图即可理解。这里就不一一进行解析了,大家根据代码画图纸就行。不过需要注意的是,空表不可进行删除。

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->_prev->_next = pos->_next;
	pos->_next->_prev = pos->_prev;
	free(pos);
}

链表的销毁

这里的销毁也是需要进行遍历链表,先保存下一个链表,再释放当前链表。将有效节点销毁后,再将PHead销毁。
【数据结构】—带头双向循环链表的实现(完美链表),数据结构,链表,数据结构,c语言

代码

void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		//找到cur后面的节点
		ListNode* curnext = cur->_next;
		free(cur);//释放
		cur = curnext;
	}
	//释放pHead
	free(pHead);
}
 

测试

//双向链表查找、任意位置插入、删除
ListNodeTest3()
{
	ListNode* phead = InitListNode();
	ListPushFront(phead, 1);
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);
	//查找
	ListNode* pos = ListFind(phead, 2);
	//pos->_data = 50;
	//ListPrint(phead);// 5 4 3 50 1
	// 双向链表在pos的前面进行插入
	ListInsert(pos, 0);
	ListPrint(phead);// 5 4 3 0 2 1

	//删除pos位置
	ListErase(pos);
	ListPrint(phead);// 5 4 3 0 1
	//链表销毁
	ListDestory(phead);
}

总结

该链表用起来真的很爽,能直接找到头尾节点,并且因为有头的存在,就不需要考虑是否为空表的情况下的插入,就不用改变PHead,所以就不用像之前的单链表一样,得传二级指针。真的是链表中的完美存在,不过在进行删除操作时,一定要考虑空表情况下不可进行删除。因此要加个assert进行断言。文章来源地址https://www.toymoban.com/news/detail-824585.html

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

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

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

相关文章

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

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

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

    之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~ 结构最复杂 ,一般用在单独存储数据。 实际中使用的链表数据结构,都是带头双向循环链表 。另外这个结构虽然结构复杂,但是使用代码实现以后会发现 结构会带来很多优势 ,实现反而简单

    2024年02月10日
    浏览(44)
  • 【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(45)
  • 数据结构: 线性表(带头双向循环链表实现)

    之前一章学习了单链表的相关操作, 但是单链表的限制却很多, 比如不能倒序扫描链表, 解决方法是在数据结构上附加一个域, 使它包含指向前一个单元的指针即可. 那么怎么定义数据结构呢? 首先我们先了解以下链表的分类 链表的结构非常多样, 以下情况组合起来就有 8 中链表

    2024年02月14日
    浏览(39)
  • 数据结构之双向带头循环链表函数功能实现与详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2.带头双向循环链表函数实现 3.总结         在前面我

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

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

    2024年01月17日
    浏览(76)
  • 数据结构入门(C语言版)线性表带头双向循环链表接口实现

    在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。 如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客: 线性表中链表介绍及无头单向非循环链

    2023年04月12日
    浏览(45)
  • 追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

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

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

    2024年01月16日
    浏览(60)
  • 数据结构——带头双向循环链表

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

    2024年02月09日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包