【数据结构】原来你叫“带头结点的双向循环链表”啊

🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

---

前言

  上篇博客带大家认识了单链表，单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次向后遍历。对于插入、删除操作得从头遍历，尤其是在链表尾部，还有一点就是无法一步的访问到某个节点的前驱节点，也就是说访问前驱节点的时间复杂度为O(n)。为了避免这样的缺点，便引出了双向循环链表

---

一、什么是带头结点的双向循环链表？

  首先，它是一个链表，通过指针将所有的结点连接在一起；其次，循环链表表示整个链表从头到尾构成一个环，链表尾结点的next指针指向头结点；再者，双向表示链表结点有两个指针prev和next，分别指向其前驱结点和后继节点；最后，带头结点表示链表的第一个有效结点前附加一个结点，头结点的数值域不设任何信息。带头结点的双向循环链表如下图所示：

看似带头结点的双向循环链表的结构更为复杂，但是对于之前单链表的尾插尾删操作更为简单。

二、带头结点的双向循环链表基本操作实现

注意： 该链表带头结点，所以在进行任何的插入删除操作都无需传二级指针，因为对于头指针的指向并不会改变，只会改变链表的结点结构体本身。但是在销毁操作下，就必须传二级指针，因为销毁操作是将头结点也要删除掉，也就意味着会改变头指针的指向。

双链表中结点类型的描述如下：

typedef int DHCListNode; //每个结点的数值类型为 int

typedef struct DHCList
{
	DHCListNode data;
	struct DHCList* prev;  //前驱指针
	struct DHCList* next;  //后继指针
}DHCList;
1
2
3
4
5
6
7
8

1. 动态申请一个结点

DHCList* BuyDHCListNode(DHCListNode data)
{
	DHCList* newNode = (DHCList*)malloc(sizeof(DHCList));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL; //对于没一个刚申请的结点让其前驱指针和后继指针都指向NULL
	newNode->prev = NULL;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 初始化链表

在对链表的任何操作之前得先创建一个头结点，根据双向循环的特性，需让头结点的prev和next指针都指向其自己。

DHCList* ListInit()
{
	DHCList* pHead = BuyDHCListNode(0);
	if (pHead == NULL)
	{
		return NULL;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
	return pHead;
}
1
2
3
4
5
6
7
8
9
10
11

3. 链表查找

从链表的头结点的后继结点开始逐一匹配，直到找到值相同的结点进行返回，若当查找结点一直后继到头结点时意味着没有该结点，就返回NULL

DHCList* ListFind(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. 在链表的pos位置之前插入元素

void ListInsert(DHCList* pos, DHCListNode data)
{
	assert(pos);
	DHCList* newNode = BuyDHCListNode(data);
	//以下四步不能混乱，如果先执行了三四步，那么就无法通过pos结点找到newnode结点的前驱结点。
	newNode->next = pos;
	newNode->prev = pos->prev;
	pos->prev->next = newNode;
	pos->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10

5. 删除在链表的pos位置的元素

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

6. 链表尾插

链表的尾删可以用链表pos位置插入进行复用，因为链表的插入是在pos位置之前插入，所以在链表尾插的函数里直接将pos改为头结点即可。

void ListPushBack(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead, data);
}
1
2
3
4
5

7. 链表尾删

l链表的尾删同样也可以进行复用，直接将pos改为尾结点即可，也就是头结点的前驱节点。

void ListPopBack(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->prev); //头结点的前驱节点（链表尾结点）
}
1
2
3
4
5

8. 链表头插

链表头插即为将待插结点插在头结点之后。

void ListPushFront(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead->next, data); //
}
1
2
3
4
5

9. 链表头删

void ListPopBack(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->prev); //删除头结点的后继结点
}
1
2
3
4
5

10. 链表清空

该函数意为将链表中除头结点之外的所有结点都销毁。

void ListClear(DHCList* pHead)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		pHead->next = cur->next;
		free(cur);
		cur = pHead->next;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

11. 链表销毁

void ListDestory(DHCList** pHead)  //参数为二级指针
{
	assert(pHead);
	ListClear(*pHead);  //先清空链表，再释放掉头节点即可。
	free(*pHead);
	*pHead = NULL;
}
1
2
3
4
5
6
7

三、源代码及运行结果展示

1.DCHListNode.h

结构体创建及函数声明

#include 
#include 
#include 

typedef int DHCListNode;

typedef struct DHCList
{
	DHCListNode data;
	struct DHCList* prev;
	struct DHCList* next;
}DHCList;

DHCList* ListInit();

DHCList* BuyDHCListNode(DHCListNode data);

DHCList* ListFind(DHCList* pHead, DHCListNode data);

void ListPushBack(DHCList* pHead, DHCListNode data);

void ListPushFront(DHCList* pHead, DHCListNode data);

void ListPopBack(DHCList* pHead);

void ListPopFront(DHCList* pHead);

void ListInsert(DHCList* pos, DHCListNode data);

void ListErase(DHCList* pos);

void ListPrint(DHCList* pHead);

void ListClear(DHCList* pHead);

void ListDestory(DHCList** pHead);

void TestList();
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

2.DCHListNode.c

方法实现

#include "DCHListNode.h"

DHCList* BuyDHCListNode(DHCListNode data)
{
	DHCList* newNode = (DHCList*)malloc(sizeof(DHCList));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

DHCList* ListInit()
{
	DHCList* pHead = BuyDHCListNode(0);
	if (pHead == NULL)
	{
		return NULL;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
	return pHead;
}

DHCList* ListFind(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void ListPushBack(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead, data);
}

void ListPushFront(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead->next, data);
}

void ListPopBack(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->prev);
}

void ListPopFront(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->next);
}

//在pos之前插入
void ListInsert(DHCList* pos, DHCListNode data)
{
	assert(pos);
	DHCList* newNode = BuyDHCListNode(data);
	newNode->next = pos;
	newNode->prev = pos->prev;
	pos->prev->next = newNode;
	pos->prev = newNode;
}

void ListErase(DHCList* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

void ListPrint(DHCList* pHead)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d----", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void ListClear(DHCList* pHead)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		pHead->next = cur->next;
		free(cur);
		cur = pHead->next;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
}

void ListDestory(DHCList** pHead)
{
	assert(pHead);
	ListClear(*pHead);
	free(*pHead);
	*pHead = NULL;
}

void TestList()
{
	DHCList* pHead = ListInit();
	ListPushBack(pHead, 1);
	ListPushBack(pHead, 2);
	ListPushBack(pHead, 3);
	ListPushBack(pHead, 4);
	ListPrint(pHead);

	ListPushFront(pHead, 0);
	ListPrint(pHead);

	ListPopFront(pHead);
	ListPrint(pHead);

	ListPopBack(pHead);
	ListPrint(pHead);

	ListClear(pHead);
	ListPrint(pHead);

	ListDestory(&pHead);
	//ListPrint(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
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

3.test.c

主函数

#include "DCHListNode.h"

int main()
{
	TestList();
	return 0;
}
1
2
3
4
5
6
7

结果展示：

---

总结

  带头结点的双向循环链表的结构比较复杂，所以对链表进行插入删除操作时一定要注意指针指向的先后顺序；还有就是传递的参数为一级指针即可，只有在删除链表时才需传二级指针。
  文章若有不足的地方还请大佬指正！！！