1. 编程号首页

C/C++数据结构（三） —— 双向带头循环链表

编程小号 • • 未分类

C/C++数据结构（三） —— 双向带头循环链表【数据结构系列】链表之双向带头循环链表的基本操作

在这里插入图片描述

文章目录

前言

在前两篇文章中，我们学习了 顺序表（数组） 和 单向不带头非循环 链表。
 
链接如下：
 
C/C++数据结构（一） —— 数组
 
C/C++数据结构（二） —— 单链表
 
那么今天，将要学习链表的第三种 双向带头循环链表。

链表的分类

在前面也介绍过链表的基本情况，但是还是会有朋友分不清链表到底有哪几种，所以今天再来笼统的介绍一下。

其实 链表 一共分为 8 种类型，分别如下：
在这里插入图片描述

🍑 单链表

通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是 数据域，一个是 指针域（存放指向下一个节点的指针），最后一个节点的指针域指向 NULL（空指针的意思）。

链接的入口节点称为链表的头结点也就是 head。

如图所示：
在这里插入图片描述

🍑 双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示：
在这里插入图片描述

🍑 循环链表

循环链表，顾名思义，就是链表 首尾相连。

循环链表可以用来解决 约瑟夫环问题。
在这里插入图片描述

双向带头循环链表

既然单链表也可以有循环链表，那么双向链表也不例外。

双向链表的 循环带头结点 的空链表如下图所示👇
在这里插入图片描述

🍑 头结点的作用

定义：

头结点 也被称为 哨兵结点，可以用来简化边界条件。
 
它是一个附加的链表结点，该 结点 作为第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。
 
也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。

作用：

说了这么多，那它到底有什么用呢？
 
在很多时候，我们处理某个节点需要用到它的前驱节点。
 
比如删除链表的某个节点，对于没有哨兵的单链表，当待删除的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。
 
而如果有哨兵节点，则第一个节点的处理方式与其他节点相同，可以统一进行处理。

注意：本篇文章中，统一把 头结点 称为 哨兵结点。

非空的循环带头结点的双向链表，如下图所示👇
在这里插入图片描述

由于这是双向链表，那么对于链表中的某一个节点 p，它的后继的前驱是谁？当然还是它自己。

比如，在上图的双向循环链表中，节点 B 的前驱的后继，还是节点 B。

即：p->next->prev == p == p->prev->next。（prev 表示 前驱指针，next 表示 后继指针）。

这就好比：坐动车时，北京的下一站是天津，那么北京的下一站的前一站是哪里？哈哈哈，当然还是北京。

1. 初始化链表

双向链表是单链表中扩展出来的结构，所以它的很多操作是和 单链表 相同的，甚至理解起来比单链表更简单。

首先，还是先定义一个结点类型，与单向链表相比，双向链表的结点类型中需要多出一个 前驱指针，用于指向前面一个结点，实现双向。

📝 代码示例

typedef int LTDataType; // 存储的数据类型

typedef struct ListNode
{ 
   
	LTDataType data; // 数据域
	struct ListNode* next; // 后驱指针
	struct ListNode* prev; // 前驱指针
}LTNode;

在初始化之前，先申请一个 带哨兵位 的头结点，头结点的前驱和后继指针都指向自己，使得链表一开始便满足循环。然后再用一个 初始化函数 对链表进行初始化。
在这里插入图片描述

📝 代码示例

//增加一个节点
LTNode* BuyLTNode(LTDataType x) { 
   
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL) { 
   
		printf("malloc fail\n");
		exit(-1); // 终止程序
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

//双向链表初始化
LTNode* ListInit() { 
   
	LTNode* phead = BuyLTNode(0); // 申请一个头结点，不存储有效数据
	/*起始时只有头结点，让它的前驱和后继都指向自己*/
	phead->next = phead;
	phead->prev = phead;
	return phead; // 返回头结点
}

2. 打印链表

打印 双向链表 ，是从头结点的后一个结点处开始，向后遍历并打印，直到遍历到头结点处时便停止。

📝 代码示例

//双向链表打印
void ListPrint(LTNode* phead) { 
   
	assert(phead);

	LTNode* cur = phead->next; // 从头结点的后一个结点开始打印
	while (cur != phead) { 
    // 当cur指针指向头结点时，说明链表全部打印完成
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

注意：第一个是 头结点，也被称为 带哨兵位 的结点，它是用来 站岗 的，所以不需要打印。

3. 查找元素

给定一个值，在链表中寻找与该值相同的结点，若找到了，则返回结点地址；

若没有找到，则返回空指针（NULL）。

📝 代码示例

//双向链表查找
LTNode* ListFind(LTNode* phead, LTDataType x) { 
   
	assert(phead);

	LTNode* cur = phead->next; // 从头结点的后一个结点开始查找
	while (cur != phead) { 
    // 从头结点的后一个结点开始查找
		if (cur->data == x) { 
   
			return cur; // 返回目标结点的地址
		}
		cur = cur->next;
	}
	return NULL; // 没有找到目标结点
}

4. 插入结点

双向链表的插入操作分为 3 种情况：

（1）头插
（2）尾插
（3）在指定 pos 位置之前插入

🍑 头插

进行头插时，需要申请一个新的结点，将 新结点 插入到 头结点 与 头结点的后一个结点 之间即可。
在这里插入图片描述

动图演示👇
在这里插入图片描述

📝 代码示例

//双向链表头插
void ListPushFront(LTNode* phead, LTDataType x)
{ 
   
	assert(phead);

	LTNode* newnode = BuyLTNode(x); // 申请一个结点，数据域赋值为 x
	LTNode* after = phead->next; // 记录头结点的后一个结点位置
	
	/*建立新结点与头结点之间的双向关系*/
	phead->next = newnode;
	newnode->prev = phead;
	
	//建立新结点与beHind结点之间的双向关系
	newnode->next = after;
	after->prev = newnode;
}

注意：第一个是 哨兵结点，所以不能在它的前面插入。

🍑 尾插

尾插也是一样，申请一个新结点，将新结点插入到头结点和头结点的前一个结点之间即可。

因为链表是循环的，头结点的前驱指针直接指向最后一个结点，所以我们不必遍历链表找尾。
在这里插入图片描述

动图演示👇
在这里插入图片描述

📝 代码示例

//双向链表尾插
void ListPushBack(LTNode* phead, LTDataType x) { 
   
	assert(phead);

	LTNode* tail = phead->prev; //尾节点就是头节点的前驱指针
	LTNode* newnode = BuyLTNode(x); // 申请一个结点，数据域赋值为x
	
	/*建立新结点与头结点之间的双向关系*/
	newnode->next = phead;
	phead->prev = newnode;
	
	//建立新结点与tail结点之间的双向关系
	tail->next = newnode;
	newnode->prev = tail;
}

🍑 指定位置插入

这里的指定插入，是在指定的 pos 位置的 前面 插入结点。

这里 pos 是指定位置的 地址，那么如何得到这个地址呢？很简单，需要用到上面的 查找函数。

然后，我们只需申请一个新结点插入到 指定位置结点 和其 前一个结点 之间即可。

动图演示👇
在这里插入图片描述

📝 代码示例

//双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x) { 
   
	assert(pos);

	LTNode* newnode = BuyLTNode(x); // 申请一个结点，数据域赋值为x
	LTNode* posPrev = pos->prev; // 记录 pos 指向结点的前一个结点
	
	/*建立新结点与posPrev结点之间的双向关系*/
	posPrev->next = newnode;
	newnode->prev = posPrev;
	
	
	/*建立新结点与pos指向结点之间的双向关系*/
	newnode->next = pos;
	pos->prev = newnode;
}

🍑 插入升级

我们仔细回顾一下，刚刚写的 头插 和 尾插，有没有发现什么规律呢？

没错，头插 其实就是在 哨兵结点 的 下一个结点 插入数据，所以我们可以用上面写的 ListInsert 函数来实现。

📝 代码升级

//头插升级
void ListPushFront(LTNode* phead, LTDataType x) { 
   
	assert(phead);
	ListInsert(phead->next, x);
}

那么 尾插 呢？其实就是在 哨兵结点 的 前面 插入结点。

📝 代码升级

//尾删升级
void ListPopBack(LTNode* phead) { 
   
	assert(phead);
	ListErase(phead->prev);
}

5. 删除结点

双向链表的删除操作分为 3 种情况：

（1）头删
（2）尾删
（3）在指定 pos 位置删除

🍑 头删

头删，即释 哨兵结点 的后一个结点，并建立 哨兵结点 与 被删除结点的后一个结点 之间的双向关系即可。
在这里插入图片描述

动图演示👇
在这里插入图片描述

📝 代码示例

//双链表头删
void ListPopFront(LTNode* phead)
{ 
   
	assert(phead);
	assert(phead->next != phead);

	LTNode* after = phead->next; // 记录头结点的后一个结点
	LTNode* newAfter = after->next; // 记录after结点的后一个结点
	
	/*建立头结点与newAfter结点之间的双向关系*/
	phead->next = newAfter;
	newAfter->prev = phead;
	
	free(after); // 释放after结点
}

🍑 尾删

尾删，即释放最后一个结点，并建立 哨兵结点 和 被删除结点的前一个结点 之间的双向关系即可。
在这里插入图片描述

📝 代码示例

//双链表尾删
void ListPopBack(LTNode* phead) { 
   
	assert(phead);
	assert(phead->next != phead); //检查链表是否为空

	LTNode* tail = phead->prev; //记录头结点的前一个结点
	LTNode* newTail = tail->prev; // 记录tail结点的前一个结点

	free(tail); // 释放tail结点
	tail = NULL;
	
	/*建立头结点与newTail结点之间的双向关系*/
	newTail->next = phead;
	phead->prev = newTail;
}

🍑 指定位置删除

删除指定 pos 位置的结点，这里不是删除 pos 前面的结点，也不是删除 pos 后面的结点，而是删除 pos 地址的结点。

同样，释放掉 pos 位置的结点后，建立该结点前一个结点和后一个结点之间的双向关系即可。

动图演示👇
在这里插入图片描述

📝 代码示例

//双向链表删除pos位置的节点
void ListErase(LTNode* pos) { 
   
	assert(pos); //pos不为空

	LTNode* posPrev = pos->prev; // 记录pos指向结点的前一个结点
	LTNode* posNext = pos->next; // 记录pos指向结点的后一个结点

	free(pos); //free是把指针指向的节点还给操作系统
	pos = NULL;
	
	/*建立posPrev结点与posNext结点之间的双向关系*/
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

🍑 删除升级

同样，对于 头删 和 尾删 还是可以进行简化。

头删 实际上就是删除 哨兵结点 的 下一个结点。

📝 代码升级

//头删升级
void ListPopFront(LTNode* phead) { 
   
	assert(phead);
	assert(phead->next != NULL); //只有一个节点的时候，就别删了

	ListErase(phead->next);
}

尾删 实际上就是删除 哨兵结点 的 前一个结点。

📝 代码升级

//尾删升级
void ListPopBack(LTNode* phead) { 
   
	assert(phead);
	ListErase(phead->prev);
}

6. 链表判空

当链表的 头结点的前驱 或是 后驱 指向的是自己时，即 双向链表为空。

换句话说，当只有 哨兵结点 时，链表为空。

📝 代码示例

//双向链表判空
bool ListEmpty(LTNode* phead)
{ 
   
	assert(phead);
	return phead->next == phead; // 当链表中只有头结点时为空
}

7. 获取链表中的元素个数

获取链表中的元素个数，即遍历一次链表，统计结点的个数（哨兵结点 不纳入总数）并返回即可。

📝 代码示例

//获取链表中的元素个数
int ListSize(LTNode* phead)
{ 
   
	assert(phead);

	int count = 0; // 记录元素个数
	LTNode* cur = phead->next; // 从头结点的后一个结点开始遍历
	while (cur != phead) // 当cur指向头结点时，遍历完毕，头结点不计入总元素个数
	{ 
   
		count++;
		cur = cur->next;
	}
	return count; //返回元素个数
}

8. 销毁链表

当链表使用完以后，要进行销毁。

销毁链表，从 哨兵结点 的 后一个结点 处开始向后遍历并释放结点，直到遍历到 哨兵结点 时，停止遍历并将 哨兵结点 也释放掉。

📝 代码示例

//销毁双链表
void ListDestory(LTNode* phead) { 
   
	assert(phead);
	LTNode* cur = phead->next; // 从头结点后一个结点开始释放空间

	while (cur != phead) { 
   
		LTNode* next = cur->next; // 释放之前先保存cur的后一个结点位置
		free(cur);
		cur = next; // 把cur的下一个赋给cur
	}
	free(phead); // 最后释放哨兵结点
	phead = NULL;
}

9. 总结

疑问点：

在 单链表 这篇文章中，我们的插入、删除等操作，实参部分传的都是 链表的地址，那为什么 双向链表 不需要传 地址 呢？
 
很简单，因为我们改变的是哨兵位这个结构体，像 next、prev 这些，所以我们传的是结构体的指针；
 
单链表中，我们要改变的是 结构体的指针，所以当时传给形参的是结构体指针的地址；
 
假设单链表也加一个带哨兵位的节点，那么也可以用一级指针就解决问题；
 
但是，默认情况下，单链表是不带哨兵位的！

顺序表 与 链表 的优缺点：

优点 缺点
顺序表 1. 物理空间是连续的，方便用下标随机访问。
2. CPU高速缓存命中率会更高。		 1. 由于需要物理空间连续，空间不够需要扩容。其次扩容机制还存在一定的空间浪费。
2. 头部或者中部插入、删除、挪动数据效率低 O(N)。
链表 1、按需申请和释放空间。
2. 任意位置插入、删除数据效率高 O(1)。		 1. 不支持下标的随机访问。有些算法不适合在它上面进行。如：二分、排序等

接口函数贴图

最后附上一张完整的 双向链表 的 接口函数图
在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/37156.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注