【数据结构】双链表_数据结构 双链表

一. 前言

 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

---

二. 带头双向链表接口实现

1.准备工作

 由于实际开发项目中，项目的实现都是采用模块化的方式实现。所以博主在这也采用了模块化的方式。

#pragma once

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;//下一个节点指针
	struct ListNode* prev;//上一个节点指针
	LTDataType data;//数据域
}LTNode;
1
2
3
4
5
6
7
8
9

为了后续函数功能实现过程中数据类型书写方便性，我们将struct ListNode重命名为LTNode。
同时后续好修改数据域类型，我们将数据域类型int重命名为LTDataType.

---

2. 创建一个节点

不管是后续插入数据还是初始化，我们都先要创建一个节点来存储数据。
所以我们在这设计了一个相关函数，从而避免大量重复的工作。

代码实现：

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

	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

三. 初始化

初始化时，我们支持需要创建一个节点作为哨兵位，并将两个指针同时指向自己即可。

代码实现：

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
1
2
3
4
5
6
7

---

4. 打印

打印比较简单。但需要注意我们是从哨兵位的下一个节点开始打印。

代码实现：

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//哨兵位下一个节点
	printf("phead<=>");
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

---

5. 尾插

带头双链表的尾插比较简单。
我们通过哨兵位向前访问即可得到尾节点。在插入数据即可。

代码实现：

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

	LTNode* tail = phead->prev;//尾节点
	LTNode* newnode = BuyLTNode(x);//要插入节点
	//插入
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

6. 尾删

【代码思路】：尾删首先要判断是否还有节点可删。若有，找到尾节点以及尾节点的前一个结点。在释放尾节点，并将新的尾节点和哨兵位链接起来即可。

代码实现：

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);//还有节点可删

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);

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

---

7. 头插

要实现头插，首先要强调是插到哨兵位的后面。
【代码思路】：直接将哨兵位，哨兵位的下一个节点以及新节点链接起来即可。

代码实现：

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

	LTNode* tail = phead->next;
	LTNode* newnode = BuyLTNode(x);

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

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

---

8. 头删

【代码思路】：头删和尾删一样，需要是否还有节点可删。若还有元素可删，需要保存哨兵位后面两个节点first、second。再释放掉first后，将哨兵位和second链接起来。

代码实现：

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

	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);

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

---

9. 计算节点个数

【代码思路】：首先保存哨兵位的下一个节点。然后开始向后遍历访问，每次个数加1，直到某节点的下一个节点指向哨兵位为止。

代码实现：

int LTSize(LTNode* phead)
{
	LTNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11

Tips:

• 可能有部分学者已经注意到或在一些书籍上看到过以下思路：哨兵位的数据域是随机值，是否可以将它用于记录节点个数。每次进行增删查改等操作时，对其进行加1/减1。不仅更加方便得知节点个数，同时还避免该接口的实现。
• 在这里博主不在这建议这样做，又或者说大部分情况是不能这样做的。原因在于：我们在本篇博客中，数据域为整型，可以用于记录节点个数大下。但在实际开发过程中，数据域可能存储的是浮点数或结构体什么的，那上述思路将导致结果错误。

---

10. 查找数据

【代码思路】：查找数据，从哨兵位的下一个节点开始，遍历查找。找到返回数据地址，否则返回空指针。

代码实现：

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

---

11. 在任意位置插入数据

【代码思路】：首先需要强调的是，不管是链表还是顺序表，插入数据默认都是前插，在这里也一样。插入数据、插入位置节点、以及前一个结点链接起来即可。
我们直接将

代码实现：

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

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

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

---

12. 在任意位置删除数据

【代码思路】：将该位置前一个和后一个节点链接起来后，再将该位置节点释放。

代码实现：

void LTErase(LTNode* pos)
{
	assert(pos);

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

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

13. 销毁

由于上述节点都是动态开辟的，使用往后需要销毁，释放内存。

代码实现：

void LTDestory(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

---

四. 如何10分钟内完成一个完整双链表

在实际开发过程中，我们一般实现实现任意位置插入删除接口的。然后在头插/删和尾插/删等接口中，调用上述两个接口，从而快速达到目的。

List.h:

#pragma once

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

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);//打印

//在pos之前插入x
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置节点
void LTErase(LTNode* pos);

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 LTDestory(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

List.c:

#include "List.h"


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

	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	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("phead<=>");
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


void LTInsert(LTNode* pos, LTDataType x)//任意位置插入
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

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

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

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

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

	posPrev->next = posNext;
	posNext->prev = posPrev;
}


void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);
	LTInsert(phead, x);
}


void LTPopBack(LTNode* phead)//尾删
{
	assert(phead);
	assert(phead != phead->next);
	LTErase(phead->prev);
}


void LTPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);
	LTInsert(phead->next, x);
}


void LTPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(phead != phead->next);
	LTErase(phead->next);
}


int LTSize(LTNode* phead)//节点大小
{
	LTNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}


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


void LTDestory(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