双向链表超详解——连我奶奶都能学会的复杂链表(带头双向循环)

---

前言

前面学过单向链表，单向链表其实就是单向不带头的非循环链表，它不能随机查找，必须从第一个结点开始一个一个的遍历，查找效率比较低，且只有一个指向下一个结点的指针next，它想找到上一个结点还是比较困难的，所以我们今天学习的双向链表就很好的弥补了它的一些缺点。

---

一、双向链表的概念

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

如图所示：

二、双向链的结构设计

三、双链表的基本功能接口

如下所示：

//初始化
LTNode* LTInit();

//打印
void LTPrint(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead,LTDateType x);

//尾删
void LTPopBack(LTNode* phead);

//头插
void LTPushFront(LTNode* phead,LTDateType x);

//头删
void LTPopFront(LTNode* phead);

//在pos前插入
void LTInsert(LTNode* pos,LTDateType x);

//删除pos位置的结点
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

四、双向链表接口的实现

在此之前先看看双链表的大致模样，如下图：

4.1、创建结点

使用malloc函数开辟动态内存空间，在开辟的同时不要忘记检查是否开辟成功，若开辟成功，将新结点的prev和next指针都指向NULL（空），并将X赋值给新结点的数据data，最后返回该结点

LTNode* CreateLNode(LTNode* phead,LTDateType x)
{
	//开辟新结点
	LTNode* newnode=(LTNode*)malloc(sizeof(LTNode));
	//判断malloc是否成功开辟
	if(newnode==NULL)
	{
		printf("malloc fali");
		exit(-1);
	}
	newnode->next=NULL;
	newnode->prev=NULL;
	newnode->val=x;
	//返回新结点
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.2、初始化链表

这里我们使用带哨兵位的链表，因为哨兵位不存储有效空间，所以我们就给个-1，将哨兵位的前驱和后继指向自己，即prev和next指针指向自己，最后返回这个头结点，如图所示：

LTNode* LTInit()
{
	//创建哨兵位
	LTNode* phead=CreateLNode(-1);
	//哨兵位后继指向自己
	phead->next=phead;
	//哨兵位前驱指向自己
	phead->prev=phead;
	//返回哨兵位结点
	return phead;
}
1
2
3
4
5
6
7
8
9
10
11

4.3、打印链表

与单链表的打印不同的是，双链表遍历结束的条件并不是 cur等于空，而是cur==phead，也就是等于头结点，因为尾结点的next指向的是头结点。

代码：

void LTPrint(LTNode* phead)
{
	//断言
	assert(phead);
	//为了美观而这样写的
	printf("哨兵位<=>");
	LTNode* cur=phead->next;
	while(cur!=phead)
	{
		printf("%d<=>",cur->val);
		//让cur往后走，遍历链表
		cur=cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.4、尾插结点

操作要点：
创建新结点，找到位结点tail，将尾结点的后继next指向新结点，新结点的前驱prev指向尾结点，再将新结点的后继next指向头结点，头结点的前驱prev指向新结点即可，也就是将几个结点链起来。

void LTPushBack(LTNode* phead,LTDateType x)
{
	assert(phead);
	//
	LTNode* newnodw=CreateLNode(x);
    LTNode* tail=phead->prev;
	newnode->prev=tail;
	tail->next=newnode;
	newnode->next=phead;
	phead->prev=newnode;
}
1
2
3
4
5
6
7
8
9
10
11

4.5、尾删结点

依旧是遍历找到尾结点定义为指针tail，再找到尾结点tail的前驱，并将其定义为指针tailprev，把tail指向的结点释放掉，然后只需修改它们之间的指向就行了，把tailprev的后继next指向phead，phead的前驱prev指向tailprev。若链表只有哨兵位phead将不能进行删除操作。

代码：

void LTPopBack(LTNode* phead)
{
	//断言
	assert(phead);
	LTNode*tail=phead->prev;
	LTNode*tailprev=tail->prev;
	free(tail);
	phead->prev=tailprev;
	tailprev->next=phead;
}
1
2
3
4
5
6
7
8
9
10

4.6、头插结点

创建新结点，将新结点插到头结点（哨兵位的）后面，而不是前面，搞清楚这里就可以改变几个结点指针的指向了，因为d1是phead的next，所以你可以把d1写成phead->next,改变newnode和d1的指向的时候就可以写成newnode->next=phead->next。

代码：

void LTPushFront(LTNode* phead,LTDateType x)
{
	//断言
	assert(phead);
	LTNode* newnode=CreateLNode(x);

	newnode->next=phead->next;
	phead->next->prev=newnode;
	newnode->prev=phead;
	phead->next=newnode;
}
1
2
3
4
5
6
7
8
9
10
11

4.7、头删结点

定义两个指针，将哨兵位结点的后面一个，也就是第一个结点定义为first，再将first->next定义为second，把first头结点free释放掉置空，最后改变结点的指向就好了，当你把图画好后的操作就相当简单了。如下图所示：

代码：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);
	LTNode* first=phead->next;
	LTNode* second=first->next;
	phead->next=second;
	second->prev=phead;
	free(first);
	first=NULL;
}
1
2
3
4
5
6
7
8
9
10
11

4.8、在pos结点前面插入

有了前面插入操作的基础，实现此接口的功能岂不是轻而易举？通过pos的位置可以直接找到它的前驱将其定义为posprev，然后再改变posprev、newnode和pos的指向，重新接上结点就行了。

代码：

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = CreateLTNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11

4.9、删除pos位置的结点

还是一样根据pos的位置找到它的前驱和后继，并将其定义为posPrev和posNext，将这两个结点链接起来，把pos指向的结点free释放掉即可。看图会更清晰：

代码：

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
1
2
3
4
5
6
7
8
9
10

4.10、查找链表中的某个元素

从哨兵位的后一个结点开始遍历链表，当cur等于phead停止循环，若找到该元素返回该元素，没找到返回NULL。

代码：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	//cur从phead的next开始走
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.11、链表的销毁

cur从phead的next开始遍历，依次free释放掉每一个结点。

void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

五、总结 全部代码

list.c

#include"List.h"



LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

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

	return newnode;
}

LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("哨兵位<=>");

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = CreateLTNode(x);

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

void LTPopBack(LTNode* phead)
{
	assert(phead);

	// 空
	assert(phead->next != phead);

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);

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

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


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

	LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

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

		cur = cur->next;
	}

	return NULL;
}

// 在pos前面的插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = CreateLTNode(x);

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

// 删除pos位置
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(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
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

List.h

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

typedef int LTDateType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDateType val;
}LTNode;

//初始化
LTNode* LTInit();

//打印
void LTPrint(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead,LTDateType x);

//尾删
void LTPopBack(LTNode* phead);

//头插
void LTPushFront(LTNode* phead,LTDateType x);

//头删
void LTPopFront(LTNode* phead);

//查看
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos前插入
void LTInsert(LTNode* pos,LTDateType x);

//删除pos位置的结点
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
37
38
39
40
41

走前给个三连呗~