【数据结构】解密链表之旅（单链表篇）

前言

哈喽大家好，我是野生的编程萌新，首先感谢大家的观看。数据结构的学习者大多有这样的想法：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学的很累。我想让大家知道的是：数据结构非常有趣，很多算法是智慧的结晶，我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏，在这里我将把数据结构内容以有趣易懂的方式展现给大家。

 1.线性表链式存储结构定义

在上一篇博客中我们提到了线性表有两种存储方式，一种是顺序存储，一种是链式存储。线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据可以存在内存未被占用的任意位置。

 在之前的顺序结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。链式存储结构相比于顺序存储结构的优势在于插入和删除操作的高效性。由于链式存储结构中的元素通过指针连接，所以在插入和删除元素时，只需改变指针的指向，不需要移动其他元素，因此效率较高。而顺序存储结构需要移动元素位置，效率较低。线性表的链式存储结构是通过节点之间的指针来实现的，每个节点包含两个部分：数据域（存储数据元素信息的域）和指针域（存储直接后继位置的域）。n个节点链接成一个链表，即为线性表的链式存储结构（链表）。

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的存储结构就与火车车厢相似，淡季时车次的车厢会有所减少，相对的在旺季时车次的车厢会有所增加。这需要将火车的车厢去掉或者加上，不会影响其他的车厢，每节车厢都是独立的。就像下面这张图：

每节车厢都是独立的，每节车厢都有自己的车门。假设每节车厢都是锁住的状态，他们都需要不同的钥匙来解锁且每次只能携带一把钥匙，该如何从车头走向车尾呢？最简单的方法就是：在每节车厢存放下一节车厢的钥匙。那么在链表这个“火车”中，每节“车厢”的情况是什么样子的呢？

 与顺序表不同的是，链表每节“车厢”都是独立申请下来的空间，我们称为“节点/结点”。对于线性表来说，总得有头有尾啊，链表也不能例外。我们把链表中的第一个节点存储的位置叫做头指针，那么整个链表的存取就必须是从头指针开始运行了。之后的每一个节点，其实就是上一个后继指针指向的位置。既然如此，那最后一个节点的指针指向哪里？什么！最后一个？当然就意味着后继不存在了，所以我们规定最后一个节点的指针为空。有时候，我们为了更加方便地对链表进行操作，会在单链表的第一个节点之前附设一个节点，我们成为头节点。下图为在上图基础上加一个头节点：

 头指针和头结点的异同点：

1. 头指针和头节点都是链表的概念，用于表示和操作链表的入口。
2. 头指针是一个指针变量，存储的是第一个节点的地址；头节点是一个特殊节点，位于链表的第一个位置，不包含有用的数据。
3. 头指针用于遍历链表中的所有节点；头节点用于简化对链表的操作。
4. 头指针在链表中的位置是可变的，可以随着节点的插入或删除而改变；头节点在链表中位置固定，一般不会发生变化。

链表的种类非常多样，我们主要根据是否有头节点、单向或双向、是否循环将链表分为8类：

1.带头或者不带头

2.单向或者双向：

 3.是否循环：

虽然有这么多的链表结构，其实我们最常用的还是两种结构：不带头的单向链表和双向循环链表。我们这一篇就主要围绕单链表来介绍。 

2.单链表各个功能的实现

单链表是一种最简单的链表数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储节点的数据，指针域用于指向下一个节点。单链表的特点是节点之间只有一个指针连接，每个节点只能访问下一个节点，不能访问前一个节点。链表的头节点是第一个节点，尾节点是最后一个节点，尾节点的指针域通常指向一个空地址（NULL）。用C语言来描述单链表的结构指针：

typedef int SLNDataType;
typedef struct SListNode 
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;

在这里我们主要详细介绍单链表的插入删除等操作。在单链表中插入有尾插、头插、任意位置插入等操作，每次插入都需要申请空间，每次申请空间的操作都相同，我们干脆写一个函数来实现申请空间，这样能使我们的操作更加方便。

SLNode* CreateNode(SLNDataType* x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

2.1单链表的尾插和尾删

单链表的尾插操作步骤：

1. 创建一个新的节点，设置其数据域为要插入的值，指针域为空。
2. 检查链表是否为空。若为空，则将新节点作为链表的第一个节点。
3. 若链表不为空，需要找到链表的最后一个节点。从链表的头节点开始遍历，直到遍历到最后一个节点（即指针域为空的节点）。
4. 将最后一个节点的指针域指向新节点，将新节点插入到链表中。

我们需要使用单链表指针变量来创建头指针，所以我们在传参时要使用二级指针。我们来实现一下单链表的尾插操作：

void SLPushBack(SLNode** phead, SLNDataType x)
{
	assert(phead);
	SLNode* newnode=CreateNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		SLNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

单链表的尾删具体操作步骤为：

1. 判断链表是否为空。如果链表为空，则无法进行尾删操作，直接返回。
2. 如果链表只有一个结点，则将链表的头指针置为空，删除这个结点即可。
3. 如果链表有多个结点，则需要遍历到倒数第二个结点，即指针指向要删除结点的前一个结点。
4. 将前一个结点的 next 指针指向 NULL，断开要删除结点和链表的连接。
5. 释放要删除结点的内存空间。

我们来实现一下单链表尾删操作：

void SLPopBack(SLNode** phead)
{
	assert(phead);
	assert(*phead);
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* tail = *phead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
 
	}
}

2.2单链表的头插和头删

单链表的头插具体操作步骤为：

1. 首先，创建一个新的节点，并将要插入的元素值赋给新节点的数据域。
2. 为了将新节点插入到链表中，需要将新节点的next指针指向链表的第一个节点，即原本的第一个节点。
3. 然后，将链表的头节点指向新节点，即将新节点设为链表的第一个节点。

我们来实现一下这个操作：

void SLPushFront(SLNode** phead, SLNDataType x)
{
	assert(phead);
	SLNode* newnode = CreateNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

单链表的头删具体操作步骤为：

1. 检查链表是否为空。如果链表为空，无法进行头删操作，直接返回。
2. 创建一个临时变量tmp，将其指向链表的第一个节点。
3. 将链表的头节点指针指向第一个节点的下一个节点，即tmp->next。
4. 释放temp指向的节点。

我们来实现一下这个操作：

void SLPopFront(SLNode** phead)
{
	assert(phead);
	assert(*phead);
	SLNode* tmp = (*phead)->next;
	free(*phead);
	*phead = tmp;
}

2.3单链表的任意位置插入和任意位置删除

单链表的任意位置插入和顺序表中的任意插入有所不同，在单链表中我们需要先编写一个链表数据元素的查找函数，然后输入一个节点值，接着返回相对应的节点，然后进行插入删除操作。链表数据元素查找函数实现如下：

SLNode* SLFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

我们创建一个单链表节点指针变量接收查找函数的返回信息。单链表的任意位置插入操作的具体步骤为：

1. 首先，判断要插入的位置是否合法，即判断插入的位置是否超出了链表的范围。如果超出了范围，则不进行插入操作。

2. 然后我们还要判断一下插入位置是否是在头节点，如果插入的位置是头节点，那我们直接调用头插的函数就行，反之，创建一个新结点，将要插入的数据放入在其中。

3. 遍历链表，找到插入位置的前一个节点，即要在其后面插入新节点。

4. 将新节点的指针域指向插入位置的前一个节点原来指向的节点。

5. 将插入位置的前一个节点的指针域指向新节点。

我们来实现一下这个操作：

void SLInsert(SLNode** phead, SLNode* pos, SLNDataType x)
{
	assert(phead);
	assert(pos);
	if (*phead == pos)
	{
		SLPushFront(phead, x);
	}
	else
	{
		SLNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

当然还是有人喜欢任意位置之后插入，我们也来实现一下：

void SLInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

讲完任意位置插入了，我们现在来整任意位置删除，任意位置删除的基本操作步骤为：

1. 首先判断单链表是否为空，若为空则无法进行删除操作，直接返回。
2. 如果要删除的位置是头节点，则将头节点指向下一个节点，并释放原来的头节点（头删操作）。
3. 如果要删除的位置不是头节点，需找到要删除节点的前一个节点。遍历单链表，找到要删除节点的前一个节点。可以使用两个指针prev和pos，prev指向要删除节点的前一个节点，pos指向要删除节点。当pos指向要删除节点时，prev指向的即为要删除节点的前一个节点。
4. 判断要删除节点是否存在，如果pos为空，则说明要删除的节点不存在，直接返回。
5. 将p的next指针指向q的next指针，即跳过要删除的节点。
6. 释放要删除节点q的内存空间。

我们来实现一下这个操作：

void SLErase(SLNode** phead, SLNode* pos)
{
	assert(phead);
	if (*phead == pos)
	{
		SLPopFront(phead);
	}
	else
	{
		SLNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

 到了这里应该知道我要干什么了吧，实现任意位置之后的删除：

void SLEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
	tmp = NULL;
}

2.4单链表的销毁

单链表的销毁指的是将整个链表都删除，回收其占用的内存空间。单链表的销毁的具体步骤为：

1. 首先需要定义一个指针变量，用于遍历链表。假设此变量为cur，并将其初始化为链表的头节点。
2. 创建一个临时指针变量，用于保存当前节点的下一个节点。假设此变量为next。
3. 使用循环遍历链表，直到cur指针变量为空。
4. 在循环中，将next指针变量指向cur指针变量的下一个节点。
5. 释放cur指针变量指向的节点的内存空间。可以使用free()函数来实现内存的释放。
6. 将cur指针变量指向next指针变量，即将cur指针变量移动到下一个节点上。
7. 重复步骤3-6，直到遍历完整个链表，即cur指针变量指向空。

当cur指针变量为空时，说明链表的所有节点都已经被删除，此时整个链表就被销毁了。我们来实现一下这个操作：

void SLDestory(SLNode** phead)
{
	assert(phead);
	SLNode* cur = *phead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;
}

在进行链表的销毁时要注意：我们需要确保链表中的每个节点都被释放，以避免内存泄漏。同时，需要注意释放节点内存空间前，需要先保存下一个节点的指针，否则在释放当前节点后，就无法访问到下一个节点了。

3.多文件实现单链表

SList.h文件：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLNDataType;
typedef struct SListNode 
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;
void SLprint(SLNode* phead);//链表打印
void SLPushBack(SLNode** phead, SLNDataType x);//链表的尾插
void SLPushFront(SLNode** phead, SLNDataType x);//链表的头插
void SLPopBack(SLNode** phead);//链表的尾删
void SLPopFront(SLNode** phead);//链表的头删
SLNode* SLFind(SLNode* phead, SLNDataType x);//链表的查找
void SLInsert(SLNode** phead, SLNode* pos, SLNDataType x);//链表的插入
void SLErase(SLNode** phead, SLNode* pos);//链表的删除
void SLInsertAfter(SLNode* pos, SLNDataType x);//后面插入
void SLEraseAfter(SLNode* pos);//后面删除
void SLDestory(SLNode** phead);//链表的销毁

SList.c文件：

#include"SList.h"
void SLprint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur!= NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
SLNode* CreateNode(SLNDataType* x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
void SLPushBack(SLNode** phead, SLNDataType x)
{
	assert(phead);
	SLNode* newnode=CreateNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		SLNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLPushFront(SLNode** phead, SLNDataType x)
{
	assert(phead);
	SLNode* newnode = CreateNode(x);
	newnode->next = *phead;
	*phead = newnode;
}
void SLPopBack(SLNode** phead)
{
	assert(phead);
	assert(*phead);
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* tail = *phead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
 
	}
}
void SLPopFront(SLNode** phead)
{
	assert(phead);
	assert(*phead);
	SLNode* tmp = (*phead)->next;
	free(*phead);
	*phead = tmp;
}
SLNode* SLFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SLInsert(SLNode** phead, SLNode* pos, SLNDataType x)
{
	assert(phead);
	assert(pos);
	if (*phead == pos)
	{
		SLPushFront(phead, x);
	}
	else
	{
		SLNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
void SLErase(SLNode** phead, SLNode* pos)
{
	assert(phead);
	if (*phead == pos)
	{
		SLPopFront(phead);
	}
	else
	{
		SLNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
void SLInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
	tmp = NULL;
}
void SLDestory(SLNode** phead)
{
	assert(phead);
	SLNode* cur = *phead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;
}

test.c文件（在这里测试函数功能）：

#include"SList.h"
void test()
{
	SLNode* plist = NULL;
	//测试尾插
	SLPushBack(&plist, 4);
	SLPushBack(&plist, 5);
	SLPushBack(&plist, 6);
	SLPushBack(&plist, 7);
	SLprint(plist);
	//测试头插
	SLPushFront(&plist, 3);
	SLPushFront(&plist, 2);
	SLPushFront(&plist, 1);
	SLPushFront(&plist, 0);
	SLprint(plist);
	//测试尾删
	SLPopBack(&plist);
	SLprint(plist);
	//测试头删
	SLPopFront(&plist);
	SLprint(plist);
	//测试任意插入
	SLNode* pos = SLFind(plist, 3);
	SLInsert(&plist, pos, 30);
	SLprint(plist);
	//测试任意删除
	pos = SLFind(plist, 30);
	SLErase(&plist, pos);
	SLprint(plist);
}
int main()
{
	test();
	return 0;
}

我们看看对各个函数测试结果：