【数据结构功法】第4话 · 手把手拉着你入门单链表

写在前面

Hello珞大家好啊，我是kikokingzz，名字太长不好记，大家可以叫我kiko哦～本专栏的名字为【数据结构·水滴计划】，目的是通过百天刷题计划，通过题目和知识点串联的方式，完成对数据结构相关知识的全方位复习和巩固；同时还配有专门的笔记总结和文档教程哦！

欢迎订阅本专栏

博客主页：kikoking的江湖背景

往期必看

【数据结构功法】第3话 · 顺序表快速入门从今天开始，我将正式开启一个新的打卡专题——【数据结构·水滴计划】，没错！这是今年上半年的一整个系列计划！本专题目的是通过百天刷题计划，通过题目和知识点串联的方式，刷够1000道题！完成对数据结构相关知识的全方位复习和巩固；同时还配有专门的笔记总结和文档教程哦！想要搞定，搞透数据结构的同学，欢迎订阅本专栏！.....................https://kikoking.blog.csdn.net/article/details/123833759【数据结构功法】第2话 · 一篇文章带你彻底吃透·算法复杂度从今天开始，我将正式开启一个新的打卡专题——【数据结构·水滴计划】，没错！这是今年上半年的一整个系列计划！本专题目的是通过百天刷题计划，通过题目和知识点串联的方式，刷够1000道题！完成对数据结构相关知识的全方位复习和巩固；同时还配有专门的笔记总结和文档教程哦！想要搞定，搞透数据结构的同学，欢迎订阅本专栏！.........https://kikoking.blog.csdn.net/article/details/123681614

写在前面

知识点5：单链表

5.1 单链表的逻辑结构

5.2 单链表的存储结构

5.3 头指针与头结点

諾1. 头指针

諾2. 头结点

諾3. 头指针与头结点的关系

5.4 单链表的代码实现

（1）定义一个单链表结点 SListNode

（2）输出单链表（遍历单链表）SListPrint

（3）动态申请一个结点 BuySListNode

如何区分传二级指针还是一级指针？

（4）单链表尾插 SListPushBack

（5）单链表头插 SListPushFront

（6）单链表查找 SListFind

（7）指定pos位置前插入 SListInsertBefore

（8）指定pos位置后插入 SListInsertAfter

（9）单链表尾删 SListPopBack

（10）单链表头删 SListPopFront

（11）指定位置pos删除 SListErase

知识点5：单链表

5.1 单链表的逻辑结构

单链表的逻辑结构是线性表，换句话说就是单链表在逻辑上是线性结构的。
对于这句话，我们该如何理解呢？

单链表的逻辑结构与存储结构到底有什么关系呢？
对于上面这些问题，我们可以通过一个简单案例来进行分析，比如我们现在要将一串打乱的英文字母按字母顺序进行排列（c-d-a-b）。按照我们在第一话中提到的，“运算的定义是针对逻辑结构的，运算的实现是针对存储结构的”，因此我们先进行运算的定义。

运算的定义简单来说就是：你在脑海里打算怎么对这4个英文字母排序呢，总的来说就只有以下四种方法：

显然，最符合我们要求的排列方式就是线性结构。这种在脑海里构思的结构就是逻辑结构。

kiko：我们在了解完单链表的逻辑结构之后，就要开始了解单链表的存储结构啦！还是那句话“运算的定义是针对逻辑结构的，运算的实现是针对存储结构的”。接下来，我们将从运算的实现角度去分析单链表的存储结构。

5.2 单链表的存储结构

单链表的存储结构就是单链表本身；单链表是指通过一组任意的存储单元来存储线性表中的数据元素，为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。单链表结点结构如下图所示：

数据域：存储数据元素信息的域
指针域：存储直接后继元素位置的域

单链表就是依靠每个结点的指针域将线性表的数据元素按逻辑次序连接在一起

✨✨✨我是分割线✨✨✨

5.3 头指针与头结点

諾1. 头指针
我们通常用头指针来标识一个单链表，如下面的单链表L，头指针为NULL时表示一个空表。整个链表的存取从头指针开始，之后的每个结点的位置都是上一个结点后继指针指向的位置，最后一个结点指向“空”（通常用NULL或“^”来表示）。

諾2. 头结点
在单链表的第一个结点前再设置一个结点，称为头结点。头结点的数据域可以不存储任何信息，头结点的指针域指向第一个结点。

諾3. 头指针与头结点的关系
（1）头指针的特点：

头指针指的是指向链表第一个结点的指针，若链表具有头结点，则是指向头结点的指针。
头指针具有标识作用，所以通常用将链表的名字赋予头指针。
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

（2）头结点的特点：

头结点是为了操作的统一和方便而设立的，放在第一个数据元素结点之前，它的数据域一般无意义。
有了头结点，对在第一数据元素结点前插入结点和删除第一结点的操作就与其他结点的操作统一了。
头结点不一定是链表的必要元素。

kiko：在了解完单链表相关的概念内容后，接下来我们就开始着手写一个单链表。

5.4 单链表的代码实现
（1）定义一个单链表结点 SListNode
单链表是由一个一个结点通过指针链接组成的，因此我们创建单链表的第一步就要先创建一个结点，这个结点由于包括了数据域和指针域这两种不同的数据类型，因此我们要使用结构体类型进行定义。我们具体定义了数据域data以及指向下一个结点的指针*next。
typedef int DataType; //将int重命名为DataType

typedef struct SListNode {
	DataType data; //数据域，存放DataType型数据
	struct SListNode* next; //指向下一个结点的指针
                            //指针指向的类型是struct SListNode这个结点
}SListNode,SList; //用SListNode和SListNode来代替这个结构体
（2）输出单链表（遍历单链表）SListPrint
由于单链表并不像顺序表那样在内存中连续存放，单链表中的元素离散地分布在内存空间中，不能直接找到某个特定结点，因此在输出单链表时，需要从表头开始遍历，从第一个元素开始依次向后打印输出。
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead; //用cur保存头指针的值
	while (cur != NULL) //只要cur不为空就一直向后遍历
	{
		printf("%d->",cur->data); //打印当前指向结点的数据域
		cur = cur->next; //将该结构体的指针域的值赋给指针
						 //相当于让cur指向后一个结点
	}
	printf("NULLn"); //最后一个结点指向NULL
}
（3）动态申请一个结点 BuySListNode
由于之后对单链表进行的插入操作都需要新建一个结点，为了日后的方便，所以特地写成了一个函数模块，后续可以直接调用该函数进行新结点的申请操作。
SListNode* BuySListNode(DataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); //为新节点动态申请一个空间
	if (newnode == NULL) 
	{
		printf("malloc failn"); //如果新空间为空，则表明动态申请失败
		exit(-1);
	}
	else
	{
		newnode->data = x;    //新结点的数据域存放元素x
		newnode->next = NULL; //新结点的指针域指向NULL
	}
	return newnode;           //返回类型是一个指向SLitNode类型的结构体指针
}
如何区分传二级指针还是一级指针？
1、改变量的值——>用变量的指针的来接收

如果要更改传入变量的值，此时我们需要传变量的指针。举个例子来说，当我们将两个int型变量a和b传给swap函数，a和b的值可能会按需求发生更改，即传入变量的值会修改，此时我们就需要传变量的地址，swap函数要用变量的指针来接收。
void swap(int* x, int* y); //改变量的值——>用变量的指针来接收
 
int main()
{
	int a = 1;
	int b = 2;
	swap(&a, &b);
}
2、改指针的值——>用指针的指针来接收（用二级指针接收）

此时我们可以做一个类比，假如此时我们传入的是指针，这个指针可能也会按需求发生改变，即传入的指针的值会发生修改，此时我们就需要传指针的地址，此时的函数就需要用二级指针来负责接收。
void swap(int** x, int** y); //改变int* 变量的值 ————>传int**
 
int main()
{
	int* a;
	int* b;
	swap(&a, &b);
}
之所以特别讲这一点，是因为在单链表的创建过程中，特别是针对无头结点的单链表，头指针的值会发生改变，此时对于单链表进行“增删改查”时需要注意，对应的操作函数需要用二级指针来接收单链表的头指针地址。
（4）单链表尾插 SListPushBack
此处我们写的是无头结点的单链表，因此这时我们就需要考虑，链表的头指针可能指向空的情况，当链表为空链表时，头指针指向NULL；当链表非空时，头指针指向链表的第一个结点。因此可见，链表的头指针在不同情况下可能会产生值的变化，即我们可能会改变传入指针自身的值，因此需要传入二级指针。
void SListPushBack(SListNode** pphead, DataType x)
{
    assert(pphead);
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)   //如果是空链表，即头指针指向NULL时
	{
		*pphead = newnode; //头指针直接指向新结点即可
	}
	else //如果不是空链表，即头指针指向的不是NULL时
	{
		SListNode* tail = *pphead; //用一个指向空链表的结点的指针tail指向表头元素
		while (tail->next != NULL) //让tail去找尾
		{
			tail = tail->next;
		}
		tail->next = newnode;      //将最后一个元素指向newnode即完成了尾插操作
	} 
}
（5）单链表头插 SListPushFront
头插的情况相比尾插就稍微简单一些，因为头插是在原单链表的第一个结点前进行插入，即每插入一个结点，都需要改变一次头指针的值，因此依然要使用二级指针来接收头指针的地址，进而使用解引用操作来修改头指针的值。
void SListPushFront(SListNode** pphead, DataType x)
{
	SListNode* newnode = BuySListNode(x); //Buy一个新结点
	newnode->next = *pphead; //将新结点的next指向原来头指针指向的结点（可能指向空）
	*pphead = newnode; //将头指针指向新结点
}
（6）单链表查找 SListFind
单链表查找是一个查找元素的过程，在这一操作中并不会发生修改单链表头指针的行为，因此这时我们并不需要再使用二级指针来接收单链表的头指针地址了，可以直接用一级指针来接收单链表的头指针。
SListNode* SListFind(SListNode* phead, DataType x)
{
	SListNode* cur = phead; //定义一个指向单链表结点类型的指针cur，使其指向单链表头指针指向的位置
	while (cur != NULL) //只要cur不为空，就一直循环查找
	{
		if (cur->data == x) //如果找到了元素x，则返回cur指针
			return cur;
		else
			cur = cur->next; //如果该结点的数据域不是所查元素，就向后查找
	}
	return NULL; //如果cur一直遍历到NULL还没查找到，就会执行这条语句，返会一个NULL
}
这里的查找操作除了具有查找的功能外，还是为了配合之后在指定位置插入删除元素的操作。
（7）指定pos位置前插入 SListInsertBefore
这里的操作涉及到了找到一个指定位置的前一个结点，并在这个pos前插入一个结点的操作。由于涉及到链表的插入，因此可能会修改链表的头指针的值，因此需要使用二级指针来接收链表的头指针的地址；其次需要对pos和pphead的值进行判断，只有二者非空时，才有继续讨论的必要。
void SListInsertBefore(SListNode** pphead, SListNode* pos, DataType x)//在pos位置前面插入
{
	assert(pphead); //断言一下防止pphead为空指针
	assert(pos);    //断言一下防止pos为空指针
	if (pos == *pphead) //1、pos是第一个结点
	{
		SListPushFront(pphead, x); //直接使用头插程序
	}
	else //2、pos不是第一个结点
	{
		SListNode* prev = *pphead; //定义一个prev指针
		while (prev->next != pos)  //prev指针循环向后遍历到pos的前一个位置
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x); //buy一个新结点
		prev->next = newnode;     //将prev指向新结点
		newnode->next = pos;      //将新结点指向pos
	}
}
（8）指定pos位置后插入 SListInsertAfter
在pos位置后面插入一个结点的操作就比pos前插入要简单一些，这是因为我们不再需要去遍历这个单链表去找pos的前一个结点，而是可以直接得到pos的位置，直接在pos后进行插入结点的操作。
void SListInsertAfter(SListNode** pphead, SListNode* pos, DataType x)//在pos位置后面插入
{
	assert(pphead);
	assert(pos);
	SListNode* newnode = BuySListNode(x); //buy一个新结点
	newnode->next = pos->next; //将新结点指向pos的后一个结点
	pos->next = newnode; //将pos指向新结点
}
（9）单链表尾删 SListPopBack
单链表进行尾删操作时，我们需要考虑三种情况：头指针为空、只有一个结点、有多个结点；由于删除操作当删光时，单链表的头指针的值会修改为NULL，即删除操作会有可能修改头指针的值，因此我们要使用二级指针来接收单链表的头指针地址。
void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	SListNode* tail = *pphead;
	//assert(*pphead != NULL); assert属于暴力检查，有问题直接中止弹出警告
	if (*pphead == NULL) //温和检查，当链表为空时，什么操作都不做
		return;
	else if (tail->next == NULL) //当链表只有一个结点时
	{
		free(*pphead); //释放唯一那个结点的空间
		*pphead = NULL; //将头指针指向NULL
	}
	else
	{
		while (tail->next->next != NULL) //找倒数第二个结点
		{
			tail = tail->next;
		}
		free(tail->next); //释放倒数第二个结点指向的后一个结点的空间（尾删）
		tail->next = NULL; //将倒数第二个结点指向NULL
	}
}
（10）单链表头删 SListPopFront
单链表头删比尾删简单一些，只需要考虑两种情况：链表为空、链表非空。由于头删同样涉及到头指针值的修改，因此仍然使用二级指针进行接收。
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL) //如果链表为空，不做任何操作
		return;
	else //当链表非空时
	{
		SListNode* head = *pphead; //用head指向链表的第一个结点
		*pphead = (*pphead)->next; //头指针指向第一个结点指向的位置，即指向第二个结点orNULL
		free(head); //释放第一个结点的空间
	}
}
（11）指定位置pos删除 SListErase
指定位置pos删除，我们需要找到pos的前一个结点，将pos的前一个结点与pos的后一个结点通过指针域连接起来；由于这里的指定位置删除也有可能会导致头指针值的变化，因此也要使用二级指针来接收单链表头指针的地址。
void SListErase(SListNode** pphead, SListNode* pos)//删除指定的pos位置
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos) //当pos是第一个结点时
	{
		SListPopFront(pphead); //直接调用头删
	}
	else //当pos不是第一个结点时
	{
		SListNode* prev = *pphead; //定义一个prev向后遍历
		while (prev->next != pos) //prev向后遍历到pos前一个结点的位置
		{
			prev = prev->next;
		}
		prev->next = pos->next; //prev指向pos指向的位置
		free(pos);  //释放pos指向的结点空间
		pos = NULL; //将指针pos的指向置空
	}
}

【数据结构功法】第4话 · 手把手拉着你入门单链表

5.3 头指针与头结点

諾2. 头结点
在单链表的第一个结点前再设置一个结点，称为头结点。头结点的数据域可以不存储任何信息，头结点的指针域指向第一个结点。

5.4 单链表的代码实现

Java相关栏目本月热门文章

【数据结构功法】第4话 · 手把手拉着你入门单链表

5.3 头指针与头结点

諾2. 头结点 在单链表的第一个结点前再设置一个结点，称为头结点。头结点的数据域可以不存储任何信息，头结点的指针域指向第一个结点。 ​

5.4 单链表的代码实现

Java相关栏目本月热门文章

諾2. 头结点
在单链表的第一个结点前再设置一个结点，称为头结点。头结点的数据域可以不存储任何信息，头结点的指针域指向第一个结点。