【数据结构】—— 双向链表

1、双向链表的概念

双向链表（Doubly Linked List）是一种常见的链表数据结构，它与普通的单向链表不同之处在于，每个节点除了存储数据元素外，还存储着指向前一个节点和后一个节点的指针（或引用）。

与单链表的区别：双向链表中可以通过节点本身直接访问其前驱节点和后继节点，而不需要像单向链表那样只能从头节点开始顺序访问。

2、双向链表的接口实现

2.1结构

• 双向链表的一个节点由三部分构成
  1）当前节点的数据——date
  2）前驱指针——prev
  3）后驱指针——next

//定义双向链表中节点的结构
typedef int LDateType;
typedef struct ListNode {
	LDateType date;
	struct ListNode* prev;
	struct ListNode* next;
}LNode;
1
2
3
4
5
6
7

带头双向链表:

• 双向链表带有哨兵位，插入数据之前必须要初始化哨兵位
• 哨兵节点（头节点）：本身不存储有效数据，它的存在只是为了简化边界条件的处理。

这里我用双向带头循环链表来实现

2.2初始化

申请节点

对申请节点功能进行封装，方便调用。

//申请节点
LNode* LBuyNode(LDateType x) {
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->date = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

直接调用申请节点函数创建哨兵位

LNode* LInit()
{
	//创建一个哨兵位
	LNode* phead = LBuyNode(-1);
	return phead;
}
1
2
3
4
5
6

2.3插入数据

尾插

当双向链表进行尾插的时候，无需像单链表那样循环找尾节点，双向链表中的尾节点与哨兵位相连，可以直接获取:

ptail = phead->prev

• 思路：在修改指针连接时，优先对newnode的前驱和后驱进行修改，避免影响链表原来的指向，随后对ptail的后驱和phead的前驱进行修改

void LPushBack(LNode* phead, LDateType x)
{
	assert(phead);
	LNode* newnode = LBuyNode(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

头插

与尾插相似，修改对应指针连接即可

void LPushFront(LNode* phead, LDateType x)
{
	assert(phead);
	LNode* newnode = LBuyNode(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

指定位置之后插入数据

对插入数据的位置前驱后驱节点修改指针连接即可
pos-> newnode-> pos->next

void LInsert(LNode* pos, LDateType x) {
	assert(pos);
	LNode* newnode = LBuyNode(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

2.4删除数据

• 思路：修改指针连接，free函数释放被删除节点即可

尾删

void LPopBack(LNode* phead) {
	assert(phead);
	//若哨兵位节点的next指针或prev指针指向的是自己，则链表为空
	assert(phead->next != phead);
	LNode* del = phead->prev;
	LNode* 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

头删

void LPopFront(LNode* phead) {
	assert(phead);
	assert(phead->next != phead);

	LNode* del = phead->next;
	LNode* next = del->next;
	//改变指针指向，删除指定节点即可
	next->prev = phead;
	phead->next = next;
	free(del);
	del = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

指定位置删除

void LErase(LNode* 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

2.5查找

• 功能 ：查找指定节点并返回节点
• 实现思路：创建节点指针pcur指向链表中第一个节点(phead->next),
  遍历链表，查找指定节点，如果找到直接返回节点，停止条件为当pcur指向哨兵位，当跳出循环则链表中不存在指定节点，返回NULL

LNode* LFind(LNode* phead, LDateType x) {
	assert(phead);
	LNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.6打印

• 思路：创建节点指针pcur指向链表中第一个节点(phead->next),
  遍历链表，停止条件为当pcur指向哨兵位，当pcur指向哨兵位则遍历完成

void LPrint(LNode* phead) {
	assert(phead);
	LNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

2.7销毁

• 思路：通过遍历删除每个有效节点，最后删除哨兵位

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

	LNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LNode* 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

3、链表和顺序表的区别

4、问题与思考

Q：二级指针和一级指针应该什么时候用，如何选择？
在单链表和双向链表中，二级指针和一级指针的选择在于是否需要修改(删除)头节点/头指针（在双向链表中叫哨兵位）

在实际应用中：

• 一级指针：直接操作变量和简单数据结构
• 二级指针：用于处理复杂的数据结构(多级链表等)、动态内存分配以及需要改变指针本身(值)指向的情况

代码文件

.h文件

#pragma once

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

//定义双向链表中节点的结构
typedef int LDateType;
typedef struct ListNode {
	LDateType date;
	struct ListNode* prev;
	struct ListNode* next;
}LNode;

//注意，双向链表带有哨兵位，插入数据之前必须要初始化哨兵位
/*void LInit(LNode** plist);*///初始化哨兵位
LNode* LInit();//无需传参初始化哨兵位（函数里面创建哨兵位）

//申请节点
LNode* LBuyNode(LDateType x);

//不需要改变哨兵位，则不需要传二级指针
void LPushBack(LNode* pphead, LDateType x);//尾插

void LPushFront(LNode* phead, LDateType x);//头插(在第一个有效节点之前插入)

//打印双向链表
void LPrint(LNode* phead);

//头删
void LPopFront(LNode* phead);

//尾删
void LPopBack(LNode* phead);

//指定位置之后插入数据
void LInsert(LNode* pos, LDateType x);

//删除pos位置的数据
void LErase(LNode* pos);

//查找
LNode* LFind(LNode* phead, LDateType x);

//链表销毁
void LDestroy(LNode** pphead);//这里是用二级指针销毁
//推荐一级 ——>（保持接口一致性）
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

.c文件

#include "List.h"

//void LInit(LNode** pphead)
//{
//	*pphead = (LNode*)malloc(sizeof(LNode));
//	if (*pphead == NULL)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//	(*pphead)->date = -1;//该数据无作用
//	(*pphead)->next = (*pphead)->prev = *pphead;//或者NULL
//}

LNode* LInit()
{
	//创建一个哨兵位
	LNode* phead = LBuyNode(-1);
	return phead;
}

//申请节点
LNode* LBuyNode(LDateType x) {
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->date = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

//链表的打印
void LPrint(LNode* phead) {
	assert(phead);
	LNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}

//尾插和头插
void LPushBack(LNode* phead, LDateType x)
{
	assert(phead);//双向链表第一个节点不可能为空，无需assert*phead
	LNode* newnode = LBuyNode(x);
	//phead phead->prev(ptail) newnode 修改指针连接
	newnode->next = phead;
	newnode->prev = phead->prev;

	(phead->prev)->next = newnode;
	phead->prev = newnode;
}
void LPushFront(LNode* phead, LDateType x)
{
	assert(phead);
	LNode* newnode = LBuyNode(x);
	// phead newnode phead->next 修改这三个节点的连接
	newnode->next = phead->next;
	newnode->prev = phead;

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

void LPopBack(LNode* phead) {
	assert(phead);
	//若哨兵位节点的next指针或prev指针指向的是自己，则链表为空
	assert(phead->next != phead);
	LNode* del = phead->prev;
	LNode* prev = del->prev;
	//实现结果一致，无需分情况讨论，
	prev->next = phead;
	phead->prev = prev;
	free(del);
	del = NULL;
}

void LPopFront(LNode* phead) {
	assert(phead);
	assert(phead->next != phead);

	LNode* del = phead->next;
	LNode* next = del->next;
	//改变指针指向，删除指定节点即可
	next->prev = phead;
	phead->next = next;
	free(del);
	del = NULL;
}


LNode* LFind(LNode* phead, LDateType x) {
	assert(phead);
	LNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void LInsert(LNode* pos, LDateType x) {
	assert(pos);
	LNode* newnode = LBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

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

void LErase(LNode* pos) {
	assert(pos);

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

	free(pos);
	pos = NULL;
}

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

	LNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LNode* 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
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

测试文件

#include "List.h"

//void ListTest01() {
//	LNode* plist = NULL;
//	LInit(&plist);
//}

void ListTest02() {
	LNode* plist = LInit();//初始化
	//尾插
	LPushBack(plist, 1);
	LPushBack(plist, 3);
	LPushBack(plist, 5);
	LPrint(plist);
}

void ListTest03() {
	LNode* plist = LInit();//初始化
	//尾插
	LPushFront(plist, 1);
	LPushFront(plist, 3);
	LPushFront(plist, 5);
	LPrint(plist);
	LPopBack(plist);
	LPrint(plist);
	LPopBack(plist);
	LPrint(plist);
	LPopBack(plist);
	LPrint(plist);
}

void ListTest04() 
{
	LNode* plist = LInit();//初始化
	//尾插
	LPushFront(plist, 1);
	LPushFront(plist, 3);
	LPushFront(plist, 5);
	LPrint(plist);
	LPopFront(plist);
	LPrint(plist);
	LPopFront(plist);
	LPrint(plist);
	LPopFront(plist);
	LPrint(plist);
}

void ListTest05()
{
	LNode* plist = LInit();//初始化
	//尾插
	LPushFront(plist, 1);
	LPushFront(plist, 3);
	LPushFront(plist, 5);
	LPrint(plist);
	LNode* findRet1 = LFind(plist, 2);
	if (findRet1 == NULL) printf("未找到！\n");
	else printf("找到了！\n");
	LNode* findRet2 = LFind(plist, 3);
	if (findRet2 == NULL) printf("未找到！\n");
	else printf("找到了！\n");
}

void ListTest06()
{
	LNode* plist = LInit();//初始化
	//尾插
	LPushFront(plist, 1);
	LPushFront(plist, 3);
	LPushFront(plist, 5);
	LPrint(plist);
	LNode* findRet1 = LFind(plist, 3);
	LInsert(findRet1, 666);
	LPrint(plist);
	LNode* findRet2 = LFind(plist, 666);
	LErase(findRet2);
	LPrint(plist);
	LDestroy(&plist);
}

int main()
{
	//ListTest01();//由传址的哨兵位初始化
	//ListTest02();//初始化＋尾插
	//ListTest03();//头插+尾删
	//ListTest04();//头删
	//ListTest05();//查找
	ListTest06();//在指定位置之后插入数据,删除数据,销毁链表
	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