链表的极致——带头双向循环链表

​

双向带头循环链表简介：

双向带头循环链表是链表结构最复杂，但使用最方便的链表。

[图中phead表示链表的头节点（哨兵）;

d1，d2等表示链表存储的数据；

d1，d2等左侧的方框存储是指向该节点的上一个节点的指针（prev），右侧方框存储指向该节点的下一个的指针（next）]

---

双向：

双向带头循环链表的每一个节点的指针域都有俩个指针，一个指针（prev）指向该节点的前一个节点，一个指针（next）指向它的后一个节点。
解决了单链表只能向后访问，不能向前访问的问题

---

带头：

特点：

1. 双向带头循环链表的头节点（哨兵）位于第一个存储数据的链表的前一个结点

2. 双向带头循环链表有一个头节点（哨兵），该节点无论链表是否为空它都存在

3. 头节点（哨兵）的数据域一般不存储数据或者存储链表的信息（有几个节点等）

4. 双向带头循环链表的头节点（哨兵）指针域的也有两个指针，且指向前一个节点的指针（prev）指向链表的最后一个节点，指向下一个节点的指针（next）指向链表的第一个节点

---

链表带头节点的好处：

1. 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个节点上的操作就和在表的其它位置上操作一致,无须对链表的第一个节点进行进行特殊处理。 不会再改变链表phead指向的位置，也就不用再函数传参时有时传phead，有时传*phead，让链表的接口函数的参数类型也统一了。
2. 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了，不需要再分情况。

---

循环：

特点：

1. 双向带头循环链表的最后一个节点的指向下一个节点的指针（next）指向头节点（哨兵）
2. 头节点（哨兵）的指向上一个节点的指针（prev）指向链表的最后一个节点
3. 当链表为空时，只有头节点（哨兵），此时头节点（哨兵）的prev指向它自己，它的next也指向它自己

---

循环的好处：

1. 尾插时不用遍历找链表的最后一个节点（尾节点），因为指向双向带头循环链表的最后一个的节点的指针被存放在头节点（哨兵）的prev中。
2. 在进行删除操作后，能保证链表不断开
3. 从链表中任意结点出发都能遍历整个链表。
4. 可以实现循环遍历，即在遍历到链表末尾后能够自动回到链表头部进行下一轮遍历。

---

双向带头循环链表的接口函数实现

准备工作：

创建一个头文件（SList.h）两个源文件（SList.c和test.c）

• SList.h:用于包含库函数的头文件，链表节点结构体声明，接口函数的声明等【另外两个源文件要包含SList.h这个头文件，才能使用其中的声明】
• SList.h：用于实现单链表的接口函数
• test.c:存放main函数，用于链表的测试

上图包含了以下3个操作

1.库函数的头文件的包含：

stdio.h:输入/输出等函数
stdlib.h:动态内存申请
assert.h:报错函数assert
2.给链表节点的数据域的数据类型重命名
为什么要重命名呢？
这是为了以后如果改变了LTNoed结构体中数据存储的类型时，
不用到处改函数参数等地方的数据类型，只要改typedef后的int 为对应要改成的数据类型就可以。

3.链表节点结构体定义和重命名

---

初始化链表（头结点）

参数设计：
无需参数，将返回值赋值给一个指针，这个指针就成为链表的phead。

---

尾插

---

参数设计

LTNode*phead:
上面说了因为头指针（phead）不会改变，所以传一级指针phead即可

LTDaType x：
要插入的数据

---

图解

链表为空的时候也不需要像单链表那样特殊考虑，这也是双向带头循环链表的好处

---

打印链表

---

图解

---

头插

---

图解

---

尾删

---

图解

---

头删

---

图解

---

查找

---

随机插入

随机插入的pos要配合查找函数的返回值使用·

---

图解

---

随机删除

---

图解

---

销毁链表

---

图解

---

全部代码

SList.h

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDateType;

typedef struct LTNode
{
	LTDateType data;
	struct LTNode* next;
	struct LTNode* prev;
}LTNode;

//初始化链表
LTNode* ListInit(void);
//打印链表
void ListPrint(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//头插
void ListPushFront(LTNode* phead, LTDateType x);
//尾删
void ListPopBack(LTNode* phead);
//头删
void ListPopFront(LTNode* phead);
//查找x,找到了返回指向x的结构指针，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x);
//在pos之前插入数据
void ListInsert(LTNode* phead, LTNode* pos, LTDateType x);
//删除pos指向的节点
void ListEase(LTNode* phead, LTNode* pos);
//销毁链表
void ListDestory(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

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

LTNode* ListInit()
{
	//哨兵位头节点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//为头结点申请空间

	phead->data = 0;//不存储链表数据（链表的长度等）时也可不初始化

	phead->next = phead;//链表为空时头结点的next指向自己
	phead->prev = phead;//链表为空时头结点的prev也指向自己

	return phead;//返回被一个节点（phead）接收
}

void ListPushBack(LTNode* phead, LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为新节点申请空间
	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序，-1表示程序非正常结束
	}
	LTNode* tail = phead->prev;//tail指向链表的最后一个节点

	tail->next = newnode;//让新节点成为原尾节点的下一个节点

	newnode->prev = tail;//让原尾节点成为新节点的上一个节点

	phead->prev = newnode;//更新头结点中存储的尾节点

	newnode->next = phead;//让新节点的下一个节点为头结点（phead）

	newnode->data = x;//存储数据
}

void ListPrint(LTNode* phead)
{
	LTNode* cur = phead->next;//将链表的第一个节点赋值给cur

	while (cur != phead)//因为双向带头循环链表没有指向NULL的指针了，而且链表的尾节点的next指向头结点（phead）
		                //所以遍历链表结束的条件为cur==phead
	{
		printf("%d  ", cur->data);//打印节点数据域的数据
		cur = cur->next;//让cur指向下一个节点
	}
}

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为新节点申请空间

	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序，-1表示程序非正常结束
	}
	phead->next = newnode;//让头结点的下一个节点为新节点

	newnode->next = cur;//让新节点的下一个节点为原链表的第一个节点

	newnode->prev = phead;//让新节点的上一个节点为头结点

	newnode->data = x;

	cur->prev = newnode;//让原链表的第一个节点的上一个节点为新节点
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead->next != phead);//链表为空时不能再删除

	LTNode* tail = phead->prev;//让tail指向尾节点

	tail->prev->next = phead;//让尾节点（tail）的前一个节点的next指向头结点，

	phead->prev = tail->prev;//让删除之前的尾节点的前一个节点成为新的尾节点

	free(tail);//释放删除之前的尾节点
}
//头删
void ListPopFront(LTNode* phead)
{
	assert(phead->next != phead);//链表为空时不能再删除

	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	phead->next = cur->next;//让头节点的下一个节点为原链表第一个节点的下一个节点（原链表的第二个节点）

	cur->next->prev = phead;//让原链表的第二个节点的前一个节点为头结点

	free(cur);//释放原链表第一个节点
}
//查找x,找到了返回指向x的结构指针，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	while (cur != phead)//因为双向带头循环链表没有指向NULL的指针了，而且链表的尾节点的next指向头结点（phead）
		                //所以遍历链表结束的条件为cur==phead
	{
		if (cur->data == x)
		{
			return cur;//找到了就直接返回
		}
		else
		{
			cur = cur->next;//让cur指向下一个节点
		}
	}
	return NULL;//找不到就返回NULL
}

//在pos之前插入数据
void ListInsert(LTNode** phead, LTNode* pos, LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序，-1表示程序非正常结束
	}
	newnode->data = x;//存放数据

	newnode->next = pos;//让新节点的下一个节点为pos指向的节点

	newnode->prev = pos->prev;//让新节点的上一个节点为pos指向节点的前一个节点

	pos->prev->next = newnode;//pos指向节点的上一个节点的下一个节点为新节点

	pos->prev = newnode;//让新节点成为pos指向节点的上一个节点
}

//删除pos指向的节点
void ListEase(LTNode* phead, LTNode* pos)
{
	assert(pos != phead);//链表为空时再不能删除

	pos->prev->next = pos->next;//让pos指向节点的前一个节点的next指向pos指向节点的下一个节点

	pos->next->prev = pos->prev;//让pos指向节点的下一个节点的prev指向pos指向节点的上一个节点

	free(pos);//释放pos指向节点
}

//销毁链表
void ListDestory(LTNode* phead)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	LTNode* tmp = phead->next;

	while (cur != phead)
	{
		tmp = cur->next;//tmp指向cur的下一个节点，防止cur被释放了，找不到下一个节点了
		free(cur);
		cur = tmp;//让cur指向下一个节点
	}
	phead->prev = phead;//链表的所有节点都被释放后，头节点的prev要指向自己，让链表下一次使用时不会出错

	phead->next = phead;//链表的所有节点都被释放后，头节点的next也要指向自己
}
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

---

以上就是所有内容了，如果对你有帮助的话，可以点个赞支持一下！