带头+双向+循环链表

前言：

前面我们已经学习了单链表的结构及其功能特点，也了解了单链表在实现一些功能时出现的一些缺点，比如在删除某个节点前面一个节点时就需要再开一个变量来存放前面一个节点的信息，这样就显得不灵活，为了使链表实现功能更加灵活，我给来介绍带头双向循环链表，这种链表可以看成是单链表的升级版。

什么是带头双向循环链表？

带头双向循环链表是一种常见的链表数据结构，它是由若干个结点组成的链式数据结构，每个结点包含两个指针，分别指向前一个结点和后一个结点。与普通的单向链表只能单向遍历不同，在双向循环链表中，可以使用前后两个方向进行遍历。

带头双向循环链表的优点？

带头链表意味着在链表头部添加一个空的头结点，这个头结点不包含数据，仅包含指向链表首尾结点的指针，它主要作用是简化链表的操作。在插入、删除、查找等操作时，可以直接从头结点开始操作，无需特殊处理首尾结点。

双向循环意味着链表的每一个节点都可以随意的找到上一个节点以及下一个节点，并且头节点的前驱指针指向尾节点，尾节点的后驱指针指向头节点，这样整个链表就形成了一个环状结构，可以任意方向遍历整个链表。

由于带头双向循环链表具有链表的优点，同时又兼具循环队列的特点，因此在实际应用中被广泛使用。比如在实现 LRU 缓存淘汰算法、模拟双向队列等场景中都有使用。

代码实现

DList.h头文件

各种功能函数的声明以及数据的定义：

#include
#include
#include

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, 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
21
22
23
24
25
26
27
28
29
30
31
32
33

DList.c文件

各种功能函数的具体实现细节：

#include"DList.h"

// 创建返回链表的头结点.
ListNode* ListCreate() {
	ListNode* NewList = (ListNode*) malloc(sizeof(ListNode));
	if (NewList == NULL) {
		perror("malloc: fail");
	}

	NewList->_data = -1;
	NewList->_prev = NewList;
	NewList->_next = NewList;
	return NewList;
}

//创造节点
static ListNode* CreatNode(LTDataType x) {
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL) {
		perror("malloc:fail");
	}
	newnode->_data = x;
	newnode->_next = newnode;
	newnode->_prev = newnode;
	return newnode;
}

// 双向链表销毁
void ListDestory(ListNode* phead) {
	assert(phead);
	ListNode* cur = phead;
	cur = cur->_next;
	while (cur!=phead) {
		ListNode* temp = cur->_next;
		cur->_prev->_next = cur->_next;
		cur->_next->_prev = cur->_prev;
		free(cur);
		cur = temp;
	}
	free(cur);
	cur = NULL;
}

// 双向链表打印
void ListPrint(ListNode* phead) {
	assert(phead);
	ListNode* cur = phead->_next;
	printf("%d<=>", phead->_data);
	while (cur!= phead) {
		printf(" %d <=>", cur->_data);
		cur = cur->_next;
	}
	printf("%d\n", phead->_data);
}

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x) {
	assert(phead);
	ListNode* newnode = CreatNode(x);
	ListNode* tail = phead->_prev;
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = phead;
	phead->_prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* phead) {
	assert(phead&&(phead->_next!=phead));

	ListNode* tail = phead->_prev;
	phead->_prev = tail->_prev;
	tail->_prev->_next = phead;
	free(tail);
	tail = NULL;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x) {
	assert(phead);
	ListNode* newnode = CreatNode(x);
	phead->_next->_prev = newnode;
	newnode->_next = phead->_next;
	newnode->_prev = phead;
	phead->_next = newnode;
}

// 双向链表头删
void ListPopFront(ListNode* phead) {
	assert(phead&&(phead->_next!=phead));
	ListNode* head = phead->_next;
	phead->_next->_next->_prev = phead;
	phead->_next = phead->_next->_next;
	free(head);
	head = NULL;
}

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) {
	assert(phead && (phead->_next != phead));
	//ListNode* newnode = CreatNode(x);
	ListNode* cur = phead->_next;
	while (cur != phead) {
		if (cur->_data == x) {
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
	assert(pos);
	ListNode* newnode = CreatNode(x);

	pos->_prev->_next = newnode;
	newnode->_prev = pos->_prev;
	newnode->_next = pos;
	pos->_prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {
	assert(pos&&(pos->_next!=pos));
	ListNode* temp = pos;
	pos->_prev->_next = pos->_next;
	pos->_next->_prev = pos->_prev;
	free(temp);
	temp = 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

test.c测试文件

分块测试各个部分的功能

#include"DList.h"

void test1()//测试尾插、尾删
{
	// 创建返回链表的头结点.
	ListNode* phead=NULL;
	phead= ListCreate();
	ListPushBack(phead, 1);//尾插
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPrint(phead);
	printf("尾删\n");
	ListPopBack(phead);//尾删
	ListPrint(phead);

	printf("尾删\n");
	ListPopBack(phead);//尾删
	ListPrint(phead);
	//ListPopBack(phead);
	//ListPrint(phead);
	ListDestory(phead);//销毁链表
}


void test2()//测试头插、头删
{
	// 创建返回链表的头结点.
	ListNode* phead = NULL;
	phead = ListCreate();
	ListPushFront(phead, 1);//头插，头删
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPrint(phead);
	printf("头删\n");
	ListPopFront(phead);
	ListPrint(phead);
	printf("头删\n");
	ListPopFront(phead);
	//ListPopFront(phead);
	//ListPopFront(phead);
	//ListPopFront(phead);
	ListPrint(phead);
	ListDestory(phead);

}
void test3()//测试查找，随机位置插入，随机位置删除
{
	// 创建返回链表的头结点.
	ListNode* phead = NULL;
	phead = ListCreate();//初始化链表数据 1 2 3 4 5
	ListPushFront(phead, 1);
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);
	ListPrint(phead);
	//ListNode* targetnode = ListFind(phead, 5);
	ListNode* targetnode = ListFind(phead, 4);
	

	if (targetnode == NULL) {//没有找到
		printf("没有找到\n");
	}
	else {
		printf("找到%d了\n",targetnode->_data);
		/*ListErase(targetnode);
		printf("删除这个节点\n");*/
		ListInsert(targetnode, 10);//在目标节点前面插入
		printf("在这个节点插入一个数\n");
		ListPrint(phead);
	}
	ListNode* targetnode2 = ListFind(phead, 4);
	if (targetnode2 == NULL) {//没有找到
		printf("没有找到\n");
	}
	else {
		printf("找到%d了\n", targetnode2->_data);
		ListErase(targetnode);
		printf("删除这个节点\n");
		ListPrint(phead);
	}
	//ListPopFront(phead);
	//ListPrint(phead);
	ListDestory(phead);
	phead = NULL;
}

int main() {
	test1();
	//test2();
	//test3();
	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

test1运行结果

test2运行结果

test3运行结果