C语言简单的数据结构：双向链表的实现

1.双向链表的结构和初始化

1.1双向链表的结构

之前我们的单向链表指的是：不带头单向不循环链表
而双向链表指的是：带头双向循环链表

其中头节点为哨兵位（不存储任何数据），尾部要指向哨兵位
它的节点有：数据，指向下一个节点的指针和指向下一个节点的指针

这就是双向链表的节点定义，写入VS：

1.2双向链表的初始化

当双向链表为NULL时，还有一个头节点，说一初始化时就是创建一个哨兵位

首先是申请链表：


接着是哨兵位的创建（放入一个无效数据就行）

测试：

2.双向链表的相关操作

2.1双向链表的尾插、打印和头插

2.11双向链表的尾插

这里的传参是什么呢？

58c66ffd3020b137a.png)
47be39ed4525a16999a787187d86.png)
对于这个问题其实很简单，对于完成操作来说这两种都可以，但是我们使用第一种是没办法改变哨兵位的，但是我们第二种有机会改变哨兵位的，如果让我们代码更安全一点，就使用第一个

这里的d3就是phead指向的prev指针

我们优先修改newnode指向，然后在修改phead的指向
我们再来判断NULL链表的情况：
当插入NULL指针时，并不会对NULL指针进行解引用，这个代码就没问题

这两行代码不能直接进行交换，因为会找不到d3这个数据，从而改变不了

2.12双向链表的打印

这里要用到哨兵为来确定是否循环一遍
测试：

2.13双向链表的头插

顺序为3 1 4 2
测试：

2.2双向链表的尾删和头删

2.21双向链表的尾删

首先要判断链表必须有效并且链表不能为NULL


我们只对2 3进行改变就行了

测试：

2.22双向链表的头删

测试：

2.3双向链表查找和任意位置插入、删除

2.31双向链表查找

进行遍历，然后进行判断
测试：

2.32双向链表任意位置之后插入

还是对newnode进行改变然后在该pos指针
测试：

2.33双向链表任意位置删除

删除位置理论上不能为phead，但是没有phead参数，无法增加校验

也是先将pos后的指针先修改好，然后在修改pos前的指针
测试：

这里虽然对实参进行改变了，但这里为什么不传二级指针呢
这里是为了保持接口一致性，方便我们的记忆，我们可以通过外部值NULL来解决

这里我们之前的初始化代码也可以进行优化



一个以参数的方式初始化，一个以返回值的方法初始化

2.4双向链表的销毁

销毁后要向下走，所以我们要将指针存一下

这里也是一级指针，所以无法改变头节点

手动置为NULL即可

本文代码：

List.h

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

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

LTNode* LTBuyNode(LTDataType x);//申请空间
//void LTInit(LTNode** pphead);//初始化
LTNode* LTInit();

void LTPrint(LTNode* phead);
//插入数据
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

void LTPopBack(LTNode* phead);
void LTPopFront(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

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

LTNode* LTBuyNode(LTDataType x)
{
	//申请节点
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;
	return node;
}

//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}


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

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

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

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

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

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

void LTPopBack(LTNode* phead)
{
	//链表必须有效并且链表不能为NULL
	assert(phead && phead->next != phead);

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

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

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

	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

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

void LTErase(LTNode* pos)
{
	assert(pos);
	//pos理论上不能为phead，但是没有phead参数，无法增加校验

	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = 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

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

void ListTest01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	//LTPushBack(plist, 1);
	//LTPrint(plist);
	//LTPushBack(plist, 2);
	//LTPrint(plist);
	//LTPushBack(plist, 3);
	//LTPrint(plist);
	//LTPushBack(plist, 4);
	//LTPrint(plist);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPushFront(plist, 3);
	LTPrint(plist);
	LTPushFront(plist, 2);
	LTPrint(plist);
	LTPushFront(plist, 1);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

void ListTest02()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

void ListTest03()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* find1 = LTFind(plist, 3);
	if (find1 == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了\n");
	}
	LTNode* find2 = LTFind(plist, 5);
	if (find2 == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了\n");
	}
	LTDestroy(plist);
	plist = NULL;
}

void ListTest04()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* find1 = LTFind(plist, 2);
	LTInsert(find1, 66);
	LTPrint(plist);
	LTNode* find2 = LTFind(plist, 4);
	LTInsert(find2, 99);
	LTPrint(plist);
	LTNode* find3 = LTFind(plist, 66);
	LTErase(find3);
	find3 = NULL;
	LTPrint(plist);
	LTNode* find4 = LTFind(plist, 99);
	LTErase(find4);
	find4 = NULL;
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	//ListTest01();
	//ListTest02();
	//ListTest03();
	ListTest04();
	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
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

以上就是本文的全部内容了，希望对大家有所帮助，大家加油！！！