【数据结构】【版本1.1】【线性时代】——单链表

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

数据结构世界——单链表（Single Linked List）

一、顺序表的问题

让我们回顾一下顺序表：

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

那么，如何解决以上问题呢？

二、链表的概念

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

---

• 链表的结构跟火车车厢相似，将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。
• 车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？
• 最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

---

在链表里，每节“车厢”是怎样的呢？

• 与顺序表不同的是，链表的每节"车厢"都是独立申请下来的空间，我们称之为结点/节点。
• 节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。

图中指针变量 plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

---

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

三、单链表的模拟实现

3.1 定义

//单链表
typedef int SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLNode;
1
2
3
4
5
6
7

• 在结构体内嵌套结构体，一定要表明struct，而不能直接使用typedef后的名称

3.2 打印

先来看看怎么实现链表的打印，这样更有助于我们理解它的结果。

void SLPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

• 先用cur指针接受头部地址，当cur不为NULL时，则打印当前节点的数据，并将该节点存储的下一节点的地址赋值给cur
• 这样cur指针就能一直访问整个链表，直到最后一个节点（该节点存储地址为NULL）

3.3 创建新节点

每次插入，要生成新节点，申请空间……一系列操作 ，所以我们可以把它该过程写成一个函数，以增强函数的复用性。

SLNode* BuySLNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• malloc动态开辟内存生成一个新节点，再将数据放入新节点中，初始地址为NULL

3.4 头插

void SLPushFront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuySLNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7

• 先创建新节点，再将新节点链接在链表头部
• 更新链表指针

---

可能很多人有疑惑，为什么要用二级指针呢？请看接下来的测试：

与顺序表不同的是，我们不再创建结构体，而是创建结构体指针，初始指向NULL。那么，我们要在函数内改变外部指针指向的地址，就要使用二级指针。

3.5 尾插

void SLPushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	//1.空链表
	//2.非空链表
	SLNode* newnode = BuySLNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			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

• 如果为空链表，则直接将新节点的地址传给外部的链表指针
• 如果为非空链表，先申请新节点，再用循环一直向后访问，找到最后一个节点的地址，将新节点链接在最后

3.6 头删

void SLPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}
1
2
3
4
5
6
7
8

• 将链表指针的地址改成第二个节点的，并将第一个节点的空间释放

3.7 尾删

void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//一个节点
	//多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* 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

• 如果为一个节点，直接释放空间，并赋值为NULL
• 如果有多个节点，找到倒数第二个节点，解引用将其next指针指向的空间（最后一个节点）释放，再赋值为NULL

3.8 查找与修改

SLNode* SLFind(SLNode* phead, SLDataType x)
{
	SLNode* 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
13

• 找到返回对应节点的地址，找不到返回NULL
• 能查找，也意味着能修改，因为我们获取了该节点的地址，自然能在外部解引用修改数据，这样，一个函数就有两个功能 ——查找和修改

3.9 指针断言

这里说一下关于assert断言的情况 ，并不是所有函数参数的指针都需要断言，而是要根据实际情况分析而定。

---

//打印
void SLPrint(SLNode* phead);
//查找
SLNode* SLFind(SLNode* phead, SLDataType x);
1
2
3
4

打印与查找，则不需要断言，因为空链表也可以打印，也可以查找，就比如你的银行账户没有钱，就不能显示出来看看，不能查询吗？

---

//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
1
2
3
4

头插与尾插，对于其二级指针需要断言，一级指针不用，因为pphead指向链表指针plist，所以不能为空，而链表指针可为空（即为空链表）。

---

//头删
void SLPopFront(SLNode** pphead);
//尾删
void SLPopBack(SLNode** pphead);
1
2
3
4

头删与尾删，其二级指针与一级指针都要断言，除了pphead不能为空，*pphead也不能为空，因为空链表就不能进行删除操作。

3.10 指定插入

这里有两种插入方式，在pos前插入和在pos后插入 。

在pos前插入

void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = BuySLNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 如果pos为头部地址时，即为头插，可复用头插函数
• 如果pos不为头部地址时，再找到pos前一个节点的地址，然后创建新节点，最后将它们链接起来

---

在pos后插入

void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7

• 相比于在pos前插入，单链表其实更适合在pos后插入，直接创建新节点，进行链接即可

ps：链接的过程有顺序问题，不能写反了，要不然会环状链接。

3.11 指定删除

这里也有两种删除方式，在pos删除和在pos后删除。

在pos删除

void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 如果pos为头部地址时，即为头删，可复用头删函数
• 如果pos不为头部地址时，再找到pos前一个节点的地址，链接pos后一个节点，再释放pos节点空间

---

在pos后删除

void SLEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLNode* next = pos->next;
	pos->next = pos->next->next;
	free(next);
}
1
2
3
4
5
6
7
8

• 相比于在pos位置删除，单链表其实更适合在pos后删除，这里用一个next指针，保存pos下一个节点的地址，在pos链接往后第二个节点后，再对next节点空间释放

3.12 销毁

void SLDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 在每次循环内临时创建一个新指针next，记录下一个节点的地址，让cur释放所指空间后，还可以找到下一个节点，最后把链表指针解引用置空

---

当然，这里你也可以传一级指针，不在函数内部把外部的链表指针置为NULL，而在外部手动置空，跟free函数的用法一样，实现半自动。

void SLDestroy(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
}
1
2
3
4
5
6
7
8
9
10

真诚点赞，手有余香