数据结构--单链表（图文）_单链表头节点的目的

单链表的概念

在单链表中，每个元素（称为节点）包含两部分：一部分是存储数据的数据域，另一部分是存储下一个节点地址的指针域。这里的“单”指的是每个节点只有一个指向下一个节点的指针。

1. 节点：链表中的基本单元，通常由数据域和指针域组成。数据域用于存储实际的数据，而指针域用于指向链表中的下一个节点。

2. 链：通过节点中的指针链接形成的序列。在单链表中，这种链接是单向的，即只能从一个节点指向下一个节点。

3. 头节点：链表的第一个节点，用于标识链表的开始。有时，头节点仅作为链表的头部标识，不存储实际数据。

4. 尾节点：链表的最后一个节点，其指针域通常为空（NULL），表示链表的结束。

5. 非连续性：与数组不同，单链表的节点在内存中不必连续存储。每个节点的位置由其前一个节点的指针决定。

6. 动态性：单链表的大小是动态的，可以在运行时通过增加或删除节点来改变链表的长度。

单链表的主要特点是其灵活性和动态性，它可以有效地进行插入和删除操作，尤其是在不知道数据数量的情况下，或者当数据量变化较大时。但是，由于需要通过指针进行遍历，单链表在访问特定元素时可能不如数组高效。以下是其在各种操作中的优势：

• 插入和删除：在单链表中插入或删除节点只需要O(1)的时间，前提是已经有了指向要操作节点的指针。
• 空间利用：单链表不需要预分配固定的存储空间，它可以根据需要动态地分配内存。

单链表的实现

首先创建三个文件：

• SList.h —— 用于声明函数的头文件
• SList.c —— 单链表主要函数的实现
• test.c——测试单链表。

创建单链表

typedef int SLTDataType;//方便后续使用更改类型

//创建一个节点
typedef struct SListNode
{
	SLTDataType data;//该节点储存的数据
	struct SListNode* next;//指向下一个节点的指针
}SListNode;
1
2
3
4
5
6
7
8

销毁链表

从前向后依次释放节点，最后将头节点置为NULL 。

void SListDesTroy(SListNode** pphead)//销毁链表
{
	assert(pphead && *pphead);
	SListNode* pcur = *pphead;
	while (pcur)
	{
		SListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

打印节点数据

遍历依次打印即可。

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

申请一块节点

在进行插入节点时，我们需要先申请一块节点来进行插入，所以我们将申请节点单独封装成一个函数。

SListNode* SLTBuyNode(SLTDataType x)//增加节点(空间)
{
	//开辟一个节点空间
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//设置数据并返回该节点地址
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

尾插数据

两种情况

• 情况一：链表为空直接申请新节点给头节点；
• 情况二：链表不为空，遍历找到尾节点，再将新节点接入即可。

void SLTPushBack(SListNode** pphead, SLTDataType x)//尾插数据
{
	assert(pphead);//不能为空，否则就会对空指针解引用
	if (*pphead == NULL)//指向头节点的指针为空，也就是链表为空
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* newnode = *pphead;
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		newnode->next = SLTBuyNode(x);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

头插数据

两种情况

• 情况一：链表为空直接申请新节点给头节点。
• 情况二：链表不为空，先将pphead（头节点）保存起来，然后让pphead指向新插入的节点，在让*pphead->next指向刚才保存好的原本的头节点。
  

void SLTPushFront(SListNode** pphead, SLTDataType x)//头插数据
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = SLTBuyNode(x);
		(*pphead)->next = pcur;
	}
}

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

尾删数据

两种情况

• 情况一：链表只有一个数据，直接释放该节点并将头节点置为空。
• 情况二：链表有多个数据节点，遍历找到尾节点的前一个节点，释放该节点的next节点，再将该节点的next置为空。
  

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

头删数据

两种情况

• 情况一：链表只有一个数据，直接释放该节点并将头节点置为空。
• 情况二：链表有多个数据节点，先将pphead（头节点）保存起来，然后让pphead指向*pphead->next（新的头节点），然后释放刚才保存的节点（原头节点）。
  

void SLTPopFront(SListNode** pphead)//头删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = (*pphead);
		*pphead = (*pphead)->next;
		free(pcur);
	}
}

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

查找数据

从前向后遍历整个链表，如果 plist->data == x，就说明找到了，返回 plist 此时的值，如果plist = NULL了，就说明这个链表中没有该数据，则返回空。

SListNode* SLTFind(SListNode* phead, SLTDataType x)//查找数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

有了查找函数，就可以实现任意位置的增加数据和删除数据的操作了。

在指定位置之前插入数据

两种情况

• 情况一：指定位置为头节点则直接头插。
• 情况二：指定位置为其他节点，遍历找到指定节点的前一个节点，在该节点后插入新数据。
  

void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)//在指定位置之前插入数据
{
	assert(pphead&&*pphead);
	if (*pphead == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		SListNode* newnode = SLTBuyNode(x);
		pcur->next = newnode;
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在指定位置之后插入数据

在指定位置后直接插入即可。

void SLTInsertAfter(SListNode* pos, SLTDataType x)//在指定位置之后插入数据
{
	assert(pos);
	SListNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7

删除指定位置节点

两种情况

• 情况一：指定位置为头节点则直接头删。
• 情况二：指定位置为其他节点，遍历找到指定位置的前一个节点，先将该节点的next指针指向指定位置的next位置，然后再释放指定位置。（不能改变顺序，否则找不到指定位置的下一个节点了）
  

void SLTErase(SListNode** pphead, SListNode* pos)//删除pos节点
{
	assert(*pphead && pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->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

删除指定位置之后的数据

先将指定位置的的下一个位置保存起来，让指定位置的next指针指向保存位置的下一个位置，然后释放掉保存的位置也就是指定位置之后的数据。

void SLTEraseAfter(SListNode* pos)//删除pos之后的节点
{
	assert(pos && pos->next);
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = NULL;	
}
1
2
3
4
5
6
7
8

单链表源码

SList.h

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

typedef int SLTDataType;

//创建一个节点
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;

SListNode* SLTBuyNode(SLTDataType x);//增加节点(空间)


void SLTPrint(SListNode* phead);//打印节点数据


void SListDesTroy(SListNode** pphead);//销毁链表


void SLTPushBack(SListNode** pphead, SLTDataType x);//尾插数据


void SLTPushFront(SListNode** pphead, SLTDataType x);//头插数据


SListNode* SLTFind(SListNode* phead, SLTDataType x) ;//查找数据


void SLTPopBack(SListNode** pphead);//尾删数据


void SLTPopFront(SListNode** pphead);//头删数据


void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在指定位置之前插入数据


void SLTInsertAfter(SListNode* pos, SLTDataType x);//在指定位置之后插入数据


void SLTErase(SListNode** pphead, SListNode* pos);//删除pos节点


void SLTEraseAfter(SListNode* pos);//删除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
39
40
41
42
43
44
45
46
47
48
49
50

SList.c

#include"SList.h"

SListNode* SLTBuyNode(SLTDataType x)//增加节点(空间)
{
	//开辟一个节点空间
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//设置数据并返回该节点地址
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPrint(SListNode* phead)//打印节点数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
void SListDesTroy(SListNode** pphead)//销毁链表
{
	assert(pphead && *pphead);
	SListNode* pcur = *pphead;
	while (pcur)
	{
		SListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

void SLTPushBack(SListNode** pphead, SLTDataType x)//尾插数据
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* newnode = *pphead;
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		newnode->next = SLTBuyNode(x);
	}
}



void SLTPushFront(SListNode** pphead, SLTDataType x)//头插数据
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = SLTBuyNode(x);
		(*pphead)->next = pcur;
	}
}


SListNode* SLTFind(SListNode* phead, SLTDataType x)//查找数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}


void SLTPopBack(SListNode** pphead)//尾删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next->next)
		{
			pcur = pcur->next;
		}
		free(pcur->next);
		pcur->next = NULL;
	}
}


void SLTPopFront(SListNode** pphead)//头删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = (*pphead);
		*pphead = (*pphead)->next;
		free(pcur);
	}
}


void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)//在指定位置之前插入数据
{
	assert(pphead&&*pphead);
	if (*pphead == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		SListNode* newnode = SLTBuyNode(x);
		pcur->next = newnode;
		newnode->next = pos;
	}
}


void SLTInsertAfter(SListNode* pos, SLTDataType x)//在指定位置之后插入数据
{
	assert(pos);
	SListNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


void SLTErase(SListNode** pphead, SListNode* pos)//删除pos节点
{
	assert(*pphead && pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


void SLTEraseAfter(SListNode* pos)//删除pos之后的节点
{
	assert(pos && pos->next);
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = 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
190