【数据结构】单链表——单链表的定义及基本操作的实现（头插、尾插、头删、尾删、任意位置的插入与删除）

🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

---

前言

  顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但是插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需要修改指针，但也会失去顺序表可随机存取的优点。

---

一、单链表的定义

  线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素本身的信息外，还需要存放一个指向其后继的指针。单链表的结构如下图所示，其中data为数据域，存放数据元素；next为指针域，存放其后继节点的地址。

  利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表时非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的借点时，需要从头开始遍历，依次查找。

下图为一个带头结点的单链表，头指针pList，它指向的是头结点，除最后一个节点外，它们的next都指向下一个点的地址，对于最后一个节点的next指向NULL。

从上图可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
链表中的结点一般都是从堆上申请的。
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间有可能连续，有可能不连续。

头节点和头指针的区分： 不管带不带头节点，头指针都始终指向链表的第一个节点，而头节点是带头结点的链表的第一个结点，结点内通常不存储信息。

二、单链表上基本操作的实现（不带头结点）

单链表中结点类型的描述如下：

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

1. 动态申请一个节点

对于插入操作来说，需要先动态申请一个结点，并将该结点的数值域与指针域进行赋值，指针域都设置为NULL。

SListNode* BuySListNode(SLTDateType data)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11

2. 单链表尾插

在进行尾插操作时，要考虑到的一点就是在插入该结点之前此单链表是否为空，为空时则直接将该结点设置为头结点就行，若不为空就循环遍历找到最后一个结点进行尾插就行。
还有一点最为重要，就是在进行函数传参时，第一个参数为二级指针，这是为什么呢？首先定义一个头指针，它是用来指向链表第一个节点，当你以一级指针进行传参时，那么在该函数内得到头指针是一份临时拷贝，所以对该指针的临时拷贝进行操作时就不会出现想要得到的效果，所以说，凡是有关头指针的操作就是传二级指针，对于后续结点的插入其实可以传递一级指针，因为所要改变的不是头指针，而是结点这个结构体。我感觉吧，可以把该链表想象为一个双头蛇，一个头为另一个头的拷贝，当你对那个拷贝的头操作后并不会影响另外一个头，但是对于后续节点来说就可以比作为蛇的身子。

void SListPushBack(SListNode** Head, SLTDateType data)
{
	assert(Head);
	SListNode* newNode = BuySListNode(data); //创建一个值为data的结点
	if (*Head == NULL)
	{
		*Head = newNode;
	}
	else
	{
		SListNode* cur = *Head;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 单链表尾删

在尾删时同样也要传递二级指针，有可能该链表只有一个结点。

void SListPopBack(SListNode** Head)
{
	if (*Head == NULL) //链表为空
	{
		return;
	}
	else if ((*Head)->next == NULL) //链表只有一个结点
	{
		*Head = NULL;
	}
	else  //链表中有多个结点
	{
		SListNode* cur = (*Head)->next;
		SListNode* prev = *Head; //prev为前序指针
		while (cur->next)
		{
			cur = cur->next;
			prev = prev->next;
		}
		//在循环退出后，prev指针指向倒数第二个结点
		prev->next = NULL;
		free(cur);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4. 单链表头插

void SListPushFront(SListNode** Head, SLTDateType data)
{
	assert(Head);
	SListNode* newNode = BuySListNode(data);  //创建一个值为data的结点
	newNode->next = *Head;
	*Head = newNode;
}
1
2
3
4
5
6
7

5. 单链表头删

void SListPopFront(SListNode** Head)
{
	if (*Head == NULL) //链表为空
	{
		return;
	}
	else
	{
		SListNode* cur = *Head;
		*Head = (*Head)->next;
		free(cur);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

6. 单链表查找

此函数旨在查找元素，并不会去修改头指针的指向，所以传一级指针即可。

SListNode* SListFind(SListNode* Head, SLTDateType data)
{
	assert(Head);
	while (Head)
	{
		if (Head->data == data)
		{
			return Head;
		}
		Head = Head->next;
	}
	return NULL; //没有找到就返回NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13

7. 单链表在pos位置之后插入data

该操作是在pos位置之后进行插入（该pos位置通过查找函数获取），当然也可以在pos位置之前插入，不同的是只需改变查找函数即可，让查找函数返回pos位置的前一个结点指针。
因为不管任意位置插入还是删除都在pos位置之后，所以并不会涉及到头指针，因此不需要传递二级指针。若是pos位置之前插入删除则需要考虑有可能涉及到头指针指向位置的改变。

void SListInsertAfter(SListNode* pos, SLTDateType data)
{
	SListNode* newNode = BuySListNode(data);
	if (NULL == pos)
		return;
	newNode->next = pos->next;  //这里的两行代码顺序不能乱，因为会导致pos之后的结点找不到
	pos->next = newNode;
}
1
2
3
4
5
6
7
8

8. 单链表删除pos位置之后的值

void SListDelAfter(SListNode* pos)
{
	SListNode* newNode = NULL;
	if (NULL == pos || NULL == pos->next)
		return;
	newNode = pos->next; //同样，此处代码不能乱
	pos->next = newNode->next;
	free(newNode);
}
1
2
3
4
5
6
7
8
9

---

三、源代码及运行结果展示

1. SList.h

结构体创建及函数声明

#include 
#include 
#include 

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

SListNode* BuySListNode(SLTDateType data);

void SListPrint(SListNode* Head);

void SListPushBack(SListNode** Head, SLTDateType data);

void SListPushFront(SListNode** Head, SLTDateType data);

void SListPopBack(SListNode** Head);

void SListPopFront(SListNode** Head);

SListNode* SListFind(SListNode* Head, SLTDateType data);

void SListInsertAfter(SListNode* pos, SLTDateType data);

void SListTest();
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

2. SList.c

方法实现

#include "SList.h"

SListNode* BuySListNode(SLTDateType data)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

void SListPushBack(SListNode** Head, SLTDateType data)
{
	assert(Head);
	SListNode* newNode = BuySListNode(data);
	if (*Head == NULL)
	{
		*Head = newNode;
	}
	else
	{
		SListNode* cur = *Head;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newNode;
	}
}

void SListPushFront(SListNode** Head, SLTDateType data)
{
	assert(Head);
	SListNode* newNode = BuySListNode(data);
	newNode->next = *Head;
	*Head = newNode;

}

void SListPopBack(SListNode** Head)
{
	if (*Head == NULL)
	{
		return;
	}
	else if ((*Head)->next == NULL)
	{
		*Head = NULL;
	}
	else
	{
		SListNode* cur = (*Head)->next;
		SListNode* prev = *Head;
		while (cur->next)
		{
			cur = cur->next;
			prev = prev->next;
		}
		prev->next = NULL;
		free(cur);
	}
}

void SListPopFront(SListNode** Head)
{
	if (*Head == NULL)
	{
		return;
	}
	else
	{
		SListNode* cur = *Head;
		*Head = (*Head)->next;
		free(cur);
	}
}

SListNode* SListFind(SListNode* Head, SLTDateType data)
{
	assert(Head);
	while (Head)
	{
		if (Head->data == data)
		{
			return Head;
		}
		Head = Head->next;
	}
	return NULL;
}

void SListInsertAfter(SListNode* pos, SLTDateType data)
{
	SListNode* newNode = BuySListNode(data);
	if (NULL == pos)
		return;
	newNode->next = pos->next;
	pos->next = newNode;
}

void SListDelAfter(SListNode* pos)
{
	SListNode* newNode = NULL;
	if (NULL == pos || NULL == pos->next)
		return;
	newNode = pos->next;
	pos->next = newNode->next;
	free(newNode);
}

void SListPrint(SListNode* Head)
{
	SListNode* cur = Head;
	while (cur)
	{
		printf("%d---->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void SListTest()
{
	SListNode* ListNode = NULL;
	SListPushFront(&ListNode, 0);
	SListPushBack(&ListNode, 1);
	SListPushBack(&ListNode, 2);
	SListPushBack(&ListNode, 3);
	SListPushBack(&ListNode, 4);
	SListPushBack(&ListNode, 5);
	SListPrint(ListNode);

	SListPushFront(&ListNode, -1);
	SListPrint(ListNode);

	SListPopBack(&ListNode);
	SListPopBack(&ListNode);
	SListPrint(ListNode);

	SListPopFront(&ListNode);
	SListPrint(ListNode);

	SListNode* ret = SListFind(ListNode, 0);
	if (ret == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}

	SListInsertAfter(SListFind(ListNode, 2), 0);
	SListPrint(ListNode);

	SListDelAfter(SListFind(ListNode, 2));
	SListPrint(ListNode);
}
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

3. test.c

主函数

#include "SList.h"

int main()
{
	SListTest();
	return 0;
}
1
2
3
4
5
6
7

结果展示：

总结

  对于链表来说有着自己的特点，比如：在内存中不需要连续的地址进行存储，元素之间通过指针相连、逻辑相邻但物理上并不一定相邻，插入与删除操作不需要移动大量的元素，但是无法随机存取，只能从头遍历。而对于不带头结点的单链表来说，尤其要注意对头指针的指向修改时要使用二级指针。

  文章若有不足的地方还请大佬指正！！！