今天的重点是双向循环链表，以及附带着链表所有的组合类型

字数很多，很详细，大家收藏起来，慢慢品尝😉😉😉

单链表的缺点

🎤由上一节我们理解了单链表（单向不带头非循环链表），发现它虽然相比顺序表是有一定的优势的，但是它的缺陷也是不可忽视的。

• 1.假如找一个数据只能从前向后依次遍历，而且链表中一旦一个结点的地址丢失了，这个结点往后所有的结点都找不到了；
• 2.PopBack（尾删），Insert（任插），Erase（任删）的时间复杂度都是O(N)，都是需要从头开始找前一个结点；
• 3.几乎每个接口都需要判断链表是否为空，比较麻烦。
  针对这些缺陷的解决方案是什么呢?————>>双链表（双向带头循环链表），也就是这节的重点。

---

链表的八种组合类型

🎤链表分别有六个特点，如：

• 单向，双向
• 带头，不带头
• 循环，非循环

由这六个特点可以组合成八种链表结构，下面给大家简单介绍一下这八种链表结构:

---

单向带头循环链表

🎤头结点（哨兵位）是不能存储有效数据的

---

单向带头非循环链表

---

单向不带头循环链表

---

单向不带头非循环链表

---

双向带头循环链表

---

双向带头非循环链表

---

双向不带头循环链表

---

双向不带头非循环链表

---

带头结点的优点

🎤不管链表如何，都有一个头结点在那里，但是这个头结点不存储有效数据，
尾插的话直接链接在头结点后面就行，这样我们几乎用不到二级指针了，因为我们并不会改变外面的指针，而是在这个结点后面去链接，哪怕链表为空，所以带头结点的链表尾插判断会更简单

🎤1.头删也是如此，如果是不带头单链表，插入一个数据的话，需要让plist向后移动一位，删除前一个，如：
🎤2.如果是带头链表的话，删除第一个结点，然后将头结点链接到第二个结点上即可，如：

🎤所以大家清晰的可以了解：

• 带头结点不需要改变传过来的指针，也就意味着不需要传二级指针，
• 头结点是不存储有效数据的，更不能存储链表的长度。

---

对于链表部分来说，两个极端是最重要的——单向不带头非循环链表和双向带头循环链表， 但是单向不带头非循环链表结构简单，一般用的地方不多，而双向带头循环链表结构复杂，用途广泛，而且它结构的优势在接下来的实现中大家可以清晰可见。

---

双向带头循环链表

双链表结构的定义

🎤双链表中的每一个结点有两个指针域和一个数据域。两个指针域分别是prev（前驱）和next（后驱），分别指向前一个结点和指向后一个结点，数据域就是data用来存放数据的。

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//前驱指针
	LTDataType data;
	struct ListNode* next;//后继指针
}ListNode;
1
2
3
4
5
6
7

---

结点的创建

🎤开辟新结点，能用到这个函数的接口肯定就是插入函数，x就是待插入数据，前驱和后驱指针先置为空，方便链接。

ListNode*BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9

---

双链表的初始化（头结点的创建）

🎤既然是带头结点的链表，肯定要有一个头结点，而且这个头结点的两个指针域要指向自己， 如：

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
1
2
3
4
5
6
7
8

🎤这里我们用的是返回值是一个指针，这样就不用传址调用，只是要phead去构建新节点返回给plist，并不需要对plist进行改动。

---

双链表的销毁

🎤定义两个指针cur和next，从头开始，next记录cur的下一个结点，然后循环依次释放

🎤加上一个断言，让代码风格更好，同时出现问题更好的纠正。

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

双链表的基本接口实现（增删查改）

1.双链表的打印

🎤打印是不需要打印phead的，当然它也没有数据，就让cur指向第一个数据的结点，当cur=phead的时候结束

void ListPrint(ListNode* phead)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

---

2.双链表的尾插

🎤在单链表中尾插找最后一个结点的时候需要从头遍历，但是对于双链表来说，phead的前驱指向的就是链表最后一个结点，即为tail，然后将newnode链接到tail的后面，再将newnode链接到头结点（phead）上，使其在此形成循环即可。

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

🎤相比上一节，不需要考虑链表是否为空的情况，结构虽然复杂了，但是操作简单了。

---

3.双链表的头插

🎤头插也就是在第一个有效数据前，phead头结点后面插入，那么既然是链表就很容易找到phead后面的结点，暂且叫做first，然后就还是链接，将newnode和头结点接上，然后再和first接上。

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

🎤那么头插难道也不需要判断是否为空了吗？————对

🎤由于first=phead->next，所以first还是phead。

---

4.双链表的尾删

🎤尾删和头删也是很相似的，需要两个指针，一个指针指向链表最后一个结点（tail），另外一个指向倒数第二个结点（prev），然后将prev和头结点链接，释放tail。

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;

	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

5.双链表的头删

🎤定义两个指针，first指向第一个结点，second指向第二个结点，先将头结点phead和第二个数据second链接，然后释放first。

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* first = phead->next;
	ListNode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

	ListErase(phead->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🎤有一个问题😧就是如果链表只有一个头结点，也就是为空的话，最后会把自己free，所以加上一个断言处理一下。

---

6.双链表的查找

🎤和打印很相似，用cur去遍历链表，当cur=phead的时候结束，并返回pos位置的指针。

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

---

7.pos位置之前插入

🎤先通过Find查找函数找到pos，并返回的指针，然后找到pos的前一个结点（prev），下一步开始链接。

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

🎤大家也可以只用一个指针pos进行链接，但是对于链接顺序有严格的要求，大家可以试一试。😎😎😎

---

8.删除pos位置的值

🎤用Find返回pos的指针，然后对pos的前后进行标记，分别是prev和next，链接prev和next（prev->next=next ; next->prev=prev ; ）释放掉pos即可。

void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
1
2
3
4
5
6
7
8
9
10

---

9.更改pos位置的值

🎤Find查找函数返回的就是pos位置的地址，直接对数据域赋值就可以了。

void ListModity(ListNode* pos, LTDataType x)
{
	assert(pos);

	pos->data = x;
}

1
2
3
4
5
6
7

---

到这里，我相信大家对链表的所有结构已经基本掌握了🎉🎉🎉，有错误大家可以指出哦，有疑问也可以问我，大家共同进步，后续会持续更新《数据结构》的相关内容，大家喜欢的话可以关注一下，😚😚😚
下面是项目代码，大家参考一下。

---

代码参考

🎤最终会发现，所有的插入都可以用Insert函数，所有的删除都可以用Erase函数，下面是代码大家看一下。

List.h

#pragma once

#include
#include
#include

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//前驱指针
	LTDataType data;
	struct ListNode* next;//后继指针
}ListNode;

ListNode* BuyListNode(LTDataType x);//链表结构的创建
ListNode* ListInit();//初始化
void ListDestory(ListNode* phead);//销毁
void ListPushBack(ListNode* phead, LTDataType x);//尾插
void ListPushFront(ListNode* phead, LTDataType x);//头插
void ListPopBack(ListNode* phead);//尾删
void ListPopFront(ListNode* phead);//头删

ListNode* ListFind(ListNode* phead, LTDataType x);//查找
void ListInsert(ListNode* pos, LTDataType x);//pos位置之前插入
void ListErase(ListNode* pos);//删除pos位置的值

void ListModity(ListNode*pos, LTDataType x);//更改


void ListPrint(ListNode* 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

---

List.c

#include "List.h"

ListNode*BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

void ListPrint(ListNode* phead)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	//ListNode* tail = phead->prev;
	//ListNode* newnode = BuyListNode(x);

	//tail->next = newnode;
	//newnode->prev = tail;

	//newnode->next = phead;
	//phead->prev = newnode;
	ListInsert(phead->prev, x);
}

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	//ListNode* first = phead->next;
	//ListNode* newnode = BuyListNode(x);

	//phead->next = newnode;
	//newnode->prev = phead;

	//newnode->next = first;
	//first->prev = newnode;
	ListInsert(phead->next, x);
}

//头插的第二种方法
//void ListPushFront(ListNode* phead, LTDataType x)
//{
//	assert(phead);
//
//	ListNode* newnode = BuyListNode(x);
//	newnode->next = phead->next;
//	phead->next->prev = newnode;
//
//	phead->next = newnode;
//	newnode->prev = phead;
//}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	//assert(phead->next != phead);

	//ListNode* tail = phead->prev;
	//ListNode* prev = tail->prev;

	//prev->next = phead;
	//phead->prev = prev;

	//free(tail);
	//tail = NULL;

	ListErase(phead->prev);
}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	//assert(phead->next != phead);
	//ListNode* first = phead->next;
	//ListNode* second = first->next;

	//phead->next = second;
	//second->prev = phead;

	//free(first);
	//first = NULL;

	ListErase(phead->next);
}

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

void ListModity(ListNode* pos, LTDataType x)
{
	assert(pos);

	pos->data = x;
}
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

---

Test.c

#include "List.h"

void TestList1()
{
	ListNode* plist = ListInit();
	
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	ListPushFront(plist, 0);
	ListPushFront(plist, -1);
	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	//ListPopFront(plist);
	//ListPopFront(plist);
	//ListPopFront(plist);
	ListPrint(plist);

	ListPopBack(plist);
	ListPrint(plist);

	ListDestory(plist);
}

void TestList2()
{
	ListNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	ListNode* pos = ListFind(plist, 3);
	if (pos)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没有找到\n");
	}
	ListPrint(plist);

	ListInsert(pos, 30);
	ListPrint(plist);

	ListErase(pos);
	ListPrint(plist);

	pos = ListFind(plist, 4);
	ListModity(pos,8);
	ListPrint(plist);

	ListDestory(plist);

}
int main()
{
	//TestList1();
	TestList2();

	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

---