C语言实现双向链表_c语言双向链表

1.版本一

由于节点之间的连接变多 所以我们最好提前将前驱节点和后继节点用变量保存下来 以免等下在进行节点之间的指向时出错

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 节点类
typedef struct Node {
	// 数据域
	int data;
	// 指针域
	struct Node* next;
	struct Node* pre;
}Node;// 别名
// 初始化链表
Node* initList() {
	Node* list = (Node*)malloc(sizeof(Node));
	list->data = 0;
	list->next = NULL;
	list->pre = NULL;
	return list;
}
// 头插法
void headInsert(int data, Node* list) {
	Node* node = (Node*)malloc(sizeof(Node));
	Node* pre = list;
	Node* next = list->next;
	node->data = data;
	pre->next = node;
	node->pre = pre;
	node->next = next;
	if (list->data != 0) {
		next->pre = node;
	}
	// 更新链表长度
	list->data++;
}
// 尾插法
void tailInsert(int data, Node* list) {
	// 为待插入节点分配内存
	Node* node = (Node*)malloc(sizeof(Node));
	// 获取待插入节点的前驱节点 前驱节点其实就是原来的尾节点
	Node* pre = list->next;
	while (pre->next) {
		pre = pre->next;
	}
	Node* next = pre->next;
	node->data = data;
	pre->next = node;
	node->pre = pre;
	node->next = next;
	// 更新链表长度
	list->data++;
}
// 删除方法
bool delete(int data, Node* list) {
	// 我们需要做的是删除指定节点值对应的第一个节点
	Node* cur = list->next;
	while (cur) {
		// 如果一旦遇到符合指定节点值的节点的话 那么就执行相关操作
		if (cur->data == data) {
			// 需要先考虑头删、尾删和中间删以及删除之后链表为空四种情况 总结之后 我们可以发现尾删和删除之后链表为空同属一种情况 都是只需要设置一条线即可 即前驱指向后继 但是其他情况需要设置两条线 即前驱指向后继 后继指向前驱
			cur->pre->next = cur->next;
			if (cur->next) {
				cur->next->pre = cur->pre;
			}
			free(cur);
			list->data--;
			return true;
		}
		cur = cur->next;
	}
	return false;
}
// 打印链表方法
void printList(Node* list) {
	Node* cur = list->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
int main() {
	Node* list = initList();
	headInsert(1, list);
	headInsert(2, list);
	headInsert(3, list);
	tailInsert(4, list);
	tailInsert(5, list);
	printList(list);// 3 2 1 4 5
	if (delete(5, list) == true) {
		printf("删除成功\n");
	}
	else {
		printf("删除失败\n");
	}
	printList(list);// 2 1 4 5
}
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

2.版本二(mj版本的双向链表 带有虚拟头节点)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ELEMENT_NOT_FOUND -1
// 我们的设计理念就是引入一个虚拟头节点 但是不引入头节点的标识以及尾节点的标识
// 节点类
typedef struct Node {
	int data;// 数据域
	struct Node* pre;
	struct Node* next;// 指针域
}Node;
// 初始化链表
Node* initList() {
	Node* list = (Node*)malloc(sizeof(Node));
	list->data = 0;
	list->pre = NULL;
	list->next = NULL;
	return list;
}
// 索引越界的处理
void outOfBounds(int index) {
	printf("索引为%d 索引越界了\n", index);
}
// 边界检查
void rangeCheck(int index, Node* list) {
	if (index < 0 || index >= list->data)
		outOfBounds(index);
}
// 针对添加方法的边界检查
void rangeCheckForAdd(int index, Node* list) {
	if (index < 0 || index > list->data)
		outOfBounds(index);
}
// 根据指定索引获取节点
Node* node(int index, Node* list) {
	// 对参数索引进行边界检查
	rangeCheck(index, list);
	Node* cur = list->next;
	for (int i = 0; i < index; ++i) {
		cur = cur->next;
	}
	return cur;
}
// 添加方法
void add(int index, int data, Node* list) {
	// 需要分成三种情况进行分析 一种情况是中间插入 需要设置四条线 一种情况是尾插 需要设置三条线 一种情况是头插 需要设置四条线 一种情况是对空链表进行插入操作 需要设置三条线 所以我们可以分成两种情况 一种是尾插的特殊情况 一中是其他位置插入
	// 对参数索引进行边界检查
	rangeCheckForAdd(index, list);
	// 为待插入节点分配内存
	Node* cur = (Node*)malloc(sizeof(Node));
	// 获取待插入节点的前驱节点 如果是头插的话 那么就需要特殊处理了
	Node* pre = index == 0 ? list : node(index - 1, list);
	// 获取待插入节点的后继节点
	Node* next = pre->next;
	cur->data = data;
	// 四种情况都要设置三条线 
	pre->next = cur;
	cur->pre = pre;
	cur->next = next;
	if (next)
		next->pre = cur;
	// 无论执行的是哪一种情况 都需要更新链表长度
	list->data++;
}
// 删除方法
int delete(int index, Node* list) {
	// 我们需要将问题分成三种情况去讨论 一种情况是中间删除 一种情况是尾删 一种情况是头删 如果是中间删除的话 那么我们需要操作的指针有两条 分别是前驱节点的后继节点还有后继节点的前驱节点 如果是尾删的话 那么就需要操作一条 即前驱节点指向后继节点 如果是头删的话 那么需要操作两条 同中间删除一样 如果是删除之后链表为空的话 那么就归结到尾删的情况中去考虑即可 并且复用尾删的代码
	Node* cur = node(index, list);
	// 我们保存一下待删除节点的节点值
	int delete = cur->data;
	// 通过待删除节点获取到他的前驱节点以及后继节点
	Node* pre = cur->pre;
	Node* next = cur->next;
	pre->next = next;
	if (next)
		next->pre = pre;
	// 我们还要去释放一下cur的内存 同时也解决了从cur指出的两条指针
	free(cur);
	// 更新一下链表的长度
	list->data--;
	// 返回待删除节点的节点值
	return delete;
}
// 定义一个方法 用于获取指定节点值对应的位置
int indexOf(int data, Node* list) {
	Node* cur = list->next;
	for (int i = 0; i < list->data; ++i) {
		if (cur->data == data)return i;
		cur = cur->next;
	}
	// 如果上述循环没有返回值的话 那么说明没有找到指定的节点值对应的节点
	return ELEMENT_NOT_FOUND;
}
// 获取指定索引处的节点值
int get(int index, Node* list) {
	return node(index, list)->data;
}
// 重置指定位置处的节点值
int set(int index, int newData, Node* list) {
	int data = node(index, list)->data;
	node(index, list)->data = newData;
	return data;
}
// 清空方法
void clear(Node* list) {
	Node* cur = list->next;
	Node* next;
	for (int i = 0; i < list->data; ++i) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	// 清空链表之后链表长度为0
	list->data = 0;
}
// 判断链表是否包含指定节点值
bool contains(int data, Node* list) {
	return indexOf(data, list) != ELEMENT_NOT_FOUND;
}
// 判断链表是否为空
bool isEmpty(Node* list) {
	return list->data == 0;
}
// 获取链表长度
int size(Node* list) {
	return list->data;
}
// 打印链表的方法
void printList(Node* list) {
	Node* cur = list->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 定义一个主函数
int main() {
	// 创建一个链表
	Node* list = initList();
	// 头部添加 尾部添加
	add(0, 1, list);// 1
	add(0, 2, list);// 2 1
	add(0, 3, list);// 3 2 1
	add(0, 4, list);// 4 3 2 1
	add(size(list), 5, list);// 4 3 2 1 5
	// 打印链表
	printList(list);// 4 3 2 1 5
	// 头部删除 尾部删除
	delete(0, list);// 3 2 1 5
	delete(size(list) - 1, list);// 3 2 1
	// 打印链表
	printList(list);// 3 2 1
	// 获取头部元素
	printf("%d\n", get(0, list));// 3
	// 重置头部元素
	printf("%d\n", set(0, 4, list));// 3
	// 打印链表
	printList(list);// 4 2 1
	printf("%d\n", contains(4, list));// true
	printf("%d\n", isEmpty(list));// false
	// 清空链表
	clear(list);
	printf("%d\n", size(list));// 0
	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
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
159
160
161
162
163
164
165
166

测试结果显示 这个代码符合预期