---

前言

在前两篇文章中，我们学习了 顺序表 和 单向不带头非循环 链表。
 
链接如下：
 
【大画数据结构】第一话 —— 动态顺序表的增删改查
 
【大画数据结构】第二话 —— 无头单链表的基本操作
 
那么今天，将要学习链表的第三种 双向带头循环链表。

链表的分类

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

其实 链表 一共分为 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;
1
2
3
4
5
6
7
8

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

📝 代码示例

//增加一个节点
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; // 返回头结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 打印链表

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

📝 代码示例

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

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

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

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; // 没有找到目标结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

🍑 尾插

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

因为链表是循环的，头结点的前驱指针直接指向最后一个结点，所以我们不必遍历链表找尾。

动图演示👇

📝 代码示例

//双向链表尾插
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍑 指定位置插入

这里的指定插入，是在指定的 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🍑 插入升级

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

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

📝 代码升级

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

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

📝 代码升级

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

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结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍑 尾删

尾删，即释放最后一个结点，并建立 哨兵结点 和 被删除结点的前一个结点 之间的双向关系即可。

📝 代码示例

//双链表尾删
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍑 指定位置删除

删除指定 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

🍑 删除升级

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

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

📝 代码升级

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

	ListErase(phead->next);
}
1
2
3
4
5
6
7

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

📝 代码升级

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

6. 链表判空

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

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

📝 代码示例

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

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

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

📝 代码示例

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

	int count = 0; // 记录元素个数
	LTNode* cur = phead->next; // 从头结点的后一个结点开始遍历
	while (cur != phead) // 当cur指向头结点时，遍历完毕，头结点不计入总元素个数
	{
		count++;
		cur = cur->next;
	}
	return count; //返回元素个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9. 总结

疑问点：

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

顺序表 与 链表 的优缺点：

接口函数贴图

最后附上一张完整的 双向链表 的 接口函数图