数据结构学习分享之双向链表详解-Toy模板网

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

1.前言

💓博主CSDN:杭电码农-NEO💓🎉🎉🎉

⏩专栏分类:数据结构学习分享(持续更新中🫵)⏪🎉🎉🎉

我们上一期说到,两链表中有两个最常用的结构,一个是最简单的无头不循环单向链表,还有一个就是 结构相对比较复杂的带头双向循环链表 ,我们这一章节就来分享双向带头循环链表的具体实现:

要看所有代码的朋友: 💯 我的码云放在了最后 💯
数据结构学习分享之双向链表详解

2. 结构分析

与我们上一章讲的单链表不同,这里双向带头循环链表的结构要复杂一点,主要需要注意这几个点:

定义结构体时,单链表只需要定义一个指针next,双链表需要定义额外一个指针:prev用来指向上一个节点

带头(带哨兵位)的链表在初始化时就要给哨兵位开辟一份空间,并且哨兵位不存储数据,第一个节点要链接在哨兵位的下一个位置

循环的链表的尾节点的next不能指向NULL,要指向第一个节点,形成循环结构

我们在进行插入删除的时候可以不传二级指针!因为我们拥有了哨兵位作为我们指针指向的第一个位置,并且哨兵位是不会改变的!

不循环的链表判断尾节点是cur->next == NULL时,然而循环的带头链表判断尾节点是cur->next==head时,这里的head指的是哨兵位

3. 双链表的实现

单链表我们使用的名字是SList,意为single list 就是单个的意思,这里我们直接用List表示双链表

3.1 初始化结构

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
typedef int LTDateType;//随时可以改变类型

typedef struct ListNode
{
	LTDateType data;
	struct ListNode* prev;//指向上一个节点
	struct ListNode* next;//指向下一个节点
}LTNode;//简化名字

3.2 初始化函数

在我们写初始化函数之前我们要先明白一点,那就是当链表为空时,我们哨兵位的next和prev都指向自己本身!

数据结构学习分享之双向链表详解

LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//为哨兵位开辟一个节点
	phead->next = phead;
	phead->prev = phead;
	return phead;//将phead返回后,在test.c文件中赋值给结构体指针
}

void TestList1()
{
	LTNode* plist = ListInit();//plist里面存储一个哨兵位
}

3.3 尾插函数

我们说存储数据的结构都离不开增删查改,这里我们定义的双向带头循环链表进行增删查改是很简单的

void ListPushBack(LTNode* phead, LTDateType x)//尾插
{
	assert(phead);
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为插入的数据开辟空间
	if (newnode == NULL)//这个if语句是为了判断我们的动态开辟空间有没有失败
	{
		printf("fail");
		exit(-1);
	}
	newnode->data = x;//将数据x给上
	LTNode* tail = phead->prev;//这里也可以不定义tail,直接用phead->prev表示尾
    tail->next = newnode;//尾节点与新节点相连
	newnode->prev = tail;//新的尾节点的prev与旧的尾相连
	newnode->next = phead;//新的尾节点与头相连形成循环
	phead->prev = newnode;
}

我们发现当我们定义链表结构为双向带头循环链表时,插入数据是很方便的,只需要判断好链接关系就可以了,而我们之前的单链表还需要判断链表为空的情况,这种情况要拿出来特殊处理,但是这个地方当链表为空时也是没有问题的!

数据结构学习分享之双向链表详解

3.4 尾删函数

我们有了之前的基础后,直接上代码!

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//不能把哨兵为给删除了
	LTNode* tail = phead->prev;
	LTNode* prev = tail->prev;//后面就处理链接关系
	free(tail);
	tail = NULL;
	prev->next = phead;
	phead->prev = prev;
}

值得注意的是,这里的assert(phead->next!=phead)是当我们的phead->next等于自己本身时,代表我们链表中已经没有数据了,只剩下一个哨兵位了.这时需要断言报错 👍👍👍

3.5 头插函数

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//只要是插入数据就需要开辟空间
	newnode->data = x;
	LTNode* next = phead->next;//头插相当于就是插入在哨兵位后面
	phead->next = newnode;//注意链接关系别写漏就没问题
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

同样的,当我们链表中没有数据时,这时的头插也是没有问题的,这里我就不做过多说明

3.6 头删函数

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
	next = NULL;
}

头删和尾删一样,不能把哨兵位一起删了,并且需要注意一点,我们的free不能太早使用,不然我们就找不到我们next的next和next的prev了,所以我们要把所有链接关系全部修改完之后,才能把next的空间给释放掉

3.7 销毁链表

void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)//释放掉所有的数据空间
	{
		LTNode* next = cur->next;//这里需要定义一个next指针,因为我们把cur给释放掉后就找不到cur->next的了
		free(cur);
		cur = next;
	}
	free(phead);//最后将哨兵位也释放掉,然后置空
	phead = NULL;
}

3.8 其他函数

这里我给出几个除了头插头删,尾插尾删的函数.

Find函数:返回与x值相同的节点

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

Insert函数:在pos位置之前插入数据

void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
	prev->next = newnode;
}

Erase函数:删除pos位置的节点

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
    free(pos);
	pos = NULL;
}

4. 缓存利用率

我们上一章总结顺序表和链表的区别的时候提到:顺序表的缓存利用率高,链表的缓存利用率低,那么到底什么是缓存利用率?这里我给大家大致提一下:我们的计算器存在很多存储方式:

数据结构学习分享之双向链表详解

我们在数组中开辟空间和在链表上开辟空间时,这种缓存的命中是不一样的,有兴趣了解的朋友具体的细节可以参考这篇文章CPU缓存知识.

5. 总结

我们关于链表的知识的分享就要告一段落了,但是链表这一章节虽然只有两次分享,但是它在诸多面试题中考察的概率是很高的,特别是单链表,因为我们知道单链表是有很多缺陷的,所以在校招和很多OJ题中,单链表考察的地方非常之多,建议多刷刷题找找思路,我的专栏单链表OJ中也总结了不少OJ题的思路以及衍生问题,有兴趣的朋友可以来指导指导.

💕 我的码云:gitee-杭电码农-NEO💕文章来源地址https://www.toymoban.com/news/detail-439312.html

🔎 下期预告:栈的实现 🔍

到了这里，关于数据结构学习分享之双向链表详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！