（c语言）详解单链表

 1：什么是单链表。

我们知道顺序表底层原理其实就是一块可以自由控制大小的数组，顺序表可以实现在任何地方进行插入一个数据，如果顺序表的缺点在于如果要在起始位置插入一个数据就要把后面的每一个数据都往后挪，这样会大量消耗我们的时间，单链表就很好的弥补到了这一点，因为他在内存中存储的形式的分散开来的，我要在哪里插入可以直接开辟一块空间然后把这个数据和下一个数据连接起来。

 如图所视，我们可以看到实际上每一个元素后面都跟了一个指针，这个指针就指向了下一个元素的地址，最后一个元素后面是空指针，利用这个原理我们就可以在任意位置进行插入了。

2：单链表的尾插

我们接下来就来讲解单链表如何实现插入一个数据，我们设想了一下，在进行插入的时候有两种情况，一种是链表里一个元素都没有，一种是里面有元素。我们先讲第一种，如果里面一个元素都没有那么就很简单，我们只需要开辟一个动态空间，然后把这个元素放进动态空间在把元素后面的地址置为空就完成了。那么第二种在里面有元素的情况下我们需要先对链表进行遍历找到为空指针的那个元素，然后把需要插入的地址赋给上一个空指针，然后把新开辟出来的元素后面地址置为空。讲到这里我们发现好像每一个区开辟一个空间都要写一段重复的代码，那么我们就可以直接封装成一个函数，返回构造出来的动态空间，每次需要就直接去调用它。

3:尾删

尾删尾删是同一种理念，我都需要先拿到最后那个元素的位置。那么不同的是，尾删有三种情况，一种就是如果链表里面一个元素都没有，那么就不需要我们去实现删除，如果有一个元素和有多个元素。一个元素都没有的话很好做，只需要对链表进行判断，如果为NULL我们就直接结束，如果有一个元素，我们也可以判断，如果这个元素指向下一个结点的指针为空我们就直接直接把这个结点free掉，如果有多个元素，我们就可以在定义一个指针，然后去遍历这个链表，当没有找到最后一个为空指针的时候就把重新定义的指针也往后跳，当找到了就直接free掉，然后把我们定义的这个指针置为空就好了。

4：头插，头删

头差相对于也是比较简单，我们只需要构建一个结点，然后把构建出来的这个结点指向原来的头元素，然后将构建出来的这个元素赋给原来的头元素。

我们在进行尾删的时候有三种情况，那么在头删的时候也有这几种情况。我们就简单一点只说当有多个元素的时候如何去删除。我们先保存第一个元素的位置，然后去找到第二个元素的位置，再将第一个元素的位置就完成了

 6：查找和修改

我们想查找完之后需要返回我们找到的那个元素的地址，如果需要修改可以直接用这个元素的地址对值进行修改，我们只需要去遍历链表，找到这个需要的数之后返回地址就好了

7：随机插入（删除）

随机插入我们只需要新建立一个节点，然后找到我们需要插入的位置，把需要插入的数和后一个链接就可以了

 随机删除同样，我们需要找到被删除元素的位置，然后让另一个元素指向被删除元素的下一个位置，然后让原来的结点去指向被删除的下一个结点就可以了

 8：代码实现

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SListDataType;
//节点
typedef struct SListNode
{
	SListDataType data;//第一个数据
	struct SLstNode* Next;	//指向下一个数据的指针
}SLTNode;

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

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

//头插
void SListPushFront(SLTNode** phead, SListDataType x);

//头删
void SListPopFront(SLTNode* phead);

//查找

SLTNode* SListFind(SLTNode* phead, SListDataType x);

//打印
void SListprint(SLTNode* phead);

//中间插入
void SListInsertAfter(SLTNode** phead, SListDataType seat, SListDataType x);

//随机删除
void SListEraseAfter(SLTNode* phead);



#include"SLsit.h"
//申请结点
SLTNode* BuySListNode(SListDataType x)	
{
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NewNode == NULL)
	{
		printf("申请结点失败\n");
		exit(-1);
	}
	NewNode->data = x; //data位置上放对应的数
	NewNode->Next = NULL; //将最后一个数后面的指针改变成空指针防止野指针指向不明确的指
	return NewNode;
}

//打印
void SListprint(SLTNode* phead)//指向最开始的地址
{
	SLTNode* cur = phead; //把初始指针赋值给另一个指针防止初始指针发生改变
	while (cur != NULL)
	{
		printf("%d->", cur->data); //打印data的数据
		cur = cur->Next;//使cur指向下一个地址
	}
	printf("NULL\n");
}

//尾插
void SListPushBack(SLTNode** pphead, SListDataType x)
{
	SLTNode* NewNode = BuySListNode(x);	//用另一个结构体指针来结构开辟的结点
	SLTNode* tail = *pphead; //本身是一个指针 对他解引用就找到了原来的那个指针
	if (*pphead == NULL)	//如果传过来的指针是一个空指针	
	{
		*pphead = NewNode;//就直接开辟一个结点把new出来的结点赋值 给他
	}
	else
	{
		while (tail->Next != NULL) //如果不是空指针
		{	
			tail = tail->Next;//遍历所有结点找到空指针
		}
		tail->Next = NewNode; //naex指向x x后面又被置为空指针
	}
	
}

//尾删
void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL) //结点为空
	{
		printf("当前结点暂无数据\n");
		return;
	}
	else if((*pphead)->Next==NULL)	 //一个结点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else	//一个结点以上
	{
		SLTNode* tail = *pphead;//用一个指针来记录最后一个位置
		SLTNode* prev = *pphead;	//另一个指针记录前一个位置
		while (tail->Next != NULL)//当他不为空的时候就继续
		{
			tail = tail->Next;//将下一个元素的地址给到tail
			if (tail->Next != NULL)
			{
				prev = prev->Next;//tail不为空的时候prev也跟着往后走
			}
		}
		free(tail);//找到了就释放掉
		prev->Next = NULL;//把前一个元素后面的指针置为空
	}
}


//头插
void SListPushFront(SLTNode** pphead, SListDataType x)
{
	SLTNode* newNode = BuySListNode(x);
	newNode->Next=*pphead;//把当前元素位置赋给构建出来的结点
	*pphead = newNode;//把构建出来的元素给到ppehad
}

//头删
void SListPopFront(SLTNode** pphead)
{
	SLTNode* newNode = *pphead;
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		*pphead = (*pphead)->Next;	//先把保存下一个位置
		free(newNode);//然后释放掉当前位置
	}
}

//查找
SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
	SLTNode* cur = phead;//先保存第一个元素的位置
	while (cur)
	{
		if (cur->data == x)
			return cur;//如果找到了返回这个数的地址
		cur = cur->Next; 
	}
	return NULL;
}

//随机插入
void SListInsertAfter(SLTNode** pphead, SListDataType seat, SListDataType x)
{
	SLTNode* newNode = BuySListNode(x);
	SLTNode* cur = *pphead;
	while (--seat)
	{
		cur = cur->Next;
	}
	newNode->Next = cur->Next;//让newNOde指向下一个元素
	cur->Next = newNode;//把newNode合并进去
}

//随机删除
void SListEraseAfter(SLTNode* pos)
{
		assert(pos);
	if (pos->Next)
	{
		SLTNode* next = pos->Next;	//让next指向需要删除得元素
		SLTNode* nextnext = next->Next;//nextnext指向删除得下一个元素
		pos->Next = nextnext;//pos指向被删除得下一个元素
		free(next);
	}
}



#pragma once
#include"SLsit.h"
SLTNode* pList = NULL;	
void TestSList1()
{
	SListPushBack(&pList, 1);//函数内部操作外部指把地址传过去
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListprint(pList);

	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListprint(pList);

	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);
	SListPushFront(&pList, 5);
	SListprint(pList);

	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListprint(pList);
}
void TestList2()
{
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);
	SListPushFront(&pList, 5);
	SListprint(pList);

	SLTNode* pos = SListFind(pList, 3);
	if (pos)
	{
		pos->data = 30;
	}
	SListprint(pList);
	SListInsertAfter(&pList, 1, 1);
	SListInsertAfter(&pList, 2, 2);
	SListInsertAfter(&pList, 3, 3);
	SListInsertAfter(&pList, 4, 4);
	SListprint(pList);

	SListEraseAfter(pList);
	SListprint(pList);
}
int main() 
{
	TestSList1();
	TestList2();
	free(pList);
	pList = NULL;
	return 0;
}