数据结构之链表（带头双向循环链表）

---

前言

在了解了单链表之后，想必大家对于链表已经有了很多的了解，同时对于比单链表更有趣的带头双向循环链表也有了很大的兴趣。
因此今天要带大家了解的是链表中的带头双向循环链表。

一、带头双向循环链表

结合图片可以了解到，这种链表有头结点（哨兵位），每个节点带有两个指针，一个指向前一个节点，另一个指向后一个节点，这样就可以将前后节点都联系起来。虽然它的结构看上去有点复杂，但实际上的实现和使用都很简单，具体如何我们往下接着看。

二、双向链表

1.双向链表的声明

typedef int LTDataType;
typedef struct ListNode//链表的节点
{
	LTDataType date;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
1
2
3
4
5
6
7

2.双向链表的接口

//创建链表的头结点（返回头结点的地址）
ListNode* ListCreate();
//打印链表
void ListPrint(ListNode* plist);
//链表的销毁
void ListDestory(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
//链表的尾删
void ListPopBack(ListNode* plist);
//链表的头插
void ListPushFront(ListNode* plist, LTDataType x);
//链表的头删
void ListPopFront(ListNode* plist);
//链表的查找(如果找到了就返回下标，没找到就报错)
ListNode* ListFind(ListNode* plist, LTDataType x);
//在pos前面插入数据
void ListInsert(ListNode* pos, LTDataType x);
//双向链表删除pos位置处的节点
void ListErase(ListNode* pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.接口的实现

创建返回链表的头结点

//创建返回链表的头结点
ListNode* ListCreate()//头结点（哨兵位）
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->next = p;
	p->prev = p;
	return p;
}
1
2
3
4
5
6
7
8

这里有一个要注意点：我之前看的一些书上，对于头结点的date也进行了赋值，主要用于记录链表的长度（结点个数），但是实际上这种做法是不可取的。
原因如下：
链表节点的数据类型不确定；
如果类型为char，那它所存储的最大值是127，如果链表节点个数超过了127就会产生错误；
当然，即便是int类型，如果数据数量过多也会产生问题
所以，我们所定义的链表的头结点不进行赋值。

创建一个新节点

ListNode* ListBuyNewNode(LTDataType x)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	if (!p)
	{
		perror("malloc fail");//如果扩容失败，会报警告，告诉使用者扩容失败
	}
	p->next = p;
	p->prev = p;
	p->date = x;
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12

打印链表

void ListPrint(ListNode* plist)
{
	ListNode* p = plist;
	while (p->next != plist)//因为是循环链表，所以当p->next==plist为真时，p指向末尾节点（注意：不能用p-
	{
		printf("%d->", p->next->date);
		p = p->next;
	}
	printf("NULL\n");//如果链表为空则打印NULL
}
1
2
3
4
5
6
7
8
9
10

链表的销毁

void ListDestory(ListNode* plist)
{
	ListNode* tail = plist;
	while (plist->next != plist)
	{
		tail = plist->prev;
		plist->prev = tail->prev;
		plist->prev->next = plist;
		free(tail);
	}
	free(plist);
}
1
2
3
4
5
6
7
8
9
10
11
12

尾插

void ListPushBack(ListNode* plist, LTDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	ListNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	plist->prev = newnode;
	newnode->next = plist;
}
1
2
3
4
5
6
7
8
9

尾删

void ListPopBack(ListNode* plist)
{
	ListNode* tail = plist;
	assert(plist->next != plist);//避免链表中没有数据仍在删除造成越界
	tail = plist->prev;
	plist->prev = tail->prev;
	plist->prev->next = plist;
	free(tail);
}
1
2
3
4
5
6
7
8
9

头插

void ListPushFront(ListNode* plist, LTDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->prev = plist;
	newnode->next = plist->next;
	plist->next->prev = newnode;
	plist->next = newnode;
}
1
2
3
4
5
6
7
8

头删

void ListPopFront(ListNode* plist)
{
	assert(plist->next != plist);
	ListNode* begin = plist->next;
	plist->next = begin->next;
	begin->next->prev = plist;
	free(begin);
}
1
2
3
4
5
6
7
8

在链表中进行查找

(如果找到了就返回下标，没找到就返回NULL)

ListNode* ListFind(ListNode* plist, LTDataType x)
{
	ListNode* pos = plist->next;
	while (pos != plist)
	{
		if (pos->date == x)
			return pos;
		pos = pos->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

查找也可以充当修改。

在pos前面插入数据

void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8

链表删除pos位置处的节点

void ListErase(ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}
1
2
3
4
5
6

4.主函数（测试）

void test1()//测试尾插
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	// 双向链表尾插
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
void test2()//测试尾删
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	//链表的尾删
	ListPopBack(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
	/*ListPopBack(plist);//再删除就会报错
	ListPrint(plist);*/
	//链表的销毁
	ListDestory(plist);
}
void test3()//测试头插
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
void test4()//测试头删
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPrint(plist);
	/*ListPopFront(plist);//再删除就报错
	ListPrint(plist);*/
	//链表的销毁
	ListDestory(plist);
}
void test5()//测试查找
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	ListNode*pos = ListFind(plist, 38);
	if (pos)
	{
		printf("找到了\n");
	}
	//链表的销毁
	ListDestory(plist);
}
void test6()//测试在pos位置之前插入一个节点
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	ListNode*pos = ListFind(plist, 22);
	ListInsert(pos,80);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
void test7()//测试删除pos位置的数据
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	ListNode*pos = ListFind(plist, 22);
	ListErase(pos);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	test7();
	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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

总结

以上就是今天要讲的内容，本文主要介绍了带头双向循环链表，对带头双向循环链表的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路自行实现带头双向循环链表。
本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！