【初阶数据结构】——单链表详解（C描述）_写出单链表数据元素类型为整数类型存储结构的c语言描述

前言

上一篇文章，我们学习了顺序表，在文章的最后，我们提出了一些顺序表存在的问题和缺陷。

我们再来回顾一下，对于顺序表来说：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. realloc扩容（特别是异地扩，需要申请新空间，拷贝数据，释放旧空间）会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

那么如何解决上述问题呢？

针对这些问题，又引出了另一种线性表——链表。

我们一起来看看：

1. 链表的概念及结构

概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分（单链表）：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。

由于不必须按顺序结构存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是按值查找一个节点或者访问特定编号/位置的节点则需要O(n)的时间，而线性表的顺序表相应的时间复杂度分别是O(n)和O(1)。
链表也是线性表的一种。

2. 链表的分类

实际中链表的结构非常多样。
我们先一起看看，先了解一下：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
   另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

这篇文章我们重点给大家介绍的就是无头（不带头结点）单向非循环链表。
下面我们一起来学习：

3. 无头单向非循环链表的实现

就是这个：

它由多个结点组成，每个结点包含两部分，一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

这样，通过前一个结点的指针域中存储的地址，就可以找到下一个结点，我们也常说它指向下一个结点。

因此就得到了向上面那样的图。
但是，这样的图，我们把它称为逻辑图，一个结点有一个箭头指向下一个结点，依次链接。

但是在内存中，这样的箭头真实存在吗？

显然是不存在的，这只是我们想象出来的，为了方便我们理解的。

对于单链表，它真实的物理结构应该是这样的：

这里的箭头帮助大家理解，真实是不存在的。

这里我们讲的是不带头结点（在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点。头结点的数据域可以不存储任何信息）的单链表，因为大部分OJ题中都是不带头的。
图中的Plist叫做头指针，它直接指向了第一个有效的结点。
最后一个结点的指针域存放空指针NULL。

下面我们就用C语言实现一下单链表：

3.1 结构

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
1
2
3
4
5
6

因为单链表是由一系列结点构成的，所以我们只需要给出结点的结构，创建一个个的结点，然后把它们链接起来就构成了链表。
因为每个结点包含两部分，所以我们放在了一个结构体中。

3.2 创建结点

SLTNode* CreateNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

我们单链表创建的结点是使用malloc在堆上动态申请的空间，大家有没有想过：
为什么要这样做，为什么不直接定义一个结构体变量作为结点呢，为什么要在堆上申请空间呢？

既然选择这么做，就有它的道理：

大家想一下，实现对单链表的各种增删查改功能时，我们一般都是封装一个函数，比如现在我们要写一个头插，如果我们在头插的函数里面定义一个结点，那么这个结构体是不是一个局部的变量啊，我们知道局部变量是在栈上的，出了它的作用域就销毁了，当函数调用结束，结点也随之被销毁。
这样肯定是不行的，那什么地方的空间是我们需要了就申请，不需要的时候我们也可以自己释放呢？
当然有，就是堆上的空间。
所以，结点的创建我们使用malloc动态申请空间，而对于malloc申请的空间，是在堆上的，在程序结束之前，我们只要不释放，他就会一直存在。

对于动态内存管理知识不太熟悉或遗忘的老铁可以去复习一下，我之前有篇文章是专门讲解动态内存管理的。

3.3 单链表的销毁

//销毁
void SLTDestory(SLTNode** pphead)//pphead接收头指针的地址
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单链表的销毁需要将头指针置空，可能会改变头指针，所以应该传二级指针，SLTNode** pphead接收头指针的地址。
后面需要改变头指针的我们这里都选择传二级（传头指针地址），当然也可以用其他的方法。
不需要改变头指针的传头指针即可。

因为单链表使用的空间是我们使用malloc动态开辟的，所以是需要我们手动去释放的。
但是要注意，对于单链表空间的释放，我们不能做到像顺序表那样一次性就释放掉，因为顺序表的空间是一块连续的空间，但是，链表是一个一个结点构成的，一个结点malloc一次，它们不一定是连续的空间，所以我们要一个结点一个结点的释放。

3.4 打印单链表

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

我们对单链表进行遍历打印每个结点的数据就行了。
打印单链表不需要改变头指针，不需要传二级，SLTNode* phead接收头指针即可。

3.5 尾插

尾插要进行一个判断，因为我们实现的是没有头结点的，如果是对空表尾插，直接将要插入的结点赋值给头指针即可。
不是空表的尾插，要先遍历找尾，然后让尾结点的指针域存新结点的地址，使其成为新的尾。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = CreateNode(x);
	//空表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//找尾
	else
	{
		SLTNode* tail = *pphead;
		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
19
20
21

3.6 尾删

尾删也要进行判断分情况实现：
首先如果是空表就不是删了，进行断言assert(*pphead);。
如果只有一个结点要单独处理，直接释放头指针。
一个结点以上的情况，先找尾，再删。

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.6 头插

单链表实现头插头删是非常简单的：

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}
1
2
3
4
5
6
7
8
9

3.7 头删

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* tmpnext = (*pphead)->next;
	free(*pphead);
	*pphead = tmpnext;
}
1
2
3
4
5
6
7
8
9

3.8 查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

3.9 在pos位置之后插入x

这里传的pos不是像顺序表那样的下标，而是结点的地址，可以借助find的返回值获取。

//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8
9

3.10 在pos位置之前插入x

//在pos位置之前插入x
void SLTInsertPrev(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
		SLTPushFront(pphead, x);
	else
	{
		SLTNode* newnode = CreateNode(x);
		SLTNode* cur = *pphead;
		while(cur->next != pos)
		{
			cur = cur->next;
		}
		newnode->next = pos;
		cur->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这里进行了一个判断，如果 pos == *pphead，说明pos指向第一个结点，可以直接调用头插。

3.11 删除pos位置之后的值

//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* tmpnext = pos->next->next;
		free(pos->next);
		pos->next = tmpnext;
	}

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

3.12 删除pos位置的值

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

4. 简单测试

void test4()
{
	SLTNode* phead = NULL;

	SLTPushBack(&phead, 1);
	SLTPushBack(&phead, 2);
	SLTPushBack(&phead, 3);
	SLTPushBack(&phead, 4);
	SLTPushBack(&phead, 5);
	SLTPrint(phead);

	SLTNode* pos = SLTFind(phead, 5);

	SLTErase(&phead, pos);
	SLTPrint(phead);

	SLTDestory(&phead);
}
int main()
{
	test4();
	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

5. 源码展示

SList.h

#pragma once

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

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


//创建新结点
SLTNode* CreateNode(SLTDataType x);
//销毁
void SLTDestory(SLTNode** pphead);
//打印
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//在pos位置之前插入x
void SLTInsertPrev(SLTNode** pphead,SLTNode* pos, SLTDataType x);
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);
//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* 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

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"

//创建新结点
SLTNode* CreateNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//销毁
void SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = CreateNode(x);
	//空表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//找尾
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* tmpnext = (*pphead)->next;
	free(*pphead);
	*pphead = tmpnext;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//在pos位置之前插入x
void SLTInsertPrev(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
		SLTPushFront(pphead, x);
	else
	{
		SLTNode* newnode = CreateNode(x);
		SLTNode* cur = *pphead;
		while(cur->next != pos)
		{
			cur = cur->next;
		}
		newnode->next = pos;
		cur->next = newnode;
	}
}

//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* tmpnext = pos->next->next;
		free(pos->next);
		pos->next = tmpnext;
	}

}

//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(*pphead);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos=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
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

对单链表的讲解就到这里，欢迎大家指正！！！