【数据结构】单链表（带图详解）

一、单链表的定义及其结构

1.1.概念

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

1.2.单链表的结构

单链表（Singly Linked List）是一种常用的数据结构，它由若干个节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，而指针域则用于指向下一个节点的地址。单链表中每个节点只有一个指针域，指向下一个节点，最后一个节点的指针域指向 NULL，表示链表的结尾。

一看到这种结构有就会问，顺序表的存储方式和单链表哪里不同呢？

顺序表是一种基于数组实现的线性数据结构，其元素在内存中是连续存储的，其实就是数组的原理。而单链表是一种逻辑连续，物理不一定连续的线性表，实际上在内存中，每个结点可能会隔得很远，只是通过指针的方式将他们像绳子一样穿起来，也是每个结点都指向下一个结点地址空间。

1.3.单链表的特点

与顺序表不同，单链表的元素不是连续存储的，而是通过指针相连形成链式结构。因此，单链表具有以下优缺点。
优点：

• 支持动态内存分配。由于单链表不需要预先分配一段连续的空间，因此可以根据实际需求动态地申请、释放节点空间，避免浪费内存。
• 支持高效的插入、删除操作。由于单链表中的节点是通过指针相连的，因此在插入、删除一个节点时，只需要修改其前驱节点或后继节点的指针即可，时间复杂度为$O(1)$。

缺点：

• 不支持随机访问。由于单链表中的节点不是连续存储的，因此不能像数组一样通过下标来直接访问一个元素，需要从头节点开始遍历整个链表才能访问任意位置的元素。

二、单链表的实现

2.1.定义结点

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//数据域
	struct SListNode* next;//指针域
}SLTNode;

1
2
3
4
5
6
7
8

2.2.创建单链表

为一个新结点创建空间以及输入值

SLTNode* BuySLTNode(SLTDataType x) {
	SLTNode* newnode = new SLTNode;//申请空间，等同于malloc函数
	if (!newnode) {
		perror("fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10

根据上述函数，我们可以构造一个多个结点的单链表生成函数。

SLTNode* CreateSList(int n) {
	SLTNode* phead, * p; // 头节点
	phead = p = NULL;    // 指向当前节点的指针
	for (int i = 0; i < n; i++) {
		SLTDataType x;
		cin >> x;
		SLTNode* newnode = BuySLTNode(x);// 创建新节点
		if (!phead)phead = p = newnode;
		 // 插入到链表中
		else {
			p->next = newnode;
			p = p->next;
		}
	}
	return phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3.打印单链表

遍历链表，当链表中没有元素时，头指针所指向的就是NULL，也是停止循环的条件

void SLTPrint(SLTNode* phead)
{
	SLTNode* p=phead;
	//当前指针不为空就继续走
    while(!p)
    {
      printf("%d->",p->data);
      p=p->next;
    }
    printf("NULL\n");

}
1
2
3
4
5
6
7
8
9
10
11
12

2.4. 单链表尾插与尾删

尾插：
通过遍历链表找到尾节点，并将新节点链接到尾节点之后，实现了新元素的添加。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);//判断是否为空
	SLTNode* newnode = BuySLTNode(x);//创建一个新的结点
	//如果头为空的话就将新结点赋值给头结点
	if (*pphead == NULL) 
	{
		*pphead = newnode;
	}
	//
	else
	 {
		SLTNode* p = *pphead;
		//遍历到尾结点
		while (p->next) 
		{
			p = p->next;
		}
		//尾结点指向新结点
		p->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

尾删：
在链表为空或只有一个节点时，直接释放相应内存空间即可；否则通过遍历找到尾节点，并释放其空间，然后将前一个节点的 next 指针指向 NULL

void SLTPopBack(SLTNode** pphead) {

	//链表为空就直接退出
	if (*pphead == NULL) {
		return;
	}

	//链表只有头结点的话,pphead->next=null等同于只有头结点
	if ((*pphead)->next == NULL) 
	{
	   //删除
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* p = *pphead;
		//找到尾结点的前一个结点
		while (p->next->next) {
			p = p->next;
		}
		//删除
		free(p->next);
		p->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
24
25
26

2.4. 单链表头插与头删

头插：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;//新结点后面连接旧的头结点
	*pphead = newnode;//头结点更新为新节点
}
1
2
3
4
5

头删：

void SLTPopFront(SLTNode** pphead) {
	assert(pphead);//if (*pphead == NULL)return;

	SLTNode* p = (*pphead)->next;//头结点的下一个结点
	free(*pphead);
	*pphead = p;//头结点更新为p

}
1
2
3
4
5
6
7
8

2.4.查找某个结点

查找其实就和遍历单链表差不多，不过需要加一个数值是否相等的if判断语句

SLTNode* SListFind(SLTNode* plist, SLTDataType x) {
	SLTNode* p = plist;

	while (p) {
		if (p->data == x)return p;
		p = p->next;
	}
	return NULL;
}


1
2
3
4
5
6
7
8
9
10
11

2.5.插入

该函数通过指针操作在单链表的指定位置插入一个值为x的新结点，同时也考虑了插入位置是头结点的情况。需要注意的是，此函数没有考虑插入位置为空的情况，即需要确保 pos 非空指针。同时，该函数只能在某个结点之前插入新的结点，如果需要在链表尾部插入，则需要先找到链表尾结点，并将其 next 指针指向新结点。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pos);
     
    //一个值为x的新结点
	SLTNode* newnode = BuySLTNode(x);
	//头结点需要特殊处理
	if (*pphead == pos) {
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else {
		SLTNode* p = *pphead;//p为前一个结点
		
		//遍历停止在pos结点之前
		while (p->next != pos) {
			p = p->next;
		}
		
		p->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

2.6.删除\

若要删除的结点是头结点，则通过记录头指针的下一个结点来更新头结点，并释放原结点空间。

否则，需要寻找删除结点的前一个结点 pre，从而可以断开 pos 与 pre->next 之间的连接，同时释放 pos 的空间。因此，通过 while 循环遍历单链表找到前一个结点 pre。找到之后将 pre->next 指向待删除结点的下一个结点，并释放待删除结点空间。

void SListErase(SLTNode** pphead, SLTNode* pos) {
	assert(pos);
	assert(*pphead);

    //头结点需要特殊处理
	if (*pphead == pos)
	{
		SLTNode* p = (*pphead)->next;
		//记录头结点下一个结点
		free(*pphead);
        //更新头结点
		*pphead = p;
	}
	else {
		SLTNode* pre = *pphead;//pre为前一个结点
		while (pre->next!=pos) {
			pre = pre->next;
		}
		pre->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
21
22
23

总代码

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<bits/stdc++.h>
using namespace std;
//struct SListNode
//{
//	SLTDataType data;
//	struct SListNode* next;
//};
//typedef struct SListNode SLTNode;


//void SLTPushBack(SLTDataType x)
//{
//	SLTNode node;
//}

typedef int SLTDataType;

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

SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
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* SListFind(SLTNode* plist, SLTDataType x);

// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SLTNode* pos);

// 在pos之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x);


SLTNode* BuySLTNode(SLTDataType x) {
	SLTNode* newnode = new SLTNode;
	if (!newnode) {
		perror("fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;


}
SLTNode* CreateSList(int n) {

	SLTNode* phead, * p;
	phead = p = NULL;
	for (int i = 0; i < n; i++) {
		SLTDataType x;
		cin >> x;
		SLTNode* newnode = BuySLTNode(x);
		if (!phead)phead = p = newnode;
		else {
			p->next = newnode;
			p = p->next;
		}
	}
	return phead;

}


void SLTPrint(SLTNode* phead)
{
	SLTNode* p = phead;
	while (p) {
		cout << p->data << ">";
		p = p->next;
	}
	cout << "NULL" << endl;
}

//
//void SLTPushBack(SLTNode** pphead, SLTDataType x) {
//	assert(pphead);
//	SLTNode* newnode = BuySLTNode(x);
//	if (*pphead == NULL) {
//		*pphead = newnode;
//	}
//	else {
//		SLTNode* p = *pphead;
//		while (p->next) {
//			p = p->next;
//		}
//		
//		p->next = newnode;
//	}
//}
//
//
//void SLTPopBack(SLTNode** pphead) {
//
//	//链表为空就直接退出
//	if (*pphead == NULL) {
//		return;
//	}
//
//	//
//	if ((*pphead)->next == NULL) {
//		free(*pphead);
//		*pphead = NULL;
//	}
//	else 
//	{
//		SLTNode* p = *pphead;
//		while (p->next->next) {
//			p = p->next;
//		}
//		free(p->next);
//		p->next = NULL;
//	}
//}
//
//
//
//void SLTPushFront(SLTNode** pphead, SLTDataType x) {
//	SLTNode* newnode = BuySLTNode(x);
//	newnode->next = *pphead;
//	*pphead = newnode;
//}
//
//
//void SLTPopFront(SLTNode** pphead) {
//	assert(pphead);
//
//	if (*pphead == NULL)return;
//	
//	SLTNode* p = (*pphead)->next;
//	free(*pphead);
//	*pphead = p;
//	
//}


SLTNode* SListFind(SLTNode* plist, SLTDataType x) {
	SLTNode* p = plist;

	while (p) {
		if (p->data == x)return p;
		p = p->next;
	}
	return NULL;
}
//
//void SListInsertAfter(SLTNode* pos, SLTDataType x) {
//	assert(pos);
//	
//	
//	SLTNode* p = pos->next;
//	SLTNode* newnode = BuySLTNode(x);
//	pos->next = newnode;
//	newnode->next = p;
//
//	/*
//	 SLTNode* newnode = BuySLTNode(x);
//	 newnode->next=pos->next;
//	 pos->next=newnode;
//	*/
//}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pos);

	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == pos) {
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else {
		SLTNode* p = *pphead;
		while (p->next != pos) {
			p = p->next;
		}
		p->next = newnode;
		newnode->next = pos;
	}
}

//void SListEraseAfter(SLTNode* pos) 
//{
//	assert(pos);
//	if (pos->next)return;
//	else {
//		SLTNode* q = pos->next;
//		pos->next = q->next;
//		free(q);
//
//	}
//
//}

void SListErase(SLTNode** pphead, SLTNode* pos) {
	assert(pos);
	assert(*pphead);

	if (*pphead == pos)
	{
		SLTNode* p = (*pphead)->next;
		free(*pphead);
		*pphead = p;
	}
	else {
		SLTNode* pre = *pphead;
		while (pre->next!=pos) {
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);

	}
}

void SLTDestroy(SLTNode** pphead) {
	SLTNode* p = *pphead;
	while (p) {
		SLTNode* next = p->next;
		free(p);
		p = next;
	}
	*pphead = 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
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