【数据结构】带头双向循环链表基本操作的实现（C语言）

---

🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🐌 个人主页：蜗牛牛啊
🔥 系列专栏：🛹数据结构、🛴C++
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹

---

一、概念与结构

无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。而带头双向循环链表的结构较为复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表，虽然它的结构复杂但是因为结构优势用代码实现起来会变得简单。

二、基本操作的实现

定义结构体

typedef int ListDataType;//类型重命名
typedef struct ListNode {
	ListDataType val; //结点数据
	struct ListNode* prev;//指向上一个结点的指针
	struct ListNode* next;//指向下一个结点的指针
}LTNode;
1
2
3
4
5
6

1.创建结点

LTNode* BuyListNode(ListDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请空间
    //判断是否为空
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.初始化链表

void ListInit(LTNode** pphead)//初始化
{
    //创建一个头节点
	*pphead = (LTNode*)malloc(sizeof(LTNode));//初始化时将头结点置为-1;
    
	*pphead = BuyListNode(-1); //头节点
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//	LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//	phead->next = phead;
//	phead->prev = phead;
//	return phead;
//}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

初始化链表有两种方式，一种是有返回类型（注释部分），另一种是在初始化函数中给结构体开辟空间（不过注意参数要为二级指针）。因为是带头结点的循环链表，所以prev和next指针都指向自己。

3.打印链表

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

注意while循环的结束条件，保证能够打印链表中的所有有效值。要对头结点进行assert判断，不能为空。

4.尾插

//不用二级指针，因为是带头结点的链表，所以不会改变头节点
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
	assert(phead);//断言
    //创建新结点
	LTNode* newnode = BuyListNode(x);
    //改变指针指向，插入数据
	LTNode* tail = phead->prev;
	newnode->next = tail->next;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;
	//ListInsert(phead, x);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.尾删

void ListPopBack(LTNode* phead)//尾删
{
	assert(phead);//断言
	assert(phead->next != phead);//判断不是头节点
    
	LTNode* prevnode = phead->prev;
    //将结点从链表中移除
	prevnode->prev->next = phead;
	phead->prev = prevnode->prev;
    
	free(prevnode);//释放结点
	//ListErase(phead->prev);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

尾删时要注意判断phead->next != phead，不能删除头结点，同时记得要free(prevnode)释放删除后的空间。

6.头插

void ListPushFront(LTNode* phead, ListDataType x)//头插
{
	assert(phead);
    
	LTNode* tail = phead->next;
    //申请新节点
	LTNode* newnode = BuyListNode(x);
    //改变指针指向，插入数据
	tail->prev = newnode;
	newnode->next = tail;
	newnode->prev = phead;
	phead->next = newnode;
	//ListInsert(phead->next,x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.头删

void ListPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(phead->next != phead);//判断不是头节点
    //移除元素
	LTNode* tail = phead->next;
	phead->next = tail->next;
	tail->next->prev = phead;
    free(tail);//释放结点
	//ListErase(phead->next);
}
1
2
3
4
5
6
7
8
9
10
11

8.查找某个数并返回其指针

LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针
{
	assert(phead);
	LTNode* cur = phead->next;//从第一个结点开始
    //遍历查找
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;//相等就返回
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9.在某个位置之前插入

void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
	assert(pos);
    
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = pos->prev;
    //改变指针指向，插入数据
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

10.删除某个位置

void ListErase(LTNode* pos)//删除pos位置
{
	assert(pos);
	LTNode* prevnode = pos->prev;
	LTNode* nextnode = pos->next;
	free(pos);
	prevnode->next = nextnode;
	nextnode->prev = prevnode;
	/*pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);*/
}
1
2
3
4
5
6
7
8
9
10
11
12

11.判断链表是否为空

bool ListEmpty(LTNode* phead)//判断是否为空,如果是空，返回true
{
	assert(phead);
	return phead->next == phead; //如果头节点的next指针指向自己说明链表为空
}
1
2
3
4
5

12.计算链表中有效值的个数

size_t ListSize(LTNode* phead)//计算链表中有效值的个数
{
	assert(phead);
	size_t size = 0;
	LTNode* tail = phead->next;
    //遍历计算有效值个数
	while (tail != phead)
	{
		size++;
		tail = tail->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

13.销毁链表

void ListDestroy(LTNode* phead)//销毁链表 
{
	assert(phead);
	LTNode* tail = phead->next;
    //一个一个销毁
	while (tail != phead)
	{
		LTNode* nextnode = tail->next;
		free(tail);
		tail = nextnode;
	}
    //最后在这里将头节点也释放
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

销毁链表时要注意要保证每个结点都释放，同时最后也要将头结点释放free(phead)。但是注意这里的参数LTNode* phead是形参，释放空间之后（只要知道地址就可以释放空间），如果在这个函数内想把phead置空，注意形参的改变不会影响实参，所以不能置空。如果想在函数内置空需要传递phead的指针，即链表的二级指针。但是双链表之前的操作没有使用过二级指针，这里为了保持一致性，也不再使用二级指针，可以在函数外面手动把phead置空。

三、测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
typedef int ListDataType;
typedef struct ListNode {
	ListDataType val;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
LTNode* BuyListNode(ListDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
void ListInit(LTNode** pphead)//初始化
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	*pphead = BuyListNode(-1);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//	LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//	phead->next = phead;
//	phead->prev = phead;
//	return phead;
//}

void ListPrint(LTNode* phead)//打印
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	newnode->next = tail->next;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;
	//ListInsert(phead, x);
}
void ListPopBack(LTNode* phead)//尾删
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* prevnode = phead->prev;
	prevnode->prev->next = phead;
	phead->prev = prevnode->prev;
	free(prevnode);
	//ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, ListDataType x)//头插
{
	assert(phead);
	LTNode* tail = phead->next;
	LTNode* newnode = BuyListNode(x);
	tail->prev = newnode;
	newnode->next = tail;
	newnode->prev = phead;
	phead->next = newnode;
	//ListInsert(phead->next,x);
}
void ListPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->next;
	phead->next = tail->next;
	tail->next->prev = phead;
	//ListErase(phead->next);
}
LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = pos->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pos;
	pos->prev = newnode;
}
void ListErase(LTNode* pos)//删除pos位置
{
	assert(pos);
	LTNode* prevnode = pos->prev;
	LTNode* nextnode = pos->next;
	free(pos);
	prevnode->next = nextnode;
	nextnode->prev = prevnode;
	/*pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);*/
}
bool ListEmpty(LTNode* phead)//判断是否为空,如果是空，返回true
{
	assert(phead);
	return phead->next == phead;
}
size_t ListSize(LTNode* phead)//计算链表中有效值的个数
{
	assert(phead);
	size_t size = 0;
	LTNode* tail = phead->next;
	while (tail != phead)
	{
		size++;
		tail = tail->next;
	}
	return size;
}
void ListDestroy(LTNode* phead)//销毁链表 
{
	assert(phead);
	LTNode* tail = phead->next;
	while (tail != phead)
	{
		LTNode* nextnode = tail->next;
		free(tail);
		tail = nextnode;
	}
	free(phead);
}
void TestList()
{
	//LTNode* plist = ListInit(&plist);
	LTNode* plist = NULL;
	ListInit(&plist);
	ListPushBack(plist, 100);
	ListPushBack(plist, 200);
	ListPushBack(plist, 300);
	ListPushBack(plist, 400);
	ListPushBack(plist, 500);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 1000);
	ListPushFront(plist, 2000);
	ListPushFront(plist, 3000);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	LTNode* pos = ListFind(plist, 1000);
	if (pos != NULL)
	{
		ListInsert(pos, 500);
		ListErase(pos);
	}
	ListPrint(plist);
	if (!ListEmpty(plist))
		printf("%d\n", ListSize(plist));
}
int main()
{
	TestList();
	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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191