大家好我是沐曦希💕

1.前言

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了,可以通过对比无头单向链表实现代码进行对比。

2.带头双向循环链表的实现

2.1 List.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
//初始化带头双向循环链表
LTNode* ListInit(LTNode* phead);
//销毁链表
void ListDestory(LTNode* phead);
//尾插数据
void ListPushBack(LTNode* phead, LTDataType x);
//打印链表中的数据
void ListPrint(LTNode* phead);
//头插数据
void ListPushFront(LTNode* phead, LTDataType x);
//尾删数据
void ListPopBack(LTNode* phead);
//头删数据
void ListPopFront(LTNode* phead);
//检测链表是否为空
bool ListEmpty(LTNode* phead);
//计录链表有多少的数据
size_t ListSize(LTNode* phead);
//查找链表中数据
LTNode* ListFind(LTNode* phead, LTDataType x);
//在pos位置之前插入数据
void ListInsert(LTNode* pos, LTDataType x);
//删除pos位置
void ListErase(LTNode* pos);
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

2.2 test.c

#include"List.h"
void test1()
{
	LTNode* plist = NULL;
	plist = ListInit(plist);
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPushFront(plist, 40);
	ListPushFront(plist, 30);
	ListPushFront(plist, 20);
	ListPushFront(plist, 10);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListDestory(plist);
	plist = NULL;
}
void test2()
{
	LTNode* plist = NULL;
	plist = ListInit(plist);
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPushFront(plist, 40);
	ListPushFront(plist, 30);
	ListPushFront(plist, 20);
	ListPushFront(plist, 10);
	ListPrint(plist);
	LTNode* cur = ListFind(plist, 30);
	printf("%d\n", cur->val);
	ListInsert(cur, 100);
	ListPrint(plist);
	cur = ListFind(plist, 10);
	printf("%d\n", cur->val);
	ListErase(cur);
	ListPrint(plist);
	ListDestory(plist);
	plist = NULL;
}
int main()
{
	test1();
	test2();
	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

2.3 List.c

带头结点的双向循环链表

zip 0星 超过10%的资源 69KB

下载

#include"List.h"
LTNode* ListInit(LTNode* phead)
{
    //创建哨兵位
	phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//实现双向循环的功能
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//用一级指针，让调用ListDestory的人置空
//保持接口一致性
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
	    //从哨兵位的下一个节点遍历一遍并释放，直到cur回到phead停止
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
LTNode* BuyListNode(LTDataType x)
{
    //该函数实现了创建一个新节点
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->next = phead;
	newnode->prev = tail;
	phead->prev = newnode;*/
	ListInsert(phead, x);
	//尾插可以看成在pos=phead之前插入一个新节点
}
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("phead<=>");
	while (cur != phead)
	{
	    //从哨兵位的下一个节点遍历一遍并打印数据，直到cur回到phead停止
		LTNode* next = cur->next;
		printf("%d<=>", cur->val);
		cur = next;
	}
	printf("\n");
}
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* next = phead->next;
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;*/
	ListInsert(phead->next, x);
	//头插可以看成在pos=phead->next之前插入一个新节点
}
void ListPopBack(LTNode* phead)
{
	/*assert(phead);
	assert(!ListEmpty(phead));
	//检测链表是否还有数据可以删除
	LTNode* tail = phead->prev;
	LTNode* prev = tail->prev;
	phead->prev = prev;
	prev->next = phead;
	free(tail);
	tail = NULL;*/
	ListErase(phead->prev);
	//尾删可以看成是删除pos=phead->prev的节点
}
void ListPopFront(LTNode* phead)
{
	/*assert(phead);
	assert(!ListEmpty(phead));
	//检测链表是否还有数据可以删除
	LTNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
	cur = NULL;*/
	ListErase(phead->next);
	//头删可以看成是删除pos=phead->next的节点
}
bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
	//如果phead->next等于phead，表明没有数据。
	//不等于，表明链表还有数据。
}
size_t ListSize(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	size_t count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
    //查找经常用来进行删除和插入等操作，而不是单单进行查找操作
	assert(phead);
	LTNode* cur = phead->next;
	while (cur->next != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	pos->prev = newnode;
	newnode->next = pos;
}
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
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

3.顺序表和链表的区别

顺序表的优点（存储数据用顺序表多）：
1.尾插尾删效率高。
2.随机访问（用下标访问）
3.相比链表结构——顺序表CPU高速缓存命中率更高。

备注：缓存利用率参考存储体系结构 以及 局部原理性。

CPU执行指令，不会直接访问内存。先看数据在不在三级缓存：在（命中），直接访问；不在（不命中），先加载带缓存，再访问。
加载缓存时会从一个位置开始加载一段进入缓存（加载多少取决于硬件）。

顺序表是连续存储，加载进缓存的是有效数据，CPU高速缓存命中率效率更高。而链表不是连续存储的，各个地址之间没有关联的，所以加载进缓存的可能就一个有效数据，那么命中率低还污染。

顺序表的缺点：
1.头部和中部插入删除效率低——O(N)
2.扩容——性能消耗+空间浪费

链表的优点：
1.任意位置插入删除效率很高。——O(N)
2.按需申请释放+不存在空间浪费。
链表的缺点：
1.不支持随机访问。

4.写在最后

那么带头双向循环链表就到这里了。