【数据结构】双向循环链表

---

1. 前言

上一篇博客我们介绍了无头单向链表，但它一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。但是如果我们想要用链表来存储数据，又该怎么办呢？接下来我们就要学习一种新的链表——带头双向循环链表，它是链表中结构最复杂的，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。不过虽然该链表的结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

---

2. 链表的实现

List.h

❤️ 头文件的包含、结构体类型的定义以及各个接口函数的声明

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//初始化双向循环带头链表
LTNode* LTInit();

//开辟新结点
LTNode* BuyLTNode(LTDataType x);

//双向链表的打印
void LTPrint(LTNode* phead);

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

//双向链表的尾删
void LTPopBack(LTNode* phead);

//双向链表头删
void LTPopFront(LTNode* phead);

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

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

//在pos之前插入x
void LTInsert(LTNode* pos, LTDataType x);

//删除pos节点
void LTErase(LTNode* pos);

//判断链表是否为空
bool LTEmpty(LTNode* phead);

//返回链表中的节点个数
size_t LTSize(LTNode* phead);

//销毁链表
void LTDestroy(LTNode* phead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---

List.c

💖 所有接口函数的实现

🐶 初始化双向循环带头链表

LTNode* LTInit()
{
	LTNode* DummyNode = (LTNode*)malloc(sizeof(LTNode));
	if (!DummyNode) {
		perror("malloc fail::");
		exit(-1);
	}
	DummyNode->next = DummyNode;
	DummyNode->prev = DummyNode;
	return DummyNode;
}
1
2
3
4
5
6
7
8
9
10
11

首先先创建一个哨兵位的头节点，该节点不存储任何数据，这样我们在主函数中实现别的接口函数传参时就不需要传递二级指针，直接通过返回的哨兵位头节点来实现结构体指针的初始化，然后后续通过哨兵位头节的索引来改变结构体中的内容。这里我们先开辟一个头节点，然后将头节点的两个指针都指向自己。

---

🐱 开辟新结点

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (!newnode) {
		perror("malloc fail::");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

因为我们实现链表的插入时会经常开辟一个新的节点，然后将节点的数据域赋值为想要插入的数据，所以这里我们直接将该功能打包成一个函数，返回值为结构体指针类型，以便我们需要的时候直接调用即可。在这里我们需要注意的是最好将结构体中的两个指针全部置为空，防止野指针的出现。

---

🐭 双向链表的打印

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

我们要打印这个链表，就要遍历这个链表中除了头节点的每一个节点，但我们又不能单链表一样，找到它的最后一个节点为空，所以这里我们需要从哨兵位的下一个节点开始遍历，直到下一个节点等于哨兵位为止停止遍历。在遍历的过程中，将每一个节点的数据打印出来即可。

---

🐹 双向链表尾插尾删

//双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//双向链表的尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

要进行尾插尾删我们就要找最后一个节点，这里比较方便的是我们不用去找尾节点，因为头节点的prev指针指向的就是尾节点。最后只需要将指针间的对应关系进行链接即可。

---

🐰 双向链表头插头删

//双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* headNext = phead->next;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = headNext;
	headNext->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}
//双向链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* headNext = phead->next;
	phead->next = headNext->next;
	headNext->next->prev = phead;
	free(headNext);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

要进行头插头删也是非常容易的，注意在头删的时候链表不能只有哨兵位的
头节点，那样会把哨兵位的头节点也删掉，在后续要进行其他的操作时就会出错。

---

🦊 双向链表查找

LTNode* LTFind(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

要查找指定数据，就需要遍历链表，如果可以找到直接返回找到的节点，否则返回一个空指针。

---

🐻 在pos之前插入x/删除pos节点

//在pos之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{
	LTNode* prevPos = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = pos;
	pos->prev = newnode;
	prevPos->next = newnode;
	newnode->prev = prevPos;
}
//删除pos节点
void LTErase(LTNode* pos)
{
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这两个操作都是插入或者删除一个节点，和上面的头尾指针插入删除操作基本一致，这里不过多解释。

---

🐼 判断链表是否为空

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
1
2
3
4
5

这里直接判断哨兵位头节点的下一个节点是不是自己即可。

---

🐨 返回链表中的节点个数

size_t LTSize(LTNode* phead)
{
	size_t size = 0;
	if (phead->next == phead)
		return 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里如果链表为空直接返回0，否则遍历链表统计节点个数即可。

---

🐮 销毁链表

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12

遍历链表依次销毁每一个节点即可，这里我们需要注意最后需要把哨兵位的头节点也释放掉，在主函数中置为空。

---

Test.h

💞 测试各个接口函数的功能

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

void TestList1()
{
	LTNode* LT = LTInit();//测试尾插尾删
	LTPushBack(LT, 1);
	LTPushBack(LT, 2);
	LTPushBack(LT, 3);
	LTPushBack(LT, 4);
	LTPushBack(LT, 5);
	LTPrint(LT);
	LTPopBack(LT);
	LTPrint(LT);
	LTPopBack(LT);
	LTPrint(LT);
}
void TestList2()
{
	LTNode* LT = LTInit();//测试头插头删
	LTPushFront(LT, 1);
	LTPushFront(LT, 2);
	LTPushFront(LT, 3);
	LTPushFront(LT, 4);
	LTPushFront(LT, 5);
	LTPrint(LT);
	LTPopFront(LT);
	LTPrint(LT);
	LTPopFront(LT);
	LTPrint(LT);
	LTPopFront(LT);
	LTPrint(LT);
	LTPopFront(LT);
	LTPrint(LT);
}
void TestList3()
{
	LTNode* LT = LTInit();//测试查找指定值、指定位置插入节点
	LTPushBack(LT, 1);
	LTPushBack(LT, 2);
	LTPushBack(LT, 3);
	LTPushBack(LT, 4);
	LTPushBack(LT, 5);
	LTPrint(LT);
	LTNode* pos = LTFind(LT, 5);
	if (pos) {
		LTInsert(pos, 500);
	}
	LTPrint(LT);
	pos = LTFind(LT, 1);
	if (pos) {
		LTInsert(pos, 100);
	}
	LTPrint(LT);
}
void TestList4()
{
	LTNode* LT = LTInit();//测试删除指定节点
	LTPushBack(LT, 1);
	LTPushBack(LT, 2);
	LTPushBack(LT, 3);
	LTPushBack(LT, 4);
	LTPushBack(LT, 5);
	LTPrint(LT);
	LTNode* pos = LTFind(LT, 2);
	if (pos) {
		LTErase(pos);
	}
	LTPrint(LT);
	pos = LTFind(LT, 1);
	if (pos) {
		LTErase(pos);
	}
	LTPrint(LT);
	pos = LTFind(LT, 5);
	if (pos) {
		LTErase(pos);
	}
	LTPrint(LT);
}
void TestList5()
{
	LTNode* LT = LTInit();//测试链表判空、返回链表节点个数、销毁链表
	LTPushBack(LT, 1);
	LTPushBack(LT, 2);
	LTPushBack(LT, 3);
	LTPushBack(LT, 4);
	LTPushBack(LT, 5);
	LTPrint(LT);
	if (LTEmpty(LT)) {
		printf("链表为空\n");
	}else {
		printf("链表不为空\n");
		printf("节点个数为：%d\n", LTSize(LT));
	}
	LTDestroy(LT);
}
int main()
{
	/*TestList1();
	TestList2();
	TestList3();
	TestList4();*/
	TestList5();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

---

3. 总结

好了，以上内容就是今天对双向循环链表的讲解了，相比单向不带头链表，它的效率更高、更适合用链表来存储数据。到这里链表的基础知识就结束了，后续会继续讲解链表的OJ练习。如果觉得有收获的话还望支持一下博主哦！