数据结构初阶之单链表

//单链表的结构
typedef int SLDataType;
typedef struct ListNode
{
	SLDataType a;   //保存的数据
	struct ListNode* next;  //储存的下一个节点地址的指针
}SL;

//单链表的初始化
void SLInit(SL** sl);
//单链表的尾部插入数据
void SLBackPush(SL** sl,SLDataType x);
//单链表的头部插入数据
void SLFrontPush(SL** sl, SLDataType x);
//单链表尾部数据的删除
void SLBackDel(SL** sl);
//单链表头部数据的删除
void SLFrontDel(SL** sl);
//单链表数据的查找
SL* SLFindData(SL** sl, SLDataType x);
//单链表指定位置前的插入数据
void SLPosiFrontPush(SL** sl, SL* pos, SLDataType x);
//单链表指定位置之后的插入数据
void SLPosiBackPush(SL** sl, SL* pos, SLDataType x);
//单链表指定位置的数据删除
void SLPosiDel(SL** sl, SL* pos);
//单链表的销毁
void SLDestroy(SL** sl);

	SL* sl;//先创建一个结构体指针，准备用来接收第一个节点的地址
	//因为 sl的地址是需要存第一个节点的地址，会被改变，所以我们传的是sl指针的地址
	SLInit(&sl);

//单链表的初始化
void SLInit(SL** sl)
{
	//把头节点先置为空
	*sl = NULL;
}

//单链表的尾部插入数据
void SLBackPush(SL** sl, SLDataType x)
{
	//如果收节点是空的说明是第一次放入数据
	if (*sl == NULL)
	{
		SL* tem = (SL*)malloc(sizeof(SL));
		if (tem == NULL)
		{
			perror("malloc");
			exit(1);
		}
		*sl = tem;
		(*sl)->a = x;
		(*sl)->next = NULL;
	}
	//如果不是第一次放入数据，则把要放入的数据放到最后
	else
	{
		//先要找到尾结点
		SL* cur = *sl;
		while (cur->next)
		{
			cur = cur->next;
		}
		//开辟节点，并放入数据到新的节点中去
		SL* tem = (SL*)malloc(sizeof(SL));
		if (tem == NULL)
		{
			perror("malloc");
			exit(2);
		}
		tem->a = x;
		tem->next = NULL;
		//把新的节点和单链表连接起来
		cur->next = tem;
	}
}

//单链表的头部插入数据
void SLFrontPush(SL** sl, SLDataType x)
{
	//和尾插一样先判断单链表是否为空，如果为空就和尾插的实现一样
	if (*sl == NULL)
	{
		SL* tem = (SL*)malloc(sizeof(SL));
		if (tem == NULL)
		{
			perror("malloc");
			exit(1);
		}
		*sl = tem;
		(*sl)->a = x;
		(*sl)->next = NULL;
	}
	else
	{
		//单链表中原本就有数据来实现头插
		SL* tem = (SL*)malloc(sizeof(SL));
		if (tem == NULL)
		{
			perror("malloc");
			exit(1);
		}
		//先把数据放到这个新的节点中
		tem->a = x;
		//在用这个节点作为新的头节点连接上一个头节点
		tem->next = *sl;
		//接下来把原来的头节点换成 tem (新的头节点)；
		*sl = tem;
	}
}

单链表尾部数据的删除（尾删），请先看原理图，在实现代码：

//单链表尾部数据的删除
void SLBackDel(SL** sl)
{
	//要实现尾部数据的删除现需要判断单链表里面是否有数据才可以实现删除
	//所以先需要断言一下,单链表不为空,如果单链表为空，则不能实现数据的删除
	assert(*sl);
	//尾部数据的删除，需要先找到尾部数据在实现删除即可
	SL* cur = *sl;
	while (cur->next->next)
	{
		cur = cur->next;
	}
	SL* del = cur->next;
	cur->next = NULL;
	free(del);
	del = NULL;
}

单链表头部数据的删除(头删)：

//单链表头部数据的删除
void SLFrontDel(SL** sl)
{
	//和尾删一样需要先判断单链表中是否有数据才可以实现头删
	//先断言一下，看单链表是否为空
	assert(*sl);
	//先保存准备删除的头节点
	SL* cur = *sl;
	//然后让头节点连接后面的元素从而实现头删
	*sl = (*sl)->next;
	//在释放掉以前的头节点即已经完成头删
	free(cur);
	cur = NULL;
}

有了单链表数据的查找，才能实现后面的单链表特定位置数据的插入和删除，因为这个函数返回的指针就是特定位置的地址：

//单链表数据的查找
SL* SLFindData(SL** sl, SLDataType x)
{
	SL* cur = *sl;
	//遍历单链表找到这个数据
	//如果没找到特定的数据就返回空指针
	while (cur->a != x && cur != NULL)
	{
		cur = cur->next;
	}
	//此时的cur指针指向的就是数据的指定节点位置
	//直接返回这个节点的地址即可
	return cur;
}

//单链表指定位置前的插入数据
void SLPosiFrontPush(SL** sl, SL* pos, SLDataType x)
{
	//指定位置的插入数据必须链表不为空，如果为空就不能实现特定位置的数据插入
	//所以需要断言链表不为空
	assert(*sl);
	assert(pos);
	//找到pos之前的地址
	SL* cur = *sl;
	while (cur->next != pos)
	{
		cur = cur->next;
	}
	//再实现数据的插入
	SL* ins = (SL*)malloc(sizeof(SL));
	if (ins == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//先把数据放大这个新开辟的空间中
	ins->a = x;
	//再把节点连接起来就可以完成
	cur->next = ins;
	ins->next = pos;
}

特定数据位置之后的数据插入，先看原理图再来实现代码：

//单链表指定位置之后的插入数据
void SLPosiBackPush(SL** sl, SL* pos, SLDataType x)
{
	//先得判断链表不为空才可以插入
	//特定的位置也不能为空
	assert(*sl);
	assert(pos);
	SL* cur = (SL*)malloc(sizeof(SL));
	if (cur == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//把要插入的数据放入新的节点之中
	cur->a = x;
	//先存下pos之后的节点，为一会连接新的节点做铺垫
	SL* pnext = pos->next;
	//连接节点
	pos->next = cur;
	cur->next = pnext;
}

//单链表指定位置的数据删除
void SLPosiDel(SL** sl, SL* pos)
{
	//先得判断链表不为空,和指定位置不为空
	assert(pos);
	assert(*sl);
	//先得存下pos之前的节点，为后面删除节点做准备
	SL* cur = *sl;
	while (cur->next != pos)
	{
		cur = cur->next;
	}
	//删除节点的操作
	cur->next = pos->next;
	free(pos);
	pos = NULL;
}

单链表的销毁，先看原理图，在实现代码：

//单链表的销毁
void SLDestroy(SL** sl)
{
	//先得判断链表是否为空
	assert(*sl);
	SL* cur = *sl;
	//遍历链表，实现链表的销毁
	while (cur->next)
	{
		SL* pnext = cur->next;
		free(cur);
		cur = pnext;
	}
	//链表释放完之后再将结构体指针置为空即可完成操作
	(*sl) = NULL;
}

好了，以上就是单链表的实现，通过注释和原理图的讲解相信大家已经对单链表有一定的认识，希望大家明白了之后可以自己实现一下单链表，好记性不如烂笔头，多实践才是刚入门的同学们应该做的。

四、单链表的优缺点

通过对单链表的实现，大家可以明显的感觉到链表的优缺点（相对于顺序表），接下来我来给大家一个完整的总结。

优点：1、单链表不会存在空间的浪费，它是存储数据才会开辟空间。