数据结构-双向链表(c++)超全超详细_c++双向链表

---

前言

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、双向链表是什么？

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prev和next，分别指向其前驱结点和后继结点。

二、双向链表上的基本操作

1.定义双向链表

代码如下（示例）：

typedef struct DoubleLinkList {

	int data;		//结点的数据域

	DoubleLinkList* next;	//下一个结点的指针域

	DoubleLinkList* prev;	//上一个结点的指针域

}DoubleLinkList,DoubleLinkNode;
1
2
3
4
5
6
7
8
9

2.初始化双链表

代码如下（示例）：

bool DoubleLinkListInit(DoubleLinkList* &L) {	//构造一个空的双向链表

	L = new DoubleLinkNode;	//生成新结点作为头结点，用头指针L指向新结点
	if (!L)return false;		//生成结点失败

	L->next = NULL;		//头结点的next指针域指空
	L->prev = NULL;		//头结点的prev指针域指空
	L->data = -1;

	return true;
}
1
2
3
4
5
6
7
8
9
10
11

3.前插法创建双链表

代码如下（示例）：

bool DoubleLinkListInsertFront(DoubleLinkList*& L, DoubleLinkNode* node) {

	if (!L || !node) return false;

	
	if (L->next == NULL) {//只有头结点
		node->next = NULL;
		node->prev = L;		//新结点的prev指针指向头结点
		L->next = node;		//头结点的next指针指向新结点
	}
	else {
		L->next->prev = node;	//第二个结点的prev指向新结点
		node->next = L->next;	//新结点的next指向第二个结点
		node->prev = L;			//新结点的prev指向第一个结点
		L->next = node;			//第一个结点的next指向新结点
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.尾插法创建双链表

代码如下（示例）：

bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node) {

	DoubleLinkNode* last = NULL;

	if (!L || !node) return false;

	last = L;

	while (last->next) last = last->next;

	node->next = NULL;
	node->prev = last;
	last->next = node;

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

5.双向链表的遍历输出

代码如下（示例）：

void DoubleLinkListPrint(DoubleLinkList* &L) {

	DoubleLinkNode* p=L;

	if (!L) {
		cout << "链表为空" << endl;
		return;
	}

	cout << p->data << "  ";
	while (p->next) {
		cout << p->next->data << "  ";
		p = p->next;
	}

	//逆向打印
	cout << endl << "逆向打印" << endl;
	while (p) {
		cout << p->data << " ";
		p = p->prev;
	}
	cout << endl;

	return;
}
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

6.双链表的指定位置插入

代码如下（示例）：

bool DoubleLinkListInsert(DoubleLinkList* L,int i,int e) {

	if (!L || !L->next) return false;
	if (i < 1)return false;

	int j = 0;
	DoubleLinkList* p, * s;
	p = L;

	while (p && j < i) {//查找位置为i的结点，p指向该结点
		p = p->next;
		j++;
	}

	if (!p || j != i) {
		cout << "结点不存在" << i << endl;
		return false;
	}

	s = new DoubleLinkNode;
	s->data = e;

	s->next = p;
	s->prev = p->prev;

	p->prev->next = s;
	p->prev = s;

	return true;
}
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

7.双链表的按位取值

代码如下（示例）：

bool DoubleLinkListGetElem(DoubleLinkList* &L,int i,int& e) {

	int index;
	DoubleLinkList* p;

	if (!L || !L->next) return false;

	p = L->next;
	index = 1;

	while (p || index < i) { //链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;		//p指向下一个结点
		index++;				//计数器index加1
	}

	if (!p || index > i) {
		return false;   //i值不合法，i>n或i<=0
	}

	e = p->data;

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

8.双链表的任意位置删除

代码如下（示例）：

bool DoubleLinkListDelete(DoubleLinkList*& L, int i) {

	DoubleLinkList* p;
	int index = 0;

	if (!L || !L->next) {
		cout << "双向链表为空！" << endl;
		return false;
	}
	if (i < 1) {
		cout << "不能删除头结点!" << endl;
		return false;
	}
	p = L;

	while (p && index < i) {
		p = p->next;
		index++;
	}
	if (!p)return false; //当结点不存在时，返回失败

	p->prev->next = p->next;
	if(p->next!=nullptr)
		p->next->prev = p->prev;

	delete p;

	return true;
}
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

9.双链表的销毁

代码如下（示例）：

void DoubleLinklistDestroy(DoubleLinkList*  &L) {

	DoubleLinkList* p = L;
	cout << "销毁链表" << endl;

	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

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

三、全部代码(主函数部分比较凌乱）

#include<iostream>
using namespace std;

typedef struct DoubleLinkList {

	int data;		//结点的数据域

	DoubleLinkList* next;	//下一个结点的指针域

	DoubleLinkList* prev;	//上一个结点的指针域

}DoubleLinkList,DoubleLinkNode;


bool DoubleLinkListInit(DoubleLinkList* &L) {	//构造一个空的双向链表

	L = new DoubleLinkNode;	//生成新结点作为头结点，用头指针L指向新结点
	if (!L)return false;		//生成结点失败

	L->next = NULL;		//头结点的next指针域指空
	L->prev = NULL;		//头结点的prev指针域指空
	L->data = -1;

	return true;
}


//前插法
bool DoubleLinkListInsertFront(DoubleLinkList*& L, DoubleLinkNode* node) {

	if (!L || !node) return false;

	
	if (L->next == NULL) {//只有头结点
		node->next = NULL;
		node->prev = L;		//新结点的prev指针指向头结点
		L->next = node;		//头结点的next指针指向新结点
	}
	else {
		L->next->prev = node;	//第二个结点的prev指向新结点
		node->next = L->next;	//新结点的next指向第二个结点
		node->prev = L;			//新结点的prev指向第一个结点
		L->next = node;			//第一个结点的next指向新结点
	}
	return true;
}


//尾插法
bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node) {

	DoubleLinkNode* last = NULL;

	if (!L || !node) return false;

	last = L;

	while (last->next) last = last->next;

	node->next = NULL;
	node->prev = last;
	last->next = node;

	return true;
}


//双向链表的遍历输出
void DoubleLinkListPrint(DoubleLinkList* &L) {

	DoubleLinkNode* p=L;

	if (!L) {
		cout << "链表为空" << endl;
		return;
	}

	cout << p->data << "  ";
	while (p->next) {
		cout << p->next->data << "  ";
		p = p->next;
	}

	//逆向打印
	cout << endl << "逆向打印" << endl;
	while (p) {
		cout << p->data << " ";
		p = p->prev;
	}
	cout << endl;

	return;
}


//指定位置插入
bool DoubleLinkListInsert(DoubleLinkList* L,int i,int e) {

	if (!L || !L->next) return false;
	if (i < 1)return false;

	int j = 0;
	DoubleLinkList* p, * s;
	p = L;

	while (p && j < i) {//查找位置为i的结点，p指向该结点
		p = p->next;
		j++;
	}

	if (!p || j != i) {
		cout << "结点不存在" << i << endl;
		return false;
	}

	s = new DoubleLinkNode;
	s->data = e;

	s->next = p;
	s->prev = p->prev;

	p->prev->next = s;
	p->prev = s;

	return true;
}


//双向链表按位取值
bool DoubleLinkListGetElem(DoubleLinkList* &L,int i,int& e) {

	int index;
	DoubleLinkList* p;

	if (!L || !L->next) return false;

	p = L->next;
	index = 1;

	while (p || index < i) { //链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;		//p指向下一个结点
		index++;				//计数器index加1
	}

	if (!p || index > i) {
		return false;   //i值不合法，i>n或i<=0
	}

	e = p->data;

	return true;
}


//任意位置删除
bool DoubleLinkListDelete(DoubleLinkList*& L, int i) {

	DoubleLinkList* p;
	int index = 0;

	if (!L || !L->next) {
		cout << "双向链表为空！" << endl;
		return false;
	}
	if (i < 1) {
		cout << "不能删除头结点!" << endl;
		return false;
	}
	p = L;

	while (p && index < i) {
		p = p->next;
		index++;
	}
	if (!p)return false; //当结点不存在时，返回失败

	p->prev->next = p->next;
	if(p->next!=nullptr)
		p->next->prev = p->prev;

	delete p;

	return true;
}


//销毁双向链表
void DoubleLinklistDestroy(DoubleLinkList*  &L) {

	DoubleLinkList* p = L;
	cout << "销毁链表" << endl;

	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}








int main() {
	
	DoubleLinkList* L;
	DoubleLinkList* s;

	//1.初始化一个空的双向链表
	if (DoubleLinkListInit(L)) {
		cout << "初始化链表成功!" << endl;
	}
	else {
		cout << "初始化链表失败！" << endl;
	}

	//2.使用前插法插入数据
	int n;

	cout << "使用前插法创建双向链表" << endl;
	cout << "请输入元素个数：";
	cin >> n;
	cout << endl << "依次输入" << n << "个元素: ";

	while (n > 0) {
		s = new DoubleLinkNode;
		cin >> s->data;
		DoubleLinkListInsertFront(L, s);
		n--;
	}

	DoubleLinkListPrint(L);

	//3.使用尾插法插入数据
	
	cout << "使用尾插法创建双向链表" << endl;
	cout << "请输入元素个数：";
	cin >> n;
	cout << endl << "依次输入" << n << "个元素: ";

	while (n > 0) {
		s = new DoubleLinkNode;
		cin >> s->data;
		DoubleLinkListInsertBack(L, s);
		n--;
	}


	DoubleLinkListPrint(L);

	//4.任意位置插入元素
	for (int j = 0; j < 3; j++) {
		int i, x;
		cout << "请输入要插入的位置和元素(用空格隔开):";
		cin >> i >> x;

		if (DoubleLinkListInsert(L, i, x)) {
			cout << "插入成功！" << endl;
		}
		else {
			cout << "插入失败！" << endl;
		}
		DoubleLinkListPrint(L);
	}

	//5.双向链表删除元素
	if (DoubleLinkListDelete(L, 2)) {
		cout << "删除链表第2个元素成功" << endl;
	}
	else
		cout << "删除链表第2个元素失败！" << endl;


	DoubleLinkListPrint(L);

	//6.销毁链表
	DoubleLinklistDestroy(L);


	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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285

总结

以上就是今天要讲的内容，本文仅仅简单介绍了双向链表的基本操作，如有错误，欢迎大家指针，看完记得点个赞。