双向链表专题

目录

• 双向链表的结构
• 双向链表的实现
• 顺序表和双向链表的优缺点分析

1. 双向链表的结构

注意：

这⾥的“带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

1. 定义双向链表中节点的结构

//定义双向链表中节点的结构
typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
1
2
3
4
5
6
7
8
9

2. 初始化

注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位

void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == *pphead)
	{
		perror("malloc fail!");
		exit(1);
	}

	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

也可以这样写：

LTNode* LTInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == phead)
	{
		perror("malloc fail!");
		exit(1);
	}

	phead->data = -1;
	phead->next = phead->prev = phead;

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

3. 尾插

概念： 当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的。

不需要改变哨兵位，则不需要传二级指针；如果需要修改哨兵位的话，则传二级指针。

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == newnode)
	{
		perror("malloc fail!");
		exit(1);
	}

	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev(ptail) newnode
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
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

因为写了申请新节点的函数，所以上面的初始化代码可以优化：

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);

	return phead;
}
1
2
3
4
5
6

4. 打印

void LTPrint(LTNode* phead)
{
	//phead不能为空
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}

	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5. 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

6. 尾删

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

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

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

7. 头删

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* del = phead->next;
	LTNode* next = del->next;

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

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

8. 查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (x == pcur->data)
		{
			return pcur;
		}

		pcur = pcur->next;
	}

	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

9. 在pos位置之后插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

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

10. 删除pos位置的数据

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);

	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

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

11. 销毁

void LTDesTroy(LTNode** pphead)
{
	assert(pphead);
	//哨兵位不能为空
	assert(*pphead);

	LTNode* pcur = (*pphead)->next;

	while (pcur != *pphead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}

	//链表中只有一个哨兵位
	free(*pphead);
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

也可以这样写：

void LTDesTroy(LTNode* phead)
{
	//哨兵位不能为空
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}

	//链表中只有一个哨兵位
	free(phead);
	phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

但是要注意：这样写要在调用完函数后再写一句 plist = NULL;

这两种写法我们更推荐第二种：推荐传一级指针**（保持接口一致性）**

完整代码：

//List.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//定义双向链表中节点的结构
typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);//推荐传一级指针（保持接口一致性）

void LTPrint(LTNode* phead);

//概念：当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的
//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(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
38
39
40
41

//List.c

#include "List.h"

//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//
//	if (NULL == *pphead)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == newnode)
	{
		perror("malloc fail!");
		exit(1);
	}

	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//LTNode* LTInit()
//{
//	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//
//	if (NULL == phead)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//
//	phead->data = -1;
//	phead->next = phead->prev = phead;
//
//	return phead;
//}

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);

	return phead;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev(ptail) newnode
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

void LTPrint(LTNode* phead)
{
	//phead不能为空
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}

	printf("\n");
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

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

	free(del);
	del = NULL;
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* del = phead->next;
	LTNode* next = del->next;

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

	free(del);
	del = NULL;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (x == pcur->data)
		{
			return pcur;
		}

		pcur = pcur->next;
	}

	return NULL;
}

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

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

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);

	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

//void LTDesTroy(LTNode** pphead)
//{
//	assert(pphead);
//	//哨兵位不能为空
//	assert(*pphead);
//
//	LTNode* pcur = (*pphead)->next;
//
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//
//	//链表中只有一个哨兵位
//	free(*pphead);
//	*pphead = NULL;
//}

void LTDesTroy(LTNode* phead)
{
	//哨兵位不能为空
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}

	//链表中只有一个哨兵位
	free(phead);
	phead = 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
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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

//Test.c

#include "List.h"

void ListTest01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);

	LTNode* plist = LTInit();
	//尾插
	//LTPushBack(plist, 1);
	//LTPushBack(plist, 2);
	//LTPushBack(plist, 3);
	//LTPushBack(plist, 4);
	//LTPrint(plist);

	//头插
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

	//头删
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);

	LTNode* findRet = LTFind(plist, 3);

	//if (NULL == findRet)
	//{
	//	printf("未找到！\n");
	//}
	//else
	//{
	//	printf("找到了！\n");
	//}

	//在指定位置之后插入数据
	//LTInsert(findRet, 66);
	//LTPrint(plist);

	//删除pos位置的节点
	LTErase(findRet);
	LTPrint(plist);

	//LTDesTroy(&plist);
	LTDesTroy(plist);
	plist = NULL;
}

int main()
{
	ListTest01();

	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

3. 顺序表和双向链表的优缺点分析