【数据结构】双向链表

🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️

---

一、单向链表的劣势

前面我们讲解了链表8种结构中最为常用的两种结构之一的单向不带头不循环链表的基本概念和实现方法（传送门：单链表）。但是在实现时我们发现了以下局限性：

• 由于单链表是单向的，当我们想进行插入或者删除时，由于无法直接找到前驱结点，导致我们还需再使用一个指针遍历链表找到前一个结点的位置。这就导致了进行插入和删除的时间复杂度为O(N)，时间效率较低。
• 由于我们需要再使用一个指针指向链表前一个结点，这也可能在一些情况下导致出错，例如链表只有一个结点。
• 由于其不带头结点，头指针直接指向第一个有效结点，所以在进行头插等可能改变头指针的操作时我们如果传一级指针就会出错。

---

二、带头双向循环链表

2.1 逻辑结构

那么，我们要如何解决以上劣势呢？这就不得不说到另一种最为常见的链表结构：带头双向循环链表

头结点：所谓头结点，其作用就是标识链表的有效部分。我们之前实现的无头结点的链表，都是通过头指针直接指向链表的有效数据部分。而带头结点的链表，则是用头指针指向一个不存放有效数据的结点，这个结点就称作头结点。这个结点的next指针存放的下一个结点才是链表的有效结点部分。图示如下：

带头双向循环链表：其结构是8种结构中最复杂的，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。此链表的结点在单向链表的基础上，添加了前驱指针prev指向上一个结点，然后添加了上述所描述的头结点，而循环则是体现在首尾结点相连上。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现起来反而更加简单。逻辑结构如下：

注：蓝色箭头代表逻辑上指针的指向，均表示某个结点next或prev指针指向另一个结点，下同。

2.2 结点的代码实现

typedef int LTDataType;//重命名便于维护
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* prev;//指向前一个结点
	struct ListNode* next;//指向后一个结点
}LTNode;
1
2
3
4
5
6
7

---

三、链表的实现

我们同样先在主函数中定义一个头指针用于指向我们的头结点，后续通过这个指针来完成对链表各种接口的实现。由于头指针并不直接指向有效数据部分，有效数据是从第二个结点开始的，因此当我们对数据进行操作时并不需要改变头指针的内容，只需进行传值调用，用一级指针接收即可，可以有效避免头指针被无意修改。

📖3.1 初始化

在使用链表前，我们需要对链表进行初始化。我们可以在初始化接口中创建一个头结点并将其返回给头指针，代码如下：

//创建结点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}

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

	return newnode;
}

//初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);

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

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

📖3.2 头插

对于头插，根据双向循环链表结构图，我们只需将头结点的next指向新结点，新结点的prev指向头结点，next指向下一结点，下一结点的prev指向新结点即可完成头插。具体过程如下：

代码实现如下：

//头插
void LTPushFront(LTNode* phead, LTDataType x)//不改变头指针，无需传址
{
	assert(phead);//保证链表有头结点，即完成了初始化
	LTNode* newnode = BuyLTNode(x);//创建新结点
	LTNode* cur = phead->next;//找到链表头
    //开始头插
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = cur;
	cur->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

📖3.3 尾插

对于尾插，由于双向循环链表结构的特殊性，我们不需要向单链表一样遍历链表找到链表尾，直接通过头结点的prev指针就可直接找到链表尾，也不需要再遍历链表找到上一个结点。代码反而变得更加简单，只需要通过改变结点的prev和next指针即可完成尾插，这就是结构带来的优势。其时间复杂度为O(1)。具体过程如下：

具体代码如下：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//保证链表已经初始化
	LTNode* newnode = BuyLTNode(x);//创建新结点
	LTNode* tail = phead->prev;//找到链表尾
    //开始尾插
	tail->next = newnode;
	newnode->next = phead;
	newnode->prev = tail;
	phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

需要注意的是，与单链表不同，这里是双向循环链表，所以链表尾并不是指向NULL，而是指向头结点。同时不会出现对NULL解引用的情况，不需要对单向链表一样进行分类讨论。

📖3.4 头删

对于头删，我们只需要将头结点指向下一个位置，然后将原来指向的空间free()掉即可。如果链表为空，我们就让函数直接返回，具体动态效果如下：

代码实现如下：

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//找到链表头
	LTNode* next = cur->next;//找到链表头下一个结点
	free(cur);
	phead->next = next;
	next->prev = phead;
}
1
2
3
4
5
6
7
8
9
10

📖3.5 尾删

对于尾删，我们同样通过头结点的prev指针直接找到链表尾，然后进行删除操作，过程与头删类似，时间复杂度为O(1)。具体过程如下：

具体代码如下：

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;//找到链表尾
	LTNode* prev = tail->prev;//找到前驱
	free(tail);
	prev->next = phead;
	phead->prev = prev;
    tail=NULL;
}
1
2
3
4
5
6
7
8
9
10
11

📖3.6 查找

对于查找，其方法与单向链表一样，通过遍历链表的所有结点即可。有一点不同的是我们的双向链表是循环的，因此循环的条件不再是cur！=NULL而是cur！=phead，当cur等于头指针时则说明已经成功遍历一遍了。代码如下：

//查找
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

📖3.7 在pos位置之前插入

对于插入，我们可以实现一个在指定结点前插入一个新结点的接口，而这个指定结点我们可以通过查找接口来获取。由于我们的链表是双向的，我们就可以很容易的得到新结点的前一个与后一个结点的位置，进而实现插入接口，其时间复杂度为O(1)。动态效果如下：

//插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;
    
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

📖3.8 删除pos位置

对于删除，我们同样可以实现一个删除指定结点的接口，而这个指定结点我们依旧可以通过查找接口来获取。同样的，由于结构上的优势，我们可以很方便的直接对指定位置进行删除，时间复杂度为O(1)。具体过程如下：

//删除
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
1
2
3
4
5
6
7
8
9
10

📖3.9 打印

对于打印，很简单，遍历一圈链表即可，当cur等于头结点地址时停止打印。动图效果如下：

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("NULL<=>");
	while (cur!=phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

📖3.10 销毁

对于销毁，我们动态内存申请所得到的空间，当我们不需要的时候，需要我们进行手动销毁。因此，我们还需要一个接口对使用完毕的链表进行free()，具体代码如下：

//销毁
void ListDestroy(LTNode* phead)
{
	assert(phead != NULL); 
	LTNode* cur = phead->next; 
	while (cur != phead) //释放有效结点
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

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

通过上面一个个接口的实现，我们发现：

虽然双向带头循环链表的结构比起单向链表结构复杂太多，但对于各接口的实现反而变得更加方便，并且很多接口时间效率更加地高。因此，一个好的结构不仅可以简化我们的代码量，也可以提高我们代码的效率。

四、完整代码及效果展示

List.h

#pragma once
#include
#include
#include

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
//创建结点
LTNode* BuyLTNode(LTDataType x);
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//大小
int LTSize(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//插入
void LTInsert(LTNode* pos, LTDataType x);
//删除
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);
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

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

//创建结点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}

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

	return newnode;
}

// 初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);

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

	return phead;
}

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("NULL<=>");
	while (cur!=phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* tail = phead->prev;
	tail->next = newnode;
	newnode->next = phead;
	newnode->prev = tail;
	phead->prev = newnode;
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* prev = tail->prev;
	free(tail);
	prev->next = phead;
	phead->prev = prev;

}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* cur = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = cur;
	cur->prev = newnode;
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	LTNode* next = cur->next;
	free(cur);
	phead->next = next;
	next->prev = phead;
}

int LTSize(LTNode* phead)
{
	LTNode* cur = phead->next;
	int LTSize = 0;
	while (cur != phead)
	{
		LTSize++;
		cur = cur->next;
	}
	return LTSize;
}

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

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

//销毁
void LTDestroy(LTNode* phead)
{
	assert(phead != NULL); 
	LTNode* cur = phead->next; 
	while (cur != phead) //释放有效结点
	{
		LTNode* next = cur->next;
		free(cur);
		cur = 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

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListText()
{
	LTNode* plist = NULL;
	//初始化
	plist = LTInit();
	printf("链表起始数据:\n");
	LTPrint(plist);
	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	printf("尾插后数据:\n");
	LTPrint(plist);
	//头插
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);
	LTPushFront(plist, 6);
	printf("头插后数据:\n");
	LTPrint(plist);
	//尾删
	LTPopBack(plist);
	printf("尾删后数据:\n");
	LTPrint(plist);
	//头删
	LTPopFront(plist);
	printf("头删后数据:\n");
	LTPrint(plist);

	//修改数据为5的结点为50
	LTNode* cur1 = LTFind(plist, 5); //找数据为5结点
	if (cur1)
	{
		cur1->data = 50; //查找附带着修改的作用
	}
	printf("修改数据为5的结点为50后\n");
	LTPrint(plist);

	//在date为4的结点前插入数据为7的结点
	LTNode* cur2 = LTFind(plist, 4); //找数据为4结点
	if (cur2)
	{
		LTInsert(plist, cur2, 7); //插入
	}
	printf("在4前插入7后数据:\n");
	LTPrint(plist);
	//删除数据为1的结点
	LTNode* cur3 = LTFind(plist, 1); //找数据为1结点
	if (cur3)
	{
		LTErase(plist, cur3); //删除
	}
	printf("删除1后数据:\n");
	LTPrint(plist);
	//销毁
	LTDestroy(plist);
}
int main()
{
	ListText();
	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

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~