[数据结构与算法]【数据结构初阶】单链表的实现

往前走，去闯。别灰心，继续闯。随缘，别后悔。

一、单链表与顺序表的相爱相杀

1.1 单链表的引入

单链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针依次连接而形成一段链表的

其实一句话就可以解决什么是单链表了，你把指针就想象成一根针线，我们通过这根针线将所有的结点全都串起来，这样就是我们的单链表了。

其实还有一种理解方式，这个理解方式是封清扬老师介绍的理解方式，就是无间道里面警员和上司的单独联络，这就很像我们的链表，我们可以想象，如果某一个结点的前一个结点消失了的话，还有人会记得这个结点吗？当然不会了，因为没有结点可以通过next指针找到我们pos位置的结点了。所以这个单链表缺陷也还是挺大的，也为我们后续的双向链表引出打下了基础。

1.2 单链表和顺序表的对比

我们上篇博客介绍了顺序表，我们现在分析一下顺序表的缺点，以便我们引出单链表
1.空间不够了我们需要增容，而且每次增容的空间大小也是固定的，即使我们用了动态顺序表，但其实也是会造成空间浪费的，因为你不能说每次开辟空间是之前的二倍，你就说自己开辟的空间大小合理吧？所以，顺序表结构所造成的空间浪费就是它比较大的缺点
2.顺序表要求数据在一段连续的物理空间中存放我们连续的数据，这样的结构模式也导致了我们如果想要在顺序表中插入或者删除数据时，是要付出代价的，因为我们需要挪动大量的数据给我们的操作数据留出空间
3.当然顺序表也是有优势的，正因为他的数据是连续存储的，所以我们直接通过下标就可以访问第i个元素，可以完成我们的随机访问。单链表是不能完成随机访问的，想要找到pos位置的结点，我们必须通过pos位置前面的结点来找到这个pos。

二、单链表的分类

2.1 单向或者双向

2.2 带头或者不带头

我们平常OJ中见到的都是不带头的单链表，所以我们下半个博客介绍的都是不带头的单链表，带头的单链表也被称为带有哨兵卫的单链表，这个大家了解一下就好了。

2.3 循环或者非循环

2.4 常用的链表结构

我们平常中较实用和常见的链表形式有两种，一种是无头单向非循环链表，另一种是带头双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多，因为它具有结构上的缺陷，更容易拿来考察。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了，这篇博客还是给大家着重介绍无头单向非循环链表。

三、单链表的实现

3.1 结点的动态申请，单链表打印，结构体的定义

//动态申请的内存是在堆空间上申请的
typedef int SLTDateType;

typedef struct SListNode//单链表结点
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

值得注意的是我们动态申请所占用的内存都是堆空间上所开辟的，而堆空间可是一块非常大的空间，像我们之前realloc开辟空间时，它要求连续的物理地址的空间么，所以一旦开辟空间字节数过大，很有可能就会出现开辟失败的情况，但我们的链表就不用担心这样的情况了，因为我们对空间是没有要求的，只要有那么小的一块儿空间存放我们的数据和指针就好了。毕竟指针和数据加起来也不过8字节（int和int*），当然不用考虑开辟空间失败的情况了

回到正题，所以我们的结构体定义中只需要一个存放数据的变量和变量类型的指针，就可以完成我们的结点定义了。

void SListPrint(SLTNode* phead)
{
	
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//这里一定要注意一点：在对结构体成员进行访问的时候，我们有两种方式，一种是结构体变量+点操作符，另一种是结构体变量指针->
	//这里要和指针区分开来，我们对结构体进行访问的时候，用的是成员选择操作符，对指针进行访问时，用的是解引用操作符
	//千万不要搞混了，分清成员选择和解引用这两种操作符

	printf("NULL\n");//每打印完一次链表我们就换一个行&&如果链表是空，正好我们打印NULL
}

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//1MB = 1024KB = 1024 * 1024 Byte
	//linux下栈有8MB,也就800多万字节，堆的字节数一般能上亿
	//32位系统，堆都有2G，大概是20几亿字节
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);//return结束的是当前这个函数，而exit终止的是整个程序
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

在介绍接口的实现之前，先给大家区分几个概念，我写代码的时候就遇到了这样的问题，所以为了避免大家踩坑，我还是说一下吧。
值得注意的是，我们对指针进行解引用时用到的叫做解引用操作符*，而对结构体变量中的成员进行访问时，用到的是成员选择操作符，我认为大家还是要把这两个官方的名字稍微记一下，以便我们对于两者的区分，成员选择操作符有两种，一种是结构体变量加点操作符，另一种是结构体指针加箭头操作符，这两种都可以访问我们的结构体成员，第二种操作需要先创建一个结构体指针，然后再通过指针进行对结构体成员的访问。

1.结点的动态申请： 值得注意的是，这里与顺序表中空间的申请还是有区别的，我们这里每次开辟空间的大小不单单要用来存储数据本身，我们还需要在存储数据的同时去存储指针，所以我们每次开辟空间的大小是一个结构体大小的空间，用来存放data和next
虽然这里基本不可能申请空间失败，但我们做一下分支判断还是比较好的，判断之后，我们就可以将这个结点进行赋值了，我们先将这个结构体中的next赋值为NULL，后面有需要再对其进行改变。
最后，我们的申请结点的这个接口应该返回我们申请空间的地址，这个地址其实也就是newnode，我们后续如果对链表进行增加结点的话，是需要新结点的地址的。

2.单链表打印： 单链表打印还是比较简单的，我们只需要一个cur指针先去接收一下我们的链表头地址plist，然后我们每次将这个cur赋值为cur中next的值，也就是下一个结点的地址，再赋值之前我们只要进行一下成员访问就可以拿到当前结点中data的值了，所以只需要一个while循环就可以解决单链表打印这个接口的实现了。当然如果传过来的plist是NULL的话，这就是个空链表，我们也应该对空链表进行打印，只要打印NULL即可。

3.接口参数的设计： 我们再设计参数之前其实应该想一下，这个接口功能是什么，如果想要实现这样的功能的话，应该需要什么样的参数，想清楚这些问题之后，我们函数参数和返回类型的设计也就浮出水面了。
比如打印接口，我们打印嘛，只需要直到头结点的地址就好了，只要知道这个地址，我就可以轻松的通过成员访问拿到所有结点中的data了，所以我们只需要一级指针的参数。
而申请结点的接口，也很简单，我们只需要data的类型就可以了，通过这样类型的变量来接收我们数据就可以了。

3.2 单链表的尾插，尾删（很重要的两个接口）

void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	创造一个新结点,在堆区上开辟一个大小为结点大小的动态空间
	//SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	注意我们malloc函数的返回值是开辟的空间的首地址，所以我们得用指针去接收
	//newnode->data = x;
	//newnode->next = NULL;
	//if (phead == NULL)
	//{
	//	phead = newnode;	
	//}
	//else
	//{
	//	//找到尾节点
	//	SLTNode* tail = phead;
	//	while (tail->next != NULL)
	//	//这里tail是空地址，我们通过空指针去进行成员访问，这就会引发了异常: 读取访问权限冲突。因为tail是nullptr。
	//	{
	//		tail = tail->next;
	//	}
	//	//最后一步，将我们的新结点链接到这个单链表上去
	//	tail->next = newnode;
	//}
	

	//上面的代码我们看起来其实是没有什么问题的，但为什么程序运行结果什么都没有呢？
	//这其实也就引出了一个问题，我们对形参phead进行的改变，没有影响实参plist
	 
	 
	//创造一个新结点,在堆区上开辟一个大小为结点大小的动态空间
	/*SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));*/
	//注意我们malloc函数的返回值是开辟的空间的首地址，所以我们得用指针去接收
	/*newnode->data = x;
	newnode->next = NULL;*/

	assert(pphead);
	SLTNode* newnode = BuyListNode(x);//我们SListPushBack会接收一个参数x，我们这里把参数x传给创造结点的函数BuyListNode
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾节点
		SLTNode* tail = *pphead;//要注意*pphead==phead==plist
		while (tail->next != NULL)
			//这里tail是空地址，我们通过空指针去进行成员访问，这就会引发了异常: 读取访问权限冲突。因为tail是nullptr。
		{
			tail = tail->next;
		}
		//最后一步，将我们的新结点链接到这个单链表上去
		tail->next = newnode;
	}
}

void SListPopBack(SLTNode** pphead)
{
	//正确写法
	assert(*pphead);//1.零个结点
	//2.一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;//将plist置为NULL
	}
	else
	{
		//3.两个及两个以上的结点
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;

		prev->next = NULL;//一个结点就会出问题（对空指针指向的位置进行了访问）

		//或者这样写也可以
		//SLTNode* tail = *pphead;
		//while (tail->next->next != NULL)//一个结点就会出问题（对空指针指向的位置进行了访问）
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;

	}


	/*SLTNode* tail = *pphead;
	SLTNode* prev = NULL;*///前驱指针,让我们的tail总是在prev的前面，让prev指向tail后边的结点
	//定义这个变量的原因就是，我们的tail在不断更新他指向的结点时，没人记得尾结点前面的结点了，
	//然而我们还需要让尾结点前面的结点中的next置空呢，但现在没人记得他了，所以我们需要一个prev指针
	//来替我们记住这倒数第二个的结点
	/*while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	tail = NULL;*/

	/*prev->next = NULL;*///只有一个结点的时候，我们的prev是NULL，对NULL进行访问那就是非法访问
	//这样的代码会导致经典的野指针问题出现
	//我们将tail所在空间释放掉之后，相当于前一个结点中的next所指向的空间被释放掉，这就导致了野指针的出现

	//那么我们在SListPrint里面打印的时候，就会进行非法访问因为倒数第二个结点中的next指向的是一个被释放的空间


	//另一种写法
	/*SLTNode* tail = *pphead;
	while (tail->next->next!=NULL)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;*/

	//值得注意的是这两种写法状态下，程序都崩了
	//当我们删一个结点的时候，这样的写法是有问题的
}

1.尾插接口的实现： 再这个接口当中涉及一个非常重要的问题，很有必要给大家讲一下，当时我就很蒙，希望大家不要踩坑。
首先我们来简单涉及一下这个接口参数的设计，我们先假设这个参数是一个一级指针，用来接受我们链表头结点的地址，然后我们继续分析这个接口的代码实现。
（1）我们先申请一个结点用于将这个结点尾插到我们的链表末端，利用我们的SListBuyNewnode实现这个步骤。
（2）我们还需要tail指针来作为遍历指针去找到这个链表末端结点，也就是next为NULL的那个结点，我们只需要tail->next一直等于到NULL就可以了，这样我们就找到了目标结点
（3）将我们的newnode链接到目标结点的后端，也就是tail->next=newnode，newnode->next=NULL，我们现在就分析完这个接口的实现了。

值得记住的是，如果我们在没有测试用例的情况下，想要知道我们的接口功能是否健全，最好用的一个分析方法就是，分析极端情况，其实就是边界检测，我们去测试边界情况下接口的功能是否完整可靠，这其实就可以很好分析接口是否有bug了。

其实我们现在的接口是不健全的，为什么呢？比如我们要在一个空链表的末端尾插一个结点，我们的接口还可以实现相应的功能吗？答案是不可以的，因为我们上来第一步就是tail->next以次来判断tail是否遍历到尾结点了，但如果是空指针的话，我们对空指针进行成员访问操作，这其实是很危险的操作，并且程序一定会挂掉，因为空指针本身什么就没有嘛，我们对NULL指向的内存块儿进行访问，这必然是会出问题的。

所以我们应该做一个分支，用if语句来分类这两种情况，当链表为空时，我们直接将我们申请的结点当作头结点就可以了，phead=newnode.做完这一个分支判断之后我们的接口功能就可以完美的实现了。

可是你看到这里之后，有没有什么疑问呢？其实如果你按照我们呢刚刚分析的步骤去写代码的话，你一运行其实就会发现，你的终端什么都没有，就好像你用了这个尾插接口之后，你的链表什么都没有一样，你一打印，终端只有醒目的NULL。

其实这个问题不易被发现，但也挺容易发现的，就是我们这里依然用了值传递，我们将头结点的地址做了一份临时拷贝，如果此时链表为空，我们将newnode的地址赋值给了这个拷贝值，可是这有用吗？这根本没有任何屁用，你来这里疯狂操作栈区上的局部变量，等到这个接口调用完之后，这些局部变量又全部被销毁了，外面的plist变都没变，该是NULL就还是NULL，有什么用啊？打印链表时你传的还是plist，所以活该你的终端什么都没有只有个NULL。
当然这样接口的参数设计也可以是临时拷贝值，但你必须得return pphead，因为你的局部变量终会被销毁，所以你只能通过返回值带回你的头结点地址pphead，但这样做其实是非常奇怪的，你说你就尾插个结点而已，调用了这个接口之后，这个接口还给你返回了个头结点的地址，这不是八竿子打不着么，我每次尾插一次，你都返回一个地址，我还得用这个新地址给原来的地址赋值，这不纯纯牛马操作么？这接口设计的还真是有点大病！
不过哈，我是说假如，如果你不对头结点做任何操作的话，理论上你是可以使用这种拷贝值来作为参数的，但可惜理想总是会败在事实面前，只要有这种可能的情况存在，你的接口就必须包含解决这种情况的功能，所以我们必须对接口的参数设计进行修改，将其修改为址传递，通过地址，我们就可以找到真正的plist，并且对其进行实实在在的修改。

好家伙，上面这一大堆废话，其实就是想给大家说清楚一个问题，我们此接口的参数应该设计为地址的传递，也就是利用二级指针作为函数参数接收传递值。

然后我们这个接口实现的核心思想倒是没有变，我们只需要将pphead解引用操作就可以拿到首结点的地址了，后续的操作我上面说过了，大家结合上面的分析以及我贴的代码，肯定能看懂，so，我相信你们能行。

2.尾删接口： 其实当我们在想到这个接口时，我觉得第一反应应该是有东西我才能删除吧，所以我们上来就应该assert检查结点是否为空，当然这个接口的参数也应该是二级指针，我们后面的接口实现，我就不再说参数设计这个问题了，大家自己进行分析就可以了，唯一判断的标准就是，只要你有可能对头结点进行改变，那么你的参数就应该设计为二级指针的形式。

判断结点不能为空之后，我们来正式分析一下到底应该怎样实现这个接口的功能。

如果要进行尾删，我们只要free掉尾结点的空间就好了，然后再将尾结点前面结点里的next置为NULL就OK了，这样就实现我们的尾删功能了，但是如果我们只有一个指针的话显然是完成不了这个任务的，那我们怎么完成呢？
（1）创建两个指针一个为先驱指针（tail），用于找到链表的尾结点，另一个指针为后驱指针（prev），用于修改我们尾结点之前那个结点，让那个结点变成尾结点。
（2）进行遍历，每次挪动tail之前，我们就把这个地址赋值给我们的prev，让我们的prev紧跟在tail屁股后面。
（3）进行释放空间，删除尾结点。

但是吧，你这样的接口又忽视了一个问题，我感觉友友们可能快要烦死了，哈哈哈，怎么一个接口的实现会出这么多bug啊，这链表到底能不能办啊？不能办就算了😡，哈哈哈，大家不要着急嘛，遇到bug不要心急嘛，慢慢耐心的修正他就好了，况且你不画图，不分析，不测试数据，这些检验的步骤你一点都不做，就说自己代码没问题，这谁相信啊，换一套测试数据，你的代码肯定又会出问题的，所以耐心一点，沉稳一点，踏踏实实的分析和解决问题，这才是制胜法宝！

言归正传，加入当我们的链表只有一个结点的时候，我们来走读一下，看看接口功能是否可以顺利实现，我们走读就会发现，接口有问题，我们的tail上来就是尾结点，然后我们释放掉这个结点的空间之后，在让prev指向的next置为空，这又出现相同的问题了，读取访问权限冲突，怎么办呢？当然是分支处理了。

我们将这一种特殊情况拿出来，单独进行处理，如果是一个结点的话，我们释放掉其空间之后，将这块儿空间地址进行置为NULL，这样我们的链表就变为空链表了。
具体代码实现请看我上面贴出来的，通过下方的代码结果实现我们就可以观察到，经过分析之后，我们的接口功能已经实现完整了。

3.3 单链表的头插，头删

void SListPushFront(SLTNode** pphead, SLTDateType x)//头插还是比较简单的，几句代码就搞定了
{
	assert(pphead);
//不要给这个函数传一个空指针过来，防止有些同学在写代码过程中不小心传了个空指针过来，这样我们就可以通过断言检查出我们传参
//出现了问题，帮助我们快速排查出问题
	SLTNode* newnode = BuyListNode(x);//将结点中的data改成我们预期值x
	newnode->next = *pphead;
	//如果链表刚开始是空链表的话，这里解引用只是找到了那个空指针，并没有对空指针解引用，所以是没问题的
	//将结点中的next改成我们的plist，因为plist是原链表的第一个结点的地址，我们把这个地址重新给到我们新开辟的结点中的next里
	*pphead = newnode;
	//我们重新将plist变为链表首结点的地址，首结点地址其实就是newnode
}

void SListPopFront(SLTNode** pphead)
{
	//assert(pphead);
	//如果只有一个结点的话，我们将第一个结点所在空间free掉之后，再将plist的指向改为空指针，以防别人用错plist
	//如果有两个及两个以上的结点的话，我们先释放掉plist的空间，因为plist现在指向的是第一个结点的空间
	//然后将plist的指向改为第一个结点中的next，这样我们的第一个结点就没有了
	//如果没有结点我们就将其进行断言处理，粗暴解决结点为0的情况
	assert(*pphead);
	
	SLTNode* next = (*pphead)->next;//->的运算符优先级要高于*解引用操作符的优先级
	free(*pphead);
	*pphead = next;
	//一个结点和多个结点的情况是一样的，这3条代码都可解决
}

1.头插接口实现： 我们的这两个接口实现是非常简单的，我就在这里给大家简单说一下其代码如何实现的思路就行，具体如何实现还是劳烦友友们好好看一下我贴出来的代码。
首先一如既往，我们还是得利用SListBuyNewnode接口进行一个结点的开辟，然后我们先把newnode中的next赋值为*pphead，其实就是让我们的newnode中的next指向现在头结点的地址，然后下一步，将我们的头结点地址改为newnode，这样我们的newnode就成功变成我们单链表的头结点了，名正言顺地加入了我们的单链表行列当中。
哈哈哈，简单到三句代码解决接口的实现。
2.头删接口实现： 我们要删除头结点的话，下一个结点的地址应该就是 *pphead的值，但如果我们先free掉头结点的话，就没有人能找到第二个结点的地址了，所以我们先用一个指针存储一下第二个结点的地址，然后再free掉首结点的空间，最后再将首结点重新赋值为我们的第二个结点的地址，成功的将第二个结点变为我们的单链表头结点。

3.4 单链表的查找

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	//如果没有找到，返回NULL
	return NULL;
}

查找接口的实现： 这个也很简单，我们遍历整个链表中的结点里头的data，比较data是否等于我的期望值，如果等于，直接返回此时结点的地址，如果不等于继续往下遍历，知道cur已经==NULL了，此时说明链表中没有我想查到的期望值，此时我们返回一个NULL即可。

下面就是我们查找接口的实现

3.5 单链表在pos之前插入，之后插入

//在pos的后面插入，这个更适合，也更简单
void SListInsertAfter(SLTNode*pos,SLTDateType x)//如果在pos位置的后面插入结点的话，我们根本不需要传头结点过来，只要有pos就可以
{
	assert(pos);//你在空结点后面插入，疯了？
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	
	if (*pphead == pos)
	{
		SLTNode* newnode = BuyListNode(x);
		newnode->next = *pphead;//newnode中的next指向的是刚刚的头结点地址，也就是*pphead
		*pphead = newnode;//让头结点变成newnode
	}
	else
	{
		//我们需要在pos位置的前面先插入一个结点
		SLTNode* newnode = BuyListNode(x);//创造结点的函数只需要一个data的参数和结点地址的返回类型
		//找到pos的前一个位置
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		//找到前一个位置之后，将新结点放入链表当中
		posprev->next = newnode;
		newnode->next = pos;
	}
	

}

1.pos位置之前插入： 在某个位置之前插入又会设计到一个问题，就是我们得知道pos之前那个位置的结点，因为如果在pos的前面插入必然要波及到pos前面的结点，而又因为我们链表是单向非循环的，所以我们又得需要一个posprev指针，这个posprev的next必须得是pos，如果找到的话，我们就让posprev的next指向我们的新结点地址，然后在让新结点的next指向我们的pos位置的结点。

分析到这里，我们又不得不考虑一个问题，如果这个链表中只有一个结点或是零个结点我们的接口又能否实现呢？如果是一个结点的话我们的pos位置之前插入就变成了之后插入了，因为posprev的next肯定不会等于pos，他压根就不会进入循环，直接进行链接结点的操作了。所以这种情况我们的接口功能出现了问题。如果是零个结点的话，我们对NULL进行成员访问操作又会造成读取访问权限冲突。所以这两种情况下，我们此时的接口都无法实现其功能。下面我们再分析一下，这两种情况的解决方式。

其实这个问题也很好解决，当我们pos==*pphead时，就能说明两种情况，一种是零结点一种是单个结点，但是解决的方法和我们的头插是一样的，只需要将newnode作为头结点，然后让newnode的next指向pos就可以，然后再让头结点的地址改为newnode就可以，就是两句代码的事。

if (*pphead==pos)
//将这里的判断条件改为pos和头结点地址是否相等的话，链表只有一个结点和为空这两种情况在一个if语句里都可以解决
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}

2.pos位置之后插入： 这个接口实现就比较简单了，我们只要将pos后面结点的地址给到newnode中的next就好，然后再让pos中的next指向我们的newnode就可以了。

这个接口对于尾插的情况也是合理的，我们让newnode中的next指向NULL，其实就是尾插的情况。

当然我们还需要assert（pos），pos肯定不能是空指针，我们在空指针后面插入一个结点，纯属疯了。

3.6 单链表在pos位置删除，之后删除

void SListErase(SLTNode** pphead, SLTNode* pos)//O(N)的算法
{
	assert(pphead);
	//如果要删中间和尾部的话，我们让pos的前一个结点next指向pos的下一个结点就好了，
	//但是要删头部的话，我们找不到pos的前一个结点了，所以这里要有一个分支结构
	if (*pphead == pos)
	{
		//删除头结点
		*pphead = pos->next;
		free(pos);//将头节点的空间内容给释放掉
		
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;//这句代码其实是没有意义的，因为你的pos只是外面实际pos结点地址的一个临时拷贝，修改形参并不会影响实参
		//但这句代码也可以体现出我们良好写代码的习惯
	}

	//所以我们的STL是实现SListEraseAfter,删除后面的结点的话就比较省事了

}
void SListEraseAfter(SLTNode* pos)
{
	assert(pos->next);//删空干毛线啊！	
	pos->next = pos->next->next;
	free(pos->next);
	pos->next = NULL;//置空不置空也是没有意义的
}

1.pos位置删除： 我们如果删除某一个位置那就得让pos位置之前的结点和pos位置之后的结点链接起来，那怎么实现呢？我们可以利用一个posprev指针，先让他遍历，直到他的next指向我们的pos时，遍历结束。然后我们让posprev的next指向pos的next，然后free掉pos的空间，这样就实现了我们的pos位置删除。

又来了，我们又得分析特殊情况了，喵的，我自己也说的烦了。你们肯定也看出来了吧。当删除位置是头结点的时候，我们的prev的next肯定不等于pos，所以while循环会一直停不下来，而且会造成内存访问权限冲突的问题，也就是对NULL进行成员访问。

所以还是老样子我们用一个分支结构来处理这个问题，如果删除的是头结点的话，我们直接将plist改为pos的next，然后free掉pos所在空间即可完成头删。

2.pos位置之后删除： 这个简单的要命，我们只要让pos的next指向pos的next的next，然后free掉pos的next即可。
当然使用这个接口的前提是你必须得知道，你删除的位置的后面得有结点才可以

最后这几个接口的功能测试：

3.7 单链表销毁

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

销毁接口： 我们在free某个结点之前先将这个结点后面的结点的地址用一个指针变量存放起来，然后再进行free，free掉之后，我们进行迭代，重复的进行free，知道遇到NULL为止

3.8 测试接口的代码（给友友们贴出来）

#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996) 

#include "SList.h"

void TestList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
}
void TestList2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 4);
	int i = 1;
	while (pos)
	{
		
		printf("第%d个结点:%p->%d\n", i++, pos, pos->data);
		pos->data = 40;
		pos = SListFind(pos->next, 4);//从pos后面的那个结点开始查找还有没有我目标的data的结点了
	}
	//我们既然能够找到，其实Find的另一个功能就是修改
	//我们现在把4修改为40
	SListPrint(plist);
	//我们现在在40的前面插入一个100
	pos = SListFind(plist, 40);
	SListInsert(&plist, pos, 100);
	pos = SListFind(pos->next, 40);
	SListInsert(&plist, pos, 100);
	SListPrint(plist);
}
void TestList3()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 3);
	SListEraseAfter(pos);
	SListErase(&plist, pos);
	SListPrint(plist);

	SListDestroy(&plist);

}
int main()
{
	TestList1();//测试过后,我们的头插，头删，尾插，尾删这些接口的功能就没有问题了
	//TestList2();//测试过后，我们的查找，任意位置插入，任意位置之后插入这些接口也没有问题了
	//TestList3();//测试过后，我们最后的任意位置删除元素接口也实现其功能了，到此我们的单链表也实现完了。
	return 0;
}

四、单链表总结（给看完的你点赞ヾ(≧▽≦*)o）

单链表总体来说还是要比顺序表难不少的，由于其中涉及到多次指针的问题，所以导致这部分难度偏大一点，其实大家只要自己多敲敲代码，自然而然就能领会到链表的魅力了。

其实吧，单链表也没啥好的，缺陷还是存在不少，例如它不能随机访问，所以这又为我们后面带头双向循环链表的引出埋下了伏笔，继续加油吧，接收更高级的知识，变成更好的自己，gogogo!😎😎😎