C++数据结构学习——单链表_单链表的优缺点

单链表定义

单链表（Singly Linked List）是一种常见的数据结构，用于存储一系列元素，这些元素被组织成一个链表，其中每个元素被称为节点（Node）。每个节点包含两部分信息：

数据（Data）：用来存储具体的元素值。
指针（Pointer）：用来指向下一个节点的位置。
1
2

单链表的特点是节点之间只有一个指针，指向下一个节点，而最后一个节点的指针通常为空（或者指向一个特殊的终止标志）。

单链表的优缺点

单链表（Singly Linked List）是一种常见的数据结构，具有一些优点和缺点，这些特点使得它在特定的应用场景中更适合使用。

单链表的优点：

1. 高效的插入和删除操作： 在单链表中，插入和删除元素非常高效，只需要调整指针的指向，而不需要像数组那样搬移元素。这使得单链表在需要频繁插入和删除操作的情况下非常有用。

2. 动态内存分配： 单链表的大小可以根据需要动态增长，而不需要预先分配固定大小的内存空间。这使得它更适合处理未知大小的数据集。

3. 不浪费内存： 单链表只需额外的指针来连接节点，而不像数组那样需要预分配大块连续内存空间。这可以减少内存的浪费。

4. 易于实现： 单链表的基本操作相对简单，易于实现。这使得它成为教学和学习数据结构的良好选择。

单链表的缺点：

1. 随机访问慢： 单链表中要访问特定位置的元素需要从头节点开始遍历链表，直到找到目标节点。这导致访问时间是线性的，而不像数组那样可以常数时间内访问特定位置的元素。

2. 额外的内存开销： 每个节点都需要一个额外的指针来指向下一个节点，这会导致内存开销相对较大，特别是当节点数量很大时。

3. 不适用于大型数据集： 由于额外的指针和节点开销，单链表在存储大量数据时可能不是最佳选择。对于大型数据集，可能会消耗大量内存。

4. 无法直接访问前一个节点： 单链表只有一个指向下一个节点的指针，不能直接访问前一个节点。如果需要双向访问，可以考虑使用双向链表。

总之，单链表是一种非常灵活和高效的数据结构，特别适用于需要频繁插入和删除操作的情况。然而，在需要快速随机访问元素或者对内存使用有限制的情况下，可能需要考虑其他数据结构。不同的数据结构适用于不同的应用场景，选择合适的数据结构取决于问题的需求和约束。

C语言代码实现

声明文件

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

typedef int SLDataType; 

typedef struct SListNode
{
	int data;
	struct SListNode* next;
	//strcut STLNode* next; //不能这样定义

}SLTNode;

SLTNode* BuySLTNode(SLDataType x);
SLTNode* CreateSList(int n); //创建n个节点
void SLTPrint(SLTNode* phead); //打印链表

void SLTPushBack(SLTNode** pphead, SLDataType x); //尾插
void SLTPopBack(SLTNode** pphead); //尾删
void SLTPushFront(SLTNode** pphead, SLDataType x);//头插
void SLTPopFront(SLTNode** pphead); //头删

SLTNode* SLTFind(SLTNode* plist, SLDataType x); //查找

void SLTInsertAfter(SLTNode* pos, SLDataType x);// 插入 pos为插入的位置，x为插入的值
void SLTInert(SLTNode** pphead, SLTNode* pos, SLDataType x); //前插

void SLTEraseAfter(SLTNode* pos); //删除pos后的一个节点
void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos节点

void SLTDestroy(SLTNode** pphead); //释放单链表
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

实现文件

#include "SList.h"

SLTNode* BuySLTNode(SLDataType x)//创建一个节点，并将x放到节点的data中
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

SLTNode* CreateSList(int n) //创建n个节点
{
	SLTNode* phead = NULL, *ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i); //创建一个新节点，节点中data数据放入 i
		if (phead == NULL)
		{
			ptail = phead = newnode; //初始化第一个节点
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode; // ？？？
		}
	}
	return phead;
}

void SLTPrint(SLTNode* phead) //打印链表
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next; // 将cur结构体中的next 地址传给cur，cur指向下一个节点的地址
	}
	printf("NULL\n");
}

void SLTPushBack(SLTNode** pphead, SLDataType x)//尾插
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL) 
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//void SLTPopBack(SLTNode* phead) //尾删
//{
//	SLTNode* tail = phead;//将传入的链表的地址传递给tail
//	while (tail->next != NULL)
//	{
//		tail = tail->next;
//	}
//	free(tail);
//	tail = NULL; //错误！！只将最后一个节点释放了，前一个节点指向的next地址不是NULL
//}

void SLTPopBack(SLTNode** pphead) //尾删
{
	//assert(*pphead); //断言，对链表为空的情况进行干预
	if (*pphead == NULL) // 两种检查方式
	{
		return;
	}

	if ((*pphead)->next == NULL) //当只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;//将传入的链表的地址传递给tail
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL; //此时prev最后一个节点，将最后一个节点的next置空
	}
}

void SLTPushFront(SLTNode** pphead, SLDataType x)//头插
{
	SLTNode* newnode = BuySLTNode(x); //创建一个新节点
	newnode->next = *pphead; //新节点的next指向pphead
	*pphead = newnode; //pphead再重新指向第一个节点
}


void SLTPopFront(SLTNode** pphead) //头删
{
	assert(*pphead);//断言检查
	SLTNode* plist = *pphead;
	free(*pphead);
	*pphead = plist->next;

}

SLTNode* SLTFind(SLTNode* phead, SLDataType x) //查找
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL; //返回为空证明没有找到
}

void SLTInsertAfter(SLTNode* pos, SLDataType x)// 插入 pos为插入的位置，x为插入的值
{
	assert(pos != NULL); //这里要防止pos为NULL的情况
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next; //先将newnode节点指向pos的下一个节点
	pos->next = newnode;
}

void SLTInert(SLTNode** pphead, SLTNode* pos, SLDataType x) //前插，造pos之前插入
{
	assert(pos != NULL);
	if (*pphead == pos) //如果为第一个节点，头插
	{
		SLTNode* newnode = BuySLTNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		SLTNode* prev = *pphead; //定义一个新节点，用于查找pos的前一个节点
		while (prev->next != pos) // 查找pos的前一个指针
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x); //新建一个节点
		newnode->next = pos; //新节点的下一个节点指向pos
		prev->next = newnode; // newnode的前一个节点指向newnode
	}
}

void SLTEraseAfter(SLTNode* pos) //删除pos后的一个节点
{
	assert(pos != NULL);
	if (pos->next == NULL) //如果pos节点为最后一个节点
	{
		return; //无法删除，直接退出
	}
	else //如果为中间位置
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode); //释放pos后的节点
	}
}

void SLTErase(SLTNode** pphead, SLTNode* pos) //删除pos节点
{
	assert(pos != NULL);
	if (*pphead == pos) //当pos位置为第一个节点时
	{
		*pphead = pos->next;
		free(pos);//释放掉pos节点
	}
	else
	{
		SLTNode* prev = *pphead; //创建一个新节点，用于找pos的前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next; // 将pos的前一个节点的next指向pos的后一个节点
		free(pos); // 释放pos，避免内存泄漏
	}
}

void SLTDestroy(SLTNode** 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
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

测试代码

#include <stdio.h>
#include "SList.h"

//顺序表的缺点：
// 1、空间不够的情况下，需要进行扩容。扩容（尤其异地扩容）是由一定代价的，其次还可能存在一定的空间浪费
// 2、头部或者中部插入删除，需要挪动数据，效率低下

// 链表头插效率很高

void SListTest1()
{
	/*
	SLTNode* n1 = BuySLTNode(1);
	SLTNode* n2 = BuySLTNode(2);
	SLTNode* n3 = BuySLTNode(3);
	SLTNode* n4 = BuySLTNode(4);

	n1->next = n2; // n1节点的next指向n2节点的地址
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	*/

	SLTNode* plist = CreateSList(10);
	SLTPrint(plist);
}

void SListTest2()
{
	SLTNode* plist = CreateSList(5);
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
}

void SListTest3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPushBack(&plist, 500);
	SLTPrint(plist);

	//SLTPopBack(&plist);
	//SLTPopBack(&plist);
	//SLTPopBack(&plist);
	//SLTPopBack(&plist);
	//SLTPopFront(&plist);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 300);
	if (pos != NULL)
	{
		printf("找到了！\n");
		//SLTInsertAfter(pos, 30); //后插
		//SLTInert(&plist, pos, 30); //前插
		//SLTEraseAfter(pos); //删除pos后一个节点
		SLTErase(&plist, pos);
	}
	else
	{
		printf("没有找到！！\n");
	}
	SLTDestroy(&plist); //销毁链表
	SLTPrint(plist);


}

void Swap1(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void Swap2(int** pp1, int** pp2)
{
	int* tmp = *pp1;
	*pp1 = *pp2;
	*pp2 = tmp;
}

int main()
{
	//SListTest1();
	//SListTest2();
	SListTest3();

	//int a = 1, b = 0;
	//Swap1(&a, &b);
	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