单链表的基本实现(详细图解+解说)

一.前言：

我们都知道，顺序表是一块连续的可以存放数据的存储空间，其可以通过下标或指针解引用的方式快速访问某个位置的数据，但是由于空间的连续性，想要灵活的插入和删除数据便较为困难。

二.链表的结构实现:

链表是由多个结点相互链接形成的一种数据结构，换言之，结点是基本单位，下面介绍节点的实现

代码(编程语言为C语言):

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

一个结点为简单定义的一个结构体，其结构成员包含：

然而需要注意的是，对于一个空链表，其内部应该是没有数据的。也就是说，此时并没有创建任何结点，因此为了方便对链表进行管理，使用一个头指针slist指向头节点，若无结点，则slist指向NULL。此时链表便被我们很好的创建了。

三.单链表的功能实现-增删查.....

1.结点的申请

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	if (tmp == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}

 对tmp进行判断，若开辟失败其值为空指针，则打印错误信息，程序中断。若开辟成功，则将数据复制给data，并将其next初始化为NULL。

2.数据的头插

对于数据的头插，首先我们肯定要 1.申请新结点，那么接下来怎么进行链接呢？

 如图，此时需要将新申请的tmp结点头插入链表之中，则只需要先 2.将tmp结点内的next指向结点p1

 然后再 3.将slist指向新结点tmp

 此时新结点插入完成，即完成了数据的头插，下面给出代码实现:

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);//判断是否为空指针

	SListNode* tmp = BuySListNode(x);//步1
	tmp->next = *pplist;//步2
	*pplist = tmp;//步3
}

注:此处形参为头指针的二级指针，是因为函数需要对外部定义的头指针变量进行修改，使其指向新节点。若传入二级指针时，必须assert断言其是否为空。而若为一级指针，则无需判断，因为若链表为空，则其值便是NULL。下文函数实现功能同理。

3.数据的打印

此处先介绍数据的打印，以便于对刚实现的头插功能进行测试，同时也便于对后文实现的增删功能进行测试。

那么数据如何进行打印呢?我们知道，我们可以通过头指针找到第一个结点，结点内的next又可以寻找下一个结点，因此我们可以轻易的对链表进行遍历。下图为代码实现:

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

打印实现好之后，我们接下来完善剩余功能。

4.数据的尾插

1.申请新结点

2.遍历寻找当前尾结点p

3.插入新结点-将tmp赋值给p->next即可 

 如图操作即可,代码如下:

SListNode* tmp = BuySListNode(x);
SListNode* tail = *pplist;
while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = tmp;

尾结点特点便是p->next=NULL，因此如上代码，利用tail->next的条件判断，循环遍历寻找尾结点，再将tmp与尾结点进行链接。

然而我们需要考虑到，这只是一般情况。还有一种特殊情况没有考虑到-不存在尾结点，也即当前链表为空,此时则相当于头插，需要修改头指针，因此形参必须为二级指针。对于此特殊情况，*pplist==NULL，若执行上述程序，则条件判断时对空指针进行访问，显然是行不通的，因此需要与上述情况区别开，再复用头插函数进行插入，完整代码如下:

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* tmp = BuySListNode(x);
	SListNode* tail = *pplist;
	if (tail == NULL)
	{
		*pplist = tmp;
	}
	else
	{
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = tmp;
	}
}

 5.数据的头删

较为简单，只需1.首先令头指针指向结点2，2.再将结点1结构体申请的空间释放即可。 当然考虑特殊情况，若链表为空，无可删除的结点，此时则需要另行处理。最后给出代码如下:

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)//若为空指针，打印错误信息
	{
		printf("no valid data: %d\n",__LINE__);
		return;
	}
	SListNode* tmp = *pplist;//步1
	*pplist = tmp->next;
	free(tmp);//步2
}

 6.数据的尾删

以上图为例，基本思路是先找到尾结点p2，将p2结构体空间释放，然后将其前一个结点的next值改为NULL。但是要注意，目前我们实现的单链表只能向后访问，无法向前访问，因此我们的目的应该是尾结点前一个结点。代码实现如下:

        SListNode* tail = *pplist;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;

当tail->next->next==NULL时，即找到了p1处结点。然后将尾结点tail->next释放，再将p1的next赋值为NULL，即完成尾删。

然而还需要考虑两种特殊情况，1.链表为空  2.链表只有一个结点。对于这两种情况，显然上述代码是无法处理的，因此分开考虑，最终代码如下:

void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)
	{
		printf("no valid data: %d\n", __LINE__);
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

 1.如果为空指针，打印错误信息然后返回。  2.如果其值的next为空，即只有一个结点，此时释放此结点，头指针置空  3便为一般情况，上文已经解释过。

7.数据的查找

简单的链表遍历，此处不过详细介绍，直接上代码:

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

以cur为变量进行遍历，如果cur->data为查找值，则返回cur。否则遍历直到cur==NULL，函数返回NULL。

8.数据的指定插入和指定删除

-此处插入为向前插入

思路与前文的增删基本一致，下面给出代码:

指定插入:

void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(pos);
	SListNode* tmp = BuySListNode(x);
	if (*pplist == pos)
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		tmp->next = prev->next;
		prev->next = tmp;
	}
}

分三种情况: 

1.首先断言，若为空链表或目标位置为NULL则无法插入。

2.if-若头结点为目标位置，则调用头插函数。

3.else-寻找目标结点的前一个结点，然后将目标节点及其之前，之后的结点进行链接。

 指定删除:

void SListErase(SListNode** pplist,SListNode* pos)
{
	assert(pplist);
	assert(pos);//.....
	if (*pplist == pos)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

 同样三种情况:

1.首先断言，若为空链表或目标位置为NULL则无法插入。

2.if-若头结点为目标位置，则调用头删函数。

3.寻找目标结点的前一个结点，然后与目标结点下一个结点进行链接，并释放目标结点的空间。

9.链表的销毁

-注意需要将头指针置空 

遍历释放空间即可

void SListDestory(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;
}

四.后言

单链表部分就介绍到此，如有错误，欢迎指正。这篇博客花了博主挺长时间(哭)，路过的小伙伴也不妨点个关注呀，感谢支持