今天小胡杨手绘28张图只为教会你单链表

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

欢迎光临

个人主页：欢迎大家光临——>沙漠下的胡杨

各位大帅哥，大漂亮

如果觉得文章对自己有帮助

可以一键三连支持博主

你的每一分关心都是我坚持的动力

☄：本期重点：数据结构篇单链表实现

希望大家每天都心情愉悦的学习工作。

学数据结构，先学画图，本期和小胡杨一起开始绘画之旅吧！

什么是单链表呢？

链表的实际地址的存放

创建链表

申请结点

链表的尾插

链表的头插

链表的头删：

链表的尾删

查找链表元素：

修改链表元素

在链表任意位置后插

在链表任意位置前插

在链表任意位置后删

删除链表的任意位置

链表的打印

链表空间释放

关于整体的代码头文件篇：

关于整体代码源文件：

什么是单链表呢？

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

类似于向一条链串联起来的一样。

链表的实际地址的存放

链表我们一般的图示为下面的样子：

实际上我们要看链表的实际地址存放：

代码如下：
	SLTNode* d1 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(d1);
	SLTNode* d2 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(d2);
	SLTNode* d3 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(d3);

	d1->data = 1;
	d2->data = 2;
	d3->data = 3;
	

	d1->next = d2;
	d2->next = d3;
	d3->next = NULL;
	
	SListPrint(d1);
这是单链表的实际存放的地址

创建链表

首先我们要先创建链表，用结构体创建这就不在多说啦，关于这个头文件定义结构体细节处理都在代码中了。结构体有不明白的请移步☞结构体详解
#pragma once//防止头文件重复包含

#define  _CRT_SECURE_NO_WARNINGS//防止scanf函数报错

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//断言头文件

typedef int SLTDataType;//把int重命名

typedef struct SListNode//结构体重命名
{
	SLTDataType data;
	struct SListNode *next;//这个不可以使用重命名后的名字
}SLTNode;

申请结点

我们有链表了，但是我们还没有链表的组成成员呀！所以我们要申请结点，什么时候需要申请结点呢？那肯定是选择插入就会需要结点啊，所以我们不妨写函数是就直接申请结点，并附上数据，指针我们可以默认指向为NULL。

看下代码：
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode *)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;

	return newnode;
}
我们可以直接要把要赋给的值传给函数，然后开辟一个结点的空间，进行断言，判断是否申请到了空间，接着把要赋给的值给data，把结点指针的指向NULL。

链表的尾插

首先我们先想一下传什么参数呢？

首先是要插入的值，那么是传链表的地址，还是直接传链表呢？如果链表为NULL呢？

我们先看一个示意图：

我们已经有啦一个结点，并且已经放好值了，那么怎么操作呢？我们只需要把d3中的next的NULL指向新开辟的结点，是不是就可以啦！接着看图：

变为这个样子就可以啦。（最重要的是plist没有改变）

可是如果我们的链表没有元素呢？接着看图：

此时的plist是为NULL，那我们直接吧plist指向 d 的地址就好呀，并且只有一个 d 刚好d的下一个结点为NULL。（注意：plist已经由空指针变为了指向新节点 d 了）

看下代码（很多人都会错误的示范）：
void SListPushBack(SLTNode *pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (pphead == NULL)
	{
		pphead = newnode;
	}
	else
	{
		SLTNode* cur = pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
这样写的话有没有一点点的不妥呢？

我们调试下，发现plist没有变，链表没有插入，接着看图：

我们得出了一个结论：

不是传指针，就可以改变这个指针的指向的，我们应该传二级指针的形式，然后解引用，达到改变plist地址的效果，所以我们链表所有的插入和删除函数都传二级指针，传二级指针时，我们使用头结点只要解引用就好了。

所以正确的代码为：
void SListPushBack(SLTNode **pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
其他的都没有改变，只是把用链表头的地方，改为解引用链表头。

链表的头插

头插我们依然要考虑这个问题就是 plist 是否改变呢？

这是肯定的，头插就是换个头呀！就是链表的头被改变了，所以我们要传地址。

我们接着看个图来理解下：

这是刚开始的情况，我们要把 plist 的地址放入新结点，并且把plist改为新结点的地址。

下面我们接着看图示：

我们是没有plist，但是我们有 pphead，直接解引用就是头结点。

需要注意的点：

必须要先进行步骤一，再进行步骤二，否则，我们的头结点就被覆盖了，然后就找不到以后的节点啦，所以我们一定要先执行步骤一，在执行步骤二。

下图是先执行步骤二，在执行步骤一的后果（死循环）：

下面是正确的代码：
void SListPushFrond(SLTNode **pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

链表的头删：

链表的头删很简单，我们还是传递二级指针，因为如果就一个结点，删除后变为了NULL，此时链表的指向还是发生了变换。

看下面图示：

我们只需要把原来头结点的指向第二个结点，然后把原来头结点free掉就可以啦。

需要注意的是：

我们要先创建一个结点指针，保存第二个结点的地址

然后我们要释放原来的头指针（*pphead）

接着把保存第二个结点的地址赋值给 *pphead，让它成为新的链表的头指针。

如果刚好是一个结点，也是可以的，因为*pphead的下个结点为NULL

我们先把NULL存起来，然后把 *pphead 这个结点 free掉

再把NULL放到*pphead中，就变为NULL了，符合条件。

下面是代码：
void SListPopFrond(SLTNode **pphead)
{
	assert(pphead);
	
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

链表的尾删

链表的尾删我们要考虑的就要多点，如果有一个结点，和有多个结点分开分析

还是先看图：

如果是这种情况，就直接free掉，然后置为NULL就好了。

这种情况就要把d3这个结点 free掉，然后把 d2 结点的指向NULL就好了。

那我们怎么找到 d2 呢？接着看图：

这就是我们写代码的实际逻辑啦，下面是代码，代码中的注释部分是第二种办法，通过访问两次下一个指针的指向：
void SListPopBack(SLTNode **pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//SLTNode *cur = *pphead;
		//while (cur->next->next != NULL)
		//{
		//	cur = cur->next;
		//}
		//free(cur->next);
		//cur->next = NULL;
		SLTNode *tail = *pphead;
		SLTNode *tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;//失误三
			tail = tail->next;
		}
		free(tail);
		tailprev->next = NULL;
	}
}

查找链表元素：

查找就很简单了，我们直接暴力查找就好啦：

看下代码：
SLTNode* SListFind(SLTNode *pphead, SLTDataType x)
{
	SLTNode* cur = pphead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}
需要注意的地方：

首先，我们要先保存头指针，不要改变头指针。

其次，我们要考虑代码的健壮性，并且配合其他的函数接口使用，所以我们返回值设定为结点指针。如果找不到，我们就返回NULL。

修改链表元素

修改就可以配合查找一起使用也很简单，直接看代码吧：

我们可以通过查找到的下标，进行修改，没啥说的。
void SListModify(SLTNode *pos, SLTDataType x)
{
	assert(pos);

	pos->data = x;
}

在链表任意位置后插

在链表任意位置后插入，首先我们应该找该位置，然后进行插入。

先看图：

这个插入位置我们已知，然后我们只需要改变指向就可以啦，接着看图：

我们要注意的是先进行步骤一，在进行步骤二，顺序一定不能反，否则就和头插一样死循环了。

下面是具体的代码：
void SListInsertAfter(SLTNode *pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);//注意下面代码的位置
	newnode->next = pos->next;
	pos->next = newnode;
}

在链表任意位置前插

在链表任意位置后插，这个比较复杂啦。下面看图一点点的分析：

首先如果只有一个结点，那就相当于头插了

和头插一样，不在赘述啦~

如果有多个结点，就复杂啦~ 我们先看图吧：

我们怎么知道这个位置前一个的结点值呢？方法其实和尾删一样，使用一个变量遍历，循环结束的条件变为 p1->next != 这个位置。

看下图：

最后看下代码：
void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{
	assert(pos);

	if (pos == *pphead)
	{
		SListPushFrond(pphead, x);
	}
	else
	{
		SLTNode *prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prve->next = newnode;
	}
}

在链表任意位置后删

删除任意位置比较简单，我们只需要注意一点，

就是链表元素为1时，就没有后续啦，就不能删除啦。

还是看下图吧：

只有一个结点，不能删除后面的元素，其他的，直接覆盖，然后free掉pos位置的结点

我们直接看代码吧：
void SListEraseAfter(SLTNode *pos)
{
	assert(pos);
	SLTNode *next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

删除链表的任意位置

这个又点麻烦，我们一点点分析：

首先如果这个位置在链表的头上，那么我们就是头删，

还是看图：

如果在其他位置删除，和任意位置前插一样，我们要创建一个指针结点，进行遍历，循环结束的条件是 p1->next != pos,然后把断裂的链表链接就好啦。

接着看图吧：

下面是代码：
void SListErase(SLTNode **pphead, SLTNode *pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFrond(pphead);
	}
	else
	{
		SLTNode *prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

链表的打印

打印可以不用传链表地址，我们不会修改链表内容，还有一点就是创建临时变量来遍历。

看代码吧：
void SListPrint(SLTNode* pphead)
{
	SLTNode* cur = pphead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

链表空间释放

这个没说的，还是要传链表的地址，因为我们要把链表置为NULL

直接看代码吧：
void SListDestroy(SLTNode **pphead)
{
	assert(pphead);

	SLTNode *cur = *pphead;
	while (cur)
	{
		SLTNode *next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

关于整体的代码头文件篇：

#pragma once

#define  _CRT_SECURE_NO_WARNINGS

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

typedef int SLTDataType;

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

void SListPrint(SLTNode* pphead);//打印

SLTNode* BuySListNode(SLTDataType x);//申请新节点

void SListPushBack(SLTNode **pphead, SLTDataType x);//尾插

void SListPushFrond(SLTNode **pphead, SLTDataType x);//头插

void SListPopFrond(SLTNode **pphead);//头删

void SListPopBack(SLTNode **pphead);//尾删

SLTNode* SListFind(SLTNode *pphead, SLTDataType x);//查找

void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x);//任意位置前插

void SListInsertAfter(SLTNode *pos, SLTDataType x);//任意位置后插

void SListErase(SLTNode **pphead, SLTNode *pos);//删除任意位置

void SListEraseAfter(SLTNode *pos);//任意位置后删

void SListDestroy(SLTNode **pphead);//释放链表

void SListModify(SLTNode *pos, SLTDataType x);//修改链表

关于整体代码源文件：

#include "SList.h"

void SListPrint(SLTNode* pphead)
{
	SLTNode* cur = pphead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode *)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;

	return newnode;
}


void SListPushBack(SLTNode **pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

void SListPushFrond(SLTNode **pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopBack(SLTNode **pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//方法二
		//SLTNode *cur = *pphead;
		//while (cur->next->next != NULL)
		//{
		//	cur = cur->next;
		//}
		//free(cur->next);
		//cur->next = NULL;
		SLTNode *tail = *pphead;
		SLTNode *tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;
		}
		free(tail);
		tailprev->next = NULL;
	}
}


void SListPopFrond(SLTNode **pphead)
{
	assert(pphead);
	
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}


SLTNode* SListFind(SLTNode *pphead, SLTDataType x)
{
	SLTNode* cur = pphead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

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

	if (pos == *pphead)
	{
		SListPushFrond(pphead, x);
	}
	else
	{
		SLTNode *prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prve->next = newnode;
	}
}

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

	SLTNode* newnode = BuySListNode(x);//注意下面代码的位置
	newnode->next = pos->next;
	pos->next = newnode;
}

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

	if (*pphead == pos)
	{
		SListPopFrond(pphead);
	}
	else
	{
		SLTNode *prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SListEraseAfter(SLTNode *pos)
{
	assert(pos);
	SLTNode *next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

void SListDestroy(SLTNode **pphead)
{
	assert(pphead);

	SLTNode *cur = *pphead;
	while (cur)
	{
		SLTNode *next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

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

	pos->data = x;
}

———————————————————————————————————————————