数据结构---双链表

专栏：数据结构
个人主页：HaiFan.
专栏简介：从零开始，数据结构！！

前言

双向链表是在结构体内存两个指针，一个指针存下一个结点的地址，另一个指针是存上一个结点的地址，这样，就可以通过一个结点，找到前后两个结点。听起来很复杂，但实现起来，要比单链表简单许多。

双链表：

typedef int LDataType;

typedef struct ListNode
{
	LDataType val;
	struct ListNode* head;
	struct ListNode* tail;
}LN;
1
2
3
4
5
6
7
8

双链表各接口的实现

LN* BuyLN(LDataType x);//为要插入的值开辟一块空间

void LNInit(LN** pphead);//初始化
void LNDestory(LN* phead);//销毁

void LNPrint(LN* phead);//打印链表中的值

void LNPushBack(LN* phead, LDataType x);//尾插
void LNPopBack(LN* phead);//尾删

void LNPushFront(LN* phead, LDataType x);//头插
void LNPopFront(LN* phead);//头删

bool LNEmpty(LN* phead);//双链表是否为空

LN* LNFind(LN* phead, LDataType x);//查找

void LNInsert(LN* pos, LDataType x);//任意位置插入
void LNErase(LN* pos);//任意位置删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

为要插入的值开辟一块空间BuyLN

这个BuyLN是为链表开辟一块空间，为什么要额外写一个这函数，因为在插入值的过程中，需要为这个值开辟一块空间，每次都需要写相同的代码，所以把这个代码写成一个函数，用到式直接调用函数即可

LN* BuyLN(LDataType x)
{
	LN* sn = (LN*)malloc(sizeof(LN));
	if (sn == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	sn->val = x;
	sn->head = NULL;
	sn->tail = NULL;

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

初始化LNInit和销毁LNDestory

双链表的初始化，只需要把链表中的head和tail指针都指向自己，形成一个环即可。

void LNInit(LN** pphead)
{
	(*pphead) = BuyLN(-1);
	(*pphead)->head = *pphead;
	(*pphead)->tail = *pphead;
}
1
2
3
4
5
6

---

空间有开辟就有销毁，销毁之后把空间还给系统

void LNDestory(LN* phead)//ٿռ
{
	assert(phead);

	LN* cur = phead->head;

	while (cur != phead)
	{
		LN* sn = cur;
		free(sn);
		sn = NULL;
		cur = cur->head;

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

打印链表中的值LNPrint

头结点是不需要打印的，所以可以先定义一个sn代表头结点指向的下一个元素的位置，然后依次打印，直到sn的地址和头节点的地址相同时，打印结束

void LNPrint(LN* phead)
{
	assert(phead);
	LN* sn = phead->head;
	while (sn != phead)
	{
		cout << sn->val << ' ';
		sn = sn->head;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

尾插LNPushBack和尾删LNPopBack

单链表的尾插需要先遍历，找到尾，然后进行插入操作，双链表不同于单链表，双链表有两个指针，一个存下一个结点，一个存上一个结点，我们只需要在头节点的左面，也就是让头节点中存上一个结点存要插入的值即可，这样就能完成尾插。

这样就不需要在遍历链表，找尾了。

void LNPushBack(LN* phead, LDataType x)
{
	LN* newnode = BuyLN(x);
	LN* prev = phead->tail;

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

---

尾删依旧是把头节点左边的那一个元素给删除即可，当然，表中如果只有头节点，就不要在删除了。。。

void LNPopBack(LN* phead)
{
	assert(phead->head != phead->tail);
	LN* prev = phead->tail;

	prev->tail->head = phead;
	phead->tail = prev->tail;
	free(prev);
	prev = NULL;
}
1
2
3
4
5
6
7
8
9
10

头插LNPushFron和头删LNPopFront

头插的话，要先找到首元素，然后把要插入的元素和头节点，首元素都双向链接起来即可。

void LNPushFront(LN* phead, LDataType x)
{
	LN* newnode = BuyLN(x);
	LN* ne = phead->head;

	ne->tail = newnode;
	newnode->head = ne;
	phead->head = newnode;
	newnode->tail = phead;
}
1
2
3
4
5
6
7
8
9
10

---

头删的话呢，跟上面一样，要先找到首元素，然后让头节点和首元素指向的下一个元素链接起来即可。

void LNPopFront(LN* phead)
{
	assert(phead->head != phead->tail);

	LN* ne = phead->head;
	phead->head = ne->head;
	ne->head->tail = phead;
	free(ne);
	ne = NULL;

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

判断链表是否为空LNEmpty

如果链表为空返回true，反之，返回false，当双链表的头指针和尾指针都指向自己的时候，就说明，双链表为空。

bool LNEmpty(LN* phead)
{

	assert(phead);
	return phead->head == phead->tail;
}
1
2
3
4
5
6

查找LNFind

查找一个元素，返回这个元素的地址，只需要遍历双链表即可。

LN* LNFind(LN* phead, LDataType x)
{
	assert(phead);
	assert(phead->head != phead->tail);

	LN* cur = phead->head;

	while (cur != phead)
	{
		if (x == cur->val)
		{
			return cur;
		}
		cur = cur->head;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

任意位置插入 LNInsert

再插入之前，要先找到要插入的位置，寻找这个位置的任务就交给了上面写的查找函数，我们只需要传递参数，对该位置进行插入即可，

void LNInsert(LN* pos, LDataType x)
{

	assert(pos);
	LN* newnode = BuyLN(x);
	LN* prev = pos->head;

	pos->head = newnode;
	newnode->tail = pos;
	newnode->head = prev;
	prev->tail = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

任意位置删除LNErase

和上面一样，要删除哪个元素，就要先找到那个元素，然后进行删除操作，找到那个元素的任务依旧交给LNFind函数

void LNErase(LN* pos)
{
	assert(pos);
	LN* ne = pos->head;

	pos->head = ne->head;
	ne->tail = pos;
}
1
2
3
4
5
6
7
8

测试结果

测试代码：

#include "List.h"

void TestLN()
{
	LN* plist = NULL;
	LNInit(&plist);
	LNPrint(plist);

	LNPushBack(plist, 1);
	LNPushBack(plist, 2);
	LNPushBack(plist, 3);
	LNPushBack(plist, 4);
	LNPushBack(plist, 5);
	LNPrint(plist);


	LNPopBack(plist);


	LNPrint(plist);

	LNPushFront(plist, -1);
	LNPushFront(plist, -2);
	LNPushFront(plist, -3);
	LNPushFront(plist, -4);
	LNPushFront(plist, -5);


	LNPrint(plist);
	LNPopFront(plist);

	LNPrint(plist);

	LN* ret = LNFind(plist, 3);
	if (ret != NULL)
	{
		cout << ret->val << ' ' << ret << endl;
		LNInsert(ret, 10000);
		LNErase(ret);
	}
	LNPrint(plist);


	LNDestory(plist);
}

int main()
{
	TestLN();

	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

源代码

.h文件

#pragma once


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

using namespace std;

typedef int LDataType;

typedef struct ListNode
{
	LDataType val;
	struct ListNode* head;
	struct ListNode* tail;
}LN;

LN* BuyLN(LDataType x);//为要插入的值开辟一块空间

void LNInit(LN** pphead);//初始化
void LNDestory(LN* phead);//销毁

void LNPrint(LN* phead);//打印链表中的值

void LNPushBack(LN* phead, LDataType x);//尾插
void LNPopBack(LN* phead);//尾删

void LNPushFront(LN* phead, LDataType x);//头插
void LNPopFront(LN* phead);//头删

bool LNEmpty(LN* phead);//双链表是否为空

LN* LNFind(LN* phead, LDataType x);//查找

void LNInsert(LN* pos, LDataType x);//任意位置插入
void LNErase(LN* pos);//任意位置删除

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

.cpp文件

#include "List.h"

LN* BuyLN(LDataType x)
{
	LN* sn = (LN*)malloc(sizeof(LN));
	if (sn == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	sn->val = x;
	sn->head = NULL;
	sn->tail = NULL;

	return sn;
}

void LNPrint(LN* phead)
{
	assert(phead);
	LN* sn = phead->head;
	while (sn != phead)
	{
		cout << sn->val << ' ';
		sn = sn->head;
	}
	cout << endl;
}

void LNInit(LN** pphead)//ʼ
{
	(*pphead) = BuyLN(-1);
	(*pphead)->head = *pphead;
	(*pphead)->tail = *pphead;
}



void LNDestory(LN* phead)//ٿռ
{
	assert(phead);

	LN* cur = phead->head;


	while (cur != phead)
	{
		LN* sn = cur;
		free(sn);
		sn = NULL;
		cur = cur->head;

	}
}

void LNPushBack(LN* phead, LDataType x)
{
	LN* newnode = BuyLN(x);
	LN* prev = phead->tail;

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

void LNPopBack(LN* phead)
{
	assert(phead->head != phead->tail);
	LN* prev = phead->tail;

	prev->tail->head = phead;
	phead->tail = prev->tail;
	free(prev);
	prev = NULL;
}



void LNPushFront(LN* phead, LDataType x)
{
	LN* newnode = BuyLN(x);
	LN* ne = phead->head;

	ne->tail = newnode;
	newnode->head = ne;
	phead->head = newnode;
	newnode->tail = phead;
}

void LNPopFront(LN* phead)
{
	assert(phead->head != phead->tail);

	LN* ne = phead->head;
	phead->head = ne->head;
	ne->head->tail = phead;
	free(ne);
	ne = NULL;

}

bool LNEmpty(LN* phead)
{

	assert(phead);
	return phead->head == phead->tail;
}

LN* LNFind(LN* phead, LDataType x)
{
	assert(phead);
	assert(phead->head != phead->tail);

	LN* cur = phead->head;

	while (cur != phead)
	{
		if (x == cur->val)
		{
			return cur;
		}
		cur = cur->head;
	}
	return NULL;
}

void LNInsert(LN* pos, LDataType x)
{

	assert(pos);
	LN* newnode = BuyLN(x);
	LN* prev = pos->head;

	pos->head = newnode;
	newnode->tail = pos;
	newnode->head = prev;
	prev->tail = newnode;
}

void LNErase(LN* pos)
{
	assert(pos);
	LN* ne = pos->head;

	pos->head = ne->head;
	ne->tail = pos;
}

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

test.cpp文件

#define _CRT_SECURE_NO_WARNINGS 1


#include "List.h"

void TestLN()
{
	LN* plist = NULL;
	LNInit(&plist);
	LNPrint(plist);

	LNPushBack(plist, 1);
	LNPushBack(plist, 2);
	LNPushBack(plist, 3);
	LNPushBack(plist, 4);
	LNPushBack(plist, 5);
	LNPrint(plist);


	LNPopBack(plist);


	LNPrint(plist);

	LNPushFront(plist, -1);
	LNPushFront(plist, -2);
	LNPushFront(plist, -3);
	LNPushFront(plist, -4);
	LNPushFront(plist, -5);


	LNPrint(plist);
	LNPopFront(plist);

	LNPrint(plist);

	LN* ret = LNFind(plist, 3);
	if (ret != NULL)
	{
		cout << ret->val << ' ' << ret << endl;
		LNInsert(ret, 10000);
		LNErase(ret);
	}
	LNPrint(plist);


	LNDestory(plist);
}

int main()
{
	TestLN();

	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