【（数据结构）— 双向链表的实现】

一.双向链表的结构

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨
的”
“哨兵位”存在的意义：
遍历循环链表避免死循环。

二. 双向链表的实现

2.1 头文件 ——双向链表的创建及功能函数的定义

List.h
1

#pragma once
#include
#include
#include
#include

typedef int LTDatatype;
//链表的结构创建
typedef struct ListNode
{
	LTDatatype data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
//打印
void LTPrint(LTNode* phead);



//双链表的初始化//销毁
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁
//void LTDestroy(LTNode** pphead);
void LTDestroy(LTNode* phead);
//头部/尾部/插入/删除
//尾插
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//再pos位置之后插入/删除 
void LTInsrt(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos);
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype 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

2.2 源文件 ——双向链表的功能函数的实现

List.c
1

#include"List.h"

//初始化
//二级指针初始化
//前提是我们需要传入一个头节点
//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	if (*pphead == NULL)
//	{
//		perror("malloc error");
//		return;
//	}
//	(*pphead)->data = -1;//哨兵位
//	(*pphead)->next = (*pphead)->prev = *pphead;
//	
//}
//一级指针初始化
//不需要传参，只需要返回一个地址即可
LTNode* LTInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->prev = phead;
	return phead;
}
//链表的销毁
//参数是二级指针
//void LTDestroy(LTNode** pphead)
//{
//	assert(pphead && *pphead);
//	LTNode* cur = (*pphead)->next;
//	while(cur!=(*pphead))
//	{
//		LTNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//}
//参数是一级指针
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)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
	

}
LTNode* LTBuyNode(LTDatatype x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	node->data = x;
	node->next = node->prev = NULL;
	return node;
}
//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{
	LTNode* node = LTBuyNode(x);
	//先处理插入的节点的前驱和后继指针
	node->next = phead;
	node->prev = phead->prev;
	//然后考虑哨兵位的前驱和尾节点的后继指针
	phead->prev->next = node;
	phead->prev = node;

}
//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{
	assert(phead);
	LTNode* node = LTBuyNode(x);
	//先处理插入节点的前驱和后继的指针
	node->next = phead->next;
	node->prev = phead;
	//然后处理phead,phead->next
	phead->next->prev = node;
	phead->next = node;

}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表不能为空，链表中只有一个哨兵位节点
	assert(phead->next != phead);

	LTNode* del = phead->prev;
	//先处理 del->prev
	del->prev->next = phead;
	//接着处理phead
	phead->prev = del->prev;
	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;
	//先处理del->next
	del->next->prev = phead;
	//接着处理phead
	phead->next = del->next;
	free(del);
	del = NULL;
}
//在pos位置之后插入
void LTInsrt(LTNode* pos, LTDatatype x)
{
	LTNode* node = LTBuyNode(x);
	//先处理node的前驱和后继
	node->next = pos->next;
	node->prev = pos;
	//接着处理pos->next,pos->next->prev
	pos->next = node;
	pos->next->prev = node;
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x)
{
	assert(phead);
	LTNode* 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
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

2.3 源文件 ——双向链表功能的测试

test.c
1

#include"List.h"


void ListTest()
{
	/*LTNode* plist = NULL;
	LTInit(&plist);*/
	//初始化
	LTNode* plist = LTInit();
	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	//头插
	/*LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);*/
	//尾删
	/*LTPopBack(plist);
	LTPopBack(plist);*/
	//头删
	/*LTPopFront(plist);
	LTPopFront(plist);*/
	LTNode* find = LTFind(plist, 4);
	//在pos位置之后插入
	/*LTInsrt(find, 5);*/
	//删除pos位置的数据
	LTErase(find);
	LTPrint(plist);
	//销毁链表
	//LTDestroy(&plist);
	//一级指针销毁需要手动将plist置空
	LTDestroy(plist);
	plist = NULL;

}


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

2.4 双向链表各项功能测试运行展示

2.4.1 双向链表的初始化 ——（以调试窗口展示）

//初始化
LTNode* plist = LTInit();
1
2

2.4.2 双向链表的尾插 ——（以打印展示）

//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
1
2
3
4
5

2.4.3 双向链表的头插 ——（以打印展示）

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

2.4.4 双向链表的尾删 ——（以打印展示）

//尾删
LTPopBack(plist);
LTPopBack(plist);
1
2
3

2.4.5 双向链表的头删 ——（以打印展示）

//头删
LTPopFront(plist);
LTPopFront(plist);
1
2
3

2.4.6 双向链表的查找指定位置及在指定位置之后插入 ——（以打印展示）

//查找指定位置pos
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
LTInsrt(find, 5);
1
2
3
4

2.4.7 双向链表的查找指定位置及删除指定位置的数据 ——（以打印展示）

// //查找指定位置pos
LTNode* find = LTFind(plist, 4);
//删除pos位置的数据
LTErase(find);
1
2
3
4

2.4.8 双向链表的销毁 ——（以调试窗口展示）

//销毁链表
//LTDestroy(&plist);
//一级指针销毁需要手动将plist置空
LTDestroy(plist);
plist = NULL;
1
2
3
4
5

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