【数据结构】单链表（不带头结点）基本操作的实现（C语言）

---

🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🐌 个人主页：蜗牛牛啊
🔥 系列专栏：🛹数据结构、🛴C++
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹

---

通过对顺序表的学习，我们可以发现顺序表有以下几点缺陷：
1.空间不够时需要扩容，扩容尤其是用realloc进行异地扩容时，是有一定代价的，其次还可能存在一定空间浪费。
2.头部或者中间插入删除，需要挪动数据，效率低下。
那我们可以对其所具有的缺陷进行优化：可以按需申请空间同时插入删除时不挪动数据。而单链表就符合这些优化所具有特点。但是我们要注意的是单链表具有这些优点并不代表链表就可以完全替代顺序表。

一、单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续，物理结构中指针域存储的是下一个结点的地址；而且链式结构的结点一般都是从堆上申请出来的；从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。链表存储数据的区域可分为数据域和指针域：

用代码表示链表中的数据域和指针域如下：

typedef int STLDataType;//typedef定义数据类型
typedef struct SListNode
{
	SLTDataType data;//结点的数据
    //STLNode* next;//不能这样定义，typedef定义在这里还没起作用，这里不能用
	struct SListNode* next;//next指针指向下一个结点
}STLNode;
1
2
3
4
5
6
7

思考：为什么在申请的时候需要申请堆上的空间？因为堆上申请的空间存储数据的时候不会因为函数销毁而销毁，堆上的空间需要的时候就申请，不需要的时候就释放；函数栈帧上开辟的空间存储的数据会因为函数栈帧的销毁而释放，后面在进行尾插和头插时候新的结点不能链接到表上。

二、单链表的基本操作

我们在创建链表结点的时候不能使用下面这种方式：

void TestSList
{
    SLTNode node;
}
1
2
3
4

因为node是在TestSList函数内创建的，属于局部变量，局部变量作用域仅限于函数内，出函数作用域就失效了，函数结束的时候会被销毁。

如当我们往链表中插入结点时使用SLTNode node往链表中插入结点，结点存在栈帧中，函数结束局部变量就销毁了。

1.创建单个结点

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//申请空间
	if (newnode == NULL)//判断是否为空
	{
		perror("BuySLTNode malloc");
		exit(-1);
	}
	newnode->val = x;//赋值
	newnode->next = NULL;//next指针指向空
	return newnode;//返回创建的结点
}
1
2
3
4
5
6
7
8
9
10
11
12

2.创建具有n个结点的链表

SLTNode* CreateSList(int n) 
{
	int i = 0;
	SLTNode* ptail = NULL,*phead = NULL;
	for (i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i); //创建新节点
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode; //链接
			ptail = newnode;
		}
	}
	return phead; //返回头节点
}
//没有返回值，形参使用的是二级指针改变头指针指向的地址。
//void CreateSList(SLTNode** pphead, int n)
//{
//	int i = 0;
//	SLTNode* ptail = NULL;
//	for (i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (*pphead == NULL)
//		{
//			ptail = *pphead = newnode;
//		}
//		else
//		{
//			ptail->next= newnode;
//			ptail = newnode;
//		}
//	}
//}
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

上述代码中提供了两种实现方式，没有注释的是返回头指针的，注释内容是没有返回值，形参使用的是二级指针改变头指针指向的地址。

3.打印单链表

void SLTPrint(SLTNode* phead)
{
	SLTNode* tail = phead;
    //遍历链表
	while (tail)
	{
		printf("%d ", tail->val);
		tail = tail->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

4.尾插

//必须传二级指针，这样当头节点为空时能够改变头节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* tail = *pphead; 
	SLTNode* newnode = BuySLTNode(x); //申请新结点
	if (*pphead == NULL) //如果链表为空
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

尾插时，要注意当单链表的头结点为空的时候，要先将新结点作为头结点。因为当头结点为空时，需要改变头指针，所以传过来的为二级指针（也可以使用一级指针，不过此时要有返回值），要想改变SLTNode*的值，就要传递它的地址即SLTNode**类型，如果只传SLTNode*指针无法改变头节点，因为形参的改变不会影响到实参。

5.尾删

//传二级指针，如果只剩头节点时能够有效删除头节点
void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(*pphead);//判断链表不为空
	if ((*pphead)->next==NULL)
	{
		free(*pphead);//释放空间
		*pphead = NULL;//置空
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
        //遍历找到最后一个结点
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);//将最后一个结点的空间释放
		prev->next = NULL;//置空
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

尾删时也要注意区分是否为头结点；同时注意删除后，要将其置空prev->next = NULL。

6.头插

//头插时也要注意是不是头节点为空，传二级指针
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySLTNode(x);//申请新节点
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7

7.头删

void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);//断言
	SLTNode* nextnode = (*pphead)->next;//记录头节点的下一个结点
	free(*pphead);//释放空间
	*pphead = nextnode;//头节点为下一个结点
}
1
2
3
4
5
6
7

头插和头删是单链表的优势，尾插和尾删是顺序表的优势。同时在尾删时注意将*pphead加上括号用来区分优先级，否则会报错。

8.查找某个结点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
	SLTNode* tail = phead;
    //遍历
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意循环条件，当循环条件写为while(tail->next)时，会有空指针的风险，同时还会漏掉最后一个结点。

9.在某个结点后面插入

void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
	assert(pos);//断言
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
    //插入新节点
	pos->next = newnode;
	newnode->next = tail;
}
1
2
3
4
5
6
7
8
9

10.在某个结点前面插入

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
    //如果pos是头节点，调用头插函数
	if (pos == *pphead)
	{
		/*newnode->next = *pphead;
		*pphead = newnode;*/
		SLTPushBack(pphead, x);
	}
	else
	{
        //遍历然后插入结点
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
        //插入结点
		tail->next = newnode;
		newnode->next = 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

11.删除某个位置后面的结点

void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
	assert(pos);
    //结点后面为空结点，直接返回
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
        //删除
		SLTNode* tail = pos->next;
		pos->next = tail->next;
		free(tail);//释放空间
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

12.删除某个结点

void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
	assert(pos);
	SLTNode* tail = *pphead;
	if (pos == *pphead)
	{
		SLTNode* nextNode = (*pphead)->next;
		free(*pphead);
		*pphead = nextNode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

13.销毁单链表

void SLTDestroy(SLTNode** pphead)//销毁
{
	assert(*pphead);
	SLTNode* tail = *pphead;
	
    //遍历，一个一个销毁
	while (tail)
	{
		SLTNode* next = tail->next;
		free(tail);
		tail = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意最后要将头结点置空。

三、测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
typedef int SLTDataType;
typedef struct SList {
	struct Slist* next;
	SLTDataType val;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuySLTNode malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
SLTNode* CreateSList(int n)
{
	int i = 0;
	SLTNode* ptail = NULL, * phead = NULL;
	for (i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//	int i = 0;
//	SLTNode* ptail = NULL;
//	for (i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (*pphead == NULL)
//		{
//			ptail = *pphead = newnode;
//		}
//		else
//		{
//			ptail->next= newnode;
//			ptail = newnode;
//		}
//	}
//}
void SLTPrint(SLTNode* phead)
{
	SLTNode* tail = phead;
	while (tail)
	{
		printf("%d ", tail->val);
		tail = tail->next;
	}
	printf("\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* tail = *pphead;
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);
	SLTNode* nextnode = (*pphead)->next;
	free(*pphead);
	*pphead = nextnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
	SLTNode* tail = phead;
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
	pos->next = newnode;
	newnode->next = tail;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	if (pos == *pphead)
	{
		/*newnode->next = *pphead;
		*pphead = newnode;*/
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = pos;
	}
}
void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* tail = pos->next;
		pos->next = tail->next;
		free(tail);
	}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
	assert(pos);
	SLTNode* tail = *pphead;
	if (pos == *pphead)
	{
		SLTNode* nextNode = (*pphead)->next;
		free(*pphead);
		*pphead = nextNode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}
void SLTDestroy(SLTNode** pphead)//销毁
{
	assert(*pphead);
	SLTNode* tail = *pphead;

	while (tail)
	{
		SLTNode* next = tail->next;
		free(tail);
		tail = next;
	}
	*pphead = NULL;
}
void TestSL()
{
	SLTNode* plist = CreateSList(2);
	/*SLTNode* plist = NULL;
	CreateSList(&plist,10);//没有返回值
	SLTPrint(plist);*/
	SLTPushBack(&plist, 600);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPushFront(&plist, 300);
	SLTPushFront(&plist, 400);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 600);
	if (pos)
	{
		SLInsertAfter(pos, 700);
		SLTInsert(&plist, pos, 500);
		SLTEraseAfter(pos);
		//SLTErase(&plist, pos);

	}
	SLTPrint(plist);
	SLTDestroy(&plist);
	SLTPrint(plist);
}
int main()
{
	TestSL();
	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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252