【C语言|数据结构】双向链表

前言

各位小伙伴大家好，即上回的单向链表之后，双向链表来了，他和单向链表的主要区别就是，他有两个指针，同时指向前面一个节点，和后面一个节点，简直是完美，几乎解决的单向链表的大多数难题

1、初步认识双向链表

1.1 定义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向前面一个节点和后面一个节点。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

1.2 结构

这是带头的双向循环链表。

1.3 节点的存储

typedef int DLDataType;

typedef struct LinkNode
{
	DLDataType data;
	struct LinkNode* next;
	struct LinkNode* prv;
}LNode;
1
2
3
4
5
6
7
8

2、双向链表的接口函数

2.1 链表的节点的动态申请

LTNode* LTFound(DLDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));

	if (newNode == NULL)
	{
		perror("LTInit()::malloc()");
		return;
	}

	newNode->next = newNode->prv = newNode;
	newNode->data = x;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 链表的初始化

// 法一：
LTNode* LTInit()
{
	LTNode* newhead = LTFound(-1);

	return newhead;
}
法二：
void LTInit(LTNode** pphead)
{
	LTNode* newhead = LTFound(-1);
	*phead = newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 尾插

void LTPushBack(LTNode* phead, DLDataType x)
{
	assert(phead);
	 
	LTNode* cmp = LTFound(x);

	// phead phead->prv cmp
	cmp->next = phead;
	cmp->prv = phead->prv;

	phead->prv->next = cmp;
	phead->prv = cmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

尾插这个节点不管是插入在头节点的前面还是尾节点后面都是一样的

2.4 头插

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

	LTNode* tmp = LTFound(x);

	// phead tmp phead->next

	tmp->next = phead->next;
	tmp->prv = phead;

	phead->next = tmp;
	phead->next->prv = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

头插必须插入在头节点的后面才是头插，头节点就是哨兵卫，链表进行操作的时候不能操作哨兵卫，否则就不带头了。

2.5 头删

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

	phead->next = cur->next;
	cur->next = phead;

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

2.5 尾删

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);

	LTNode* cur = phead->prv;
	
	// phead cur->prv cur
	phead->prv = cur->prv;
	cur->prv->next = phead;

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

2.6 在pos节点后面添加数据

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

	LTNode* cur = LTCreate(x);

	// pos cur pos->next
	cur->next = pos->next;
	cur->prv = pos;

	pos->next = cur;
	pos->next->prv = cur;

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

2.6 删除pos节点

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);

	// pos->prv pos pos->next

	pos->prv->next = pos->next;
	pos->next->prv = pos->prv;

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

3、双向链表的实现：

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

typedef int DLDataType;

typedef struct LinkNode
{
	DLDataType data;
	struct LinkNode* next;
	struct LinkNode* prv;
}LTNode;

//双链表的节点创建
LTNode* LTCreate(DLDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));

	if (newNode == NULL)
	{
		perror("LTInit()::malloc()");
		exit(-1);
	}

	newNode->next = newNode;
	newNode->prv = newNode;
	newNode->data = x;
	return newNode;
}

//初始化
//void LTInit(LTNode** pphead)
//{
//	LTNode* newhead = LTFound(-1);
//}

LTNode* LTInit()
{
	LTNode* newhead = LTCreate(-1);

	return newhead;
}

//销毁链表
void LTDesTroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

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

	free(phead);
	phead = NULL;
}

//链表的打印
void LTPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//查找pos节点
LTNode* LTFind(LTNode* phead, DLDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, DLDataType x)
{
	assert(phead);

	LTNode* cmp = LTCreate(x);

	// phead phead->prv cmp
	cmp->next = phead;
	cmp->prv = phead->prv;

	phead->prv->next = cmp;
	phead->prv = cmp;
}

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

	LTNode* tmp = LTCreate(x);

	// phead tmp phead->next

	tmp->next = phead->next;
	tmp->prv = phead;

	phead->next = tmp;
	phead->next->prv = tmp;
}


//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);

	LTNode* cur = phead->prv;

	// phead cur->prv cur
	phead->prv = cur->prv;
	cur->prv->next = phead;

	free(cur);
	cur = NULL;
}

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

	LTNode* cur = phead->next;
	// phead  cur cur->next

	phead->next = cur->next;
	cur->next = phead;

	free(cur);
	cur = NULL;
}

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

	LTNode* cur = LTCreate(x);

	// pos cur pos->next
	cur->next = pos->next;
	cur->prv = pos;

	pos->next = cur;
	pos->next->prv = cur;

}

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);

	// pos->prv pos pos->next

	pos->prv->next = pos->next;
	pos->next->prv = pos->prv;

	free(pos);
	pos = NULL;
}


void DLinkListText()
{
	LTNode* phead = LTInit();

	LTPushBack(phead, 1);
	LTPushBack(phead, 2);
	LTPushBack(phead, 3);
	LTPrint(phead);

	LTPushFront(phead, 0);
	LTPushFront(phead, 999);
	LTPrint(phead);

	// LTPopFront(phead);
	// LTPrint(phead);

	LTPopBack(phead);
	LTPrint(phead);

	LTDesTroy(phead);
}
	



int main()
{
	DLinkListText();
	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
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