指针穿梭，数据流转：探秘C语言实现单向不带头不循环链表

本篇博客会讲解链表的最简单的一种结构：单向+不带头+不循环链表，并使用C语言实现。

概述

链表是一种线性的数据结构，而本篇博客讲解的是链表中最简单的一种结构，它的一个结点的声明如下：

// 单链表存储的数据类型
typedef int SLTDateType;
// 单向+不带头+不循环链表
typedef struct SListNode
{
	SLTDateType data;       // 数据
	struct SListNode* next; // 指向下一个结点
}SListNode;

一个Node中包含2个部分：data用来存储数据，被称作“数据域”；next用来存储一个后继指针，这个指针指向了下一个结点，被称作“指针域”。链表都是由数据域和指针域组成的。

单向不带头不循环链表的特点是：

1. 只有一个方向，即每个结点内只存储一个后继指针，指向下一个结点，而没有前驱指针。所以，当我们拿到一个结点后，只能顺着往后找，而不能往前找。
2. 没有哨兵位的头结点，也就是说，所有的结点，包括第一个结点（即头结点），存储的都是有效的数据。
3. 最后一个结点指向NULL，而不是指向头结点，没有循环。

大概的样子是：

下面我们用C语言来实现一个单链表出来。

申请结点

首先实现一个函数，来动态的申请一个结点，函数的声明如下：

SListNode* BuySListNode(SLTDateType x);

只需要动态开辟一个结点，并且把数据域初始化为x，指针域初始化为NULL，即可。

SListNode* BuySListNode(SLTDateType x)
{
	// 创建一个结点
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	// 检查是否创建成功
	if (newnode == NULL)
	{
		// 创建失败
		perror("malloc fail");
		return NULL;
	}
	// 创建成功
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

打印

为了方便测试，写一个函数来打印单链表，函数的声明如下：

void SListPrint(SListNode* plist);

只要给我一个头结点，我就能顺着这个头结点，挨个挨个往后打印。如何打印下一个结点的数据呢？每一个结点里的next指针都指向了下一个数据，所以cur=cur->next就能找到cur的下一个结点。

需不需要检查plist是否为NULL呢？不需要！因为当plist为NULL时，代表链表为空，链表为空是可以打印的。就相当于，我银行卡里没钱，你还不给我查询了？

void SListPrint(SListNode* plist)
{
	// 遍历链表，并打印数据
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

尾插

接下来实现一个函数，在链表的尾部插入数据，函数的声明如下：

void SListPushBack(SListNode** pplist, SLTDateType x);

哦，你可能会很奇怪，为什么参数是一个二级指针呢？这是因为，我们规定了，如果一个单链表为空，则对应的头结点的指针也为NULL。那么，当我们对一个空链表尾插时，就需要开辟一个新结点，并且把结点的地址给头结点指针。但是，如果传的是一级指针，比如SListNode* plist，根据“函数传参的本质是拷贝”，plist只是头结点指针的一份临时拷贝，改变plist并不能改变头结点指针。如果我们想改变头结点指针，就得传它的地址，也就是一个二级指针SListNode** pplist。

尾插需要分类讨论：

1. 链表为空，开辟一个新结点，把它的地址给头结点指针即可。
2. 链表不为空，需要从头结点开始，挨个挨个向后找，找到尾结点（后继指针为NULL的结点），并把尾结点的next改成新的结点的地址，相当于在尾结点后面链接了一个新的结点。

函数内部还需要检查pplist是否是有效的指针。这是因为，哪怕链表是空，头结点指针是NULL，但头结点指针的地址是不可能为NULL的。后面的其他函数如果还涉及到二级指针，也同理需要检查有效性。

那要不要检查*pplist呢？不需要！*pplist代表头指针，当头指针为NULL时，表示链表为空，是可以尾插的。这就相当于，我银行卡里没钱，还不给我存钱了？

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);

	// 开辟新节点
	SListNode* newnode = BuySListNode(x);

	// 判断链表是否为空
	if (*pplist == NULL)
	{
		// 链表为空
		*pplist = newnode;
	}
	else
	{
		// 链表不为空
		// 找尾结点
		SListNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}

		// 在尾结点后面链接新结点
		tail->next = newnode;
	}
}

头插

接下来实现一个函数，再链表的头部插入数据。函数的声明如下：

void SListPushFront(SListNode** pplist, SLTDateType x);

函数的参数又有一个二级指针，这就非常有意思了。由于头插时，是一定要改变头指针的，而在函数内部改变头指针是要传头指针的地址的，即二级指针。

头插需不需要分类讨论呢？事实上，是不需要的，因为不同情况的处理方式是相同的。

1. 若链表为空，则直接把头指针改成新的结点的地址。
2. 若链表非空，则让新结点的next存储原来的头结点的地址，再让头指针指向新的结点。

其实，case 1也能按照case 2一样处理。因为，新结点的next存储的也是NULL，即原头结点的地址，而我们规定了若链表为空，则头指针为NULL。

函数一定要检查pplist的有效性，因为当链表为空时，头指针为NULL，但是头指针的地址不为NULL。

那要不要检查*pplist呢？不需要！*pplist代表头指针，头指针为NULL，代表链表为空，也是可以头插的。还是那句话，我银行卡里没钱，还不给我存钱了？

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);

	// 开辟新结点
	SListNode* newnode = BuySListNode(x);
	// 链接
	newnode->next = *pplist;
	// 更新头结点
	*pplist = newnode;
}

尾删

下面实现一个函数，来删除链表尾部的数据，函数的声明如下：

void SListPopBack(SListNode** pplist);

emmm，又是二级指针。大家不用意外，单链表的结构存在一定的缺陷，实现起来确实会稍显复杂。那么这次为什么又要使用二级指针呢？因为存在一种情况，当链表只剩下一个结点的时候，尾删后就空了，此时头结点发生了改变，而要在函数内部改变头指针是需要传二级指针的。

尾删可以说是相当的复杂了，要分3种情况来讨论：

1. 若链表为空，就不能尾删。
2. 若链表只有1个结点，删完后就空了，需要改变头指针。
3. 若链表至少有2个结点（包含2个），则需要找到尾结点并且释放掉，还要把尾结点的前一个结点的next置NULL。

这里重点说明第3种情况。我们需要找到尾结点的前一个，所以可以多定义一个tailPrev指针，在tail往后遍历之前，先把tail赋值给tailPrev，tail再往后走，这样tailPrev永远比tail慢一步，当tail走到尾结点时，tailPrev刚好指向尾结点的前一个。

pplist还是需要检查的，这里就不赘述了。

*pplist要不要检查呢？这次就需要检查了！因为*pplist代表头指针，当头指针为NULL时，表示链表为空，链表为空是不能尾删的！也就是说，我银行卡里没钱，就不能再取钱了，否则就乱套了（不考虑信用卡等情况）。

void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	// 防止是空链表
	assert(*pplist);

	// 判断结点数是否多于一个
	if ((*pplist)->next == NULL)
	{
		// 只有一个结点了
		// 释放空间
		free(*pplist);
		// 把链表更新为空链表
		*pplist = NULL;
	}
	else
	{
		// 至少有2个结点
		// 找到尾结点和尾结点前面的那个结点
		SListNode* tail = *pplist; // 尾结点
		SListNode* tailPrev = NULL; // 尾结点前面的那个结点
		while (tail->next)
		{
			// tailPrev比tail慢一步
			tailPrev = tail;
			tail = tail->next;
		}

		// 释放尾结点
		free(tail);
		tail = NULL;
		// tailPrev成为新的尾结点
		tailPrev->next = NULL;
	}
}

头删

接着实现一个函数，删除链表头部的结点，函数声明如下：

void SListPopFront(SListNode** pplist);

我们又见面了，二级指针。这次为什么又要用二级呢？当我们删除头部的结点时，头指针应该指向下一个结点，此时需要再函数内部改变头指针，自然需要传头指针的地址，即二级指针。

和尾删类似，还是需要分3种情况讨论；不过又类似头插，可以把其中2种情况合并一下：

1. 链表为空，不能头删。
2. 链表只有1个结点，需要释放掉这个结点，并把头指针置NULL。
3. 链表至少有2个结点（包括2个），需要释放掉头结点，并让头指针指向原头结点的下一个结点。

显然，case 2和case 3可以合并，因为在case 2中的“把头指针置NULL”，和case 3中的“让头指针指向原头结点的下一个结点”是一回事，因为当只有1个结点时，原头结点的下一个结点是不存在的，此时原头结点中的next指针为NULL。

函数内部仍然要检查pplist，因为pplist是不可能为NULL的；而且要检查*pplist，因为链表为空就不能头删了，这2个检查和尾删的检查类似。

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	// 保证至少有一个结点
	assert(*pplist);

	// 保存头结点下一个结点或者NULL
	SListNode* next = (*pplist)->next;
	// 释放空间
	free(*pplist);
	// 新的头为next
	*pplist = next;
}

查找

下面我们来实现一个函数，在链表中查找指定数据。函数的声明如下：

SListNode* SListFind(SListNode* plist, SLTDateType x);

这个函数相当于让大家中场休息一下。遍历链表并一一比对即可。

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	// 遍历数组，查找x
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			// 找到了
			return cur;
		}
		cur = cur->next;
	}
	// 找不到
	return NULL;
}

后插

接下来实现一个函数，在指定的结点后面插入一个新的结点。函数的声明如下：

void SListInsertAfter(SListNode* pos, SLTDateType x);

我们需要先记录pos的下一个结点next，在pos和next中间插入新的结点即可。

注意检查pos指针的有效性。

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);

	// 创建新的结点
	SListNode* newnode = BuySListNode(x);
	// 插入到pos的后面
	// 链接newnode和pos->next
	newnode->next = pos->next;
	// 链接pos和newnode
	pos->next = newnode;
}

后删

再来实现一个函数，删除指定结点的后一个结点，函数的声明如下：

void SListEraseAfter(SListNode* pos);

只需要先保存要删除的结点del和要删除的结点的后一个结点next，删除del，并且链接pos和next。

注意检查pos指针的有效性，并且pos->next也不能为NULL，不然的话删啥删。

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	// 保证后面有结点
	assert(pos->next);

	// 保存pos后面的结点
	SListNode* del = pos->next;
	// 链接pos和del->next
	pos->next = del->next;
	// 释放空间
	free(del);
	del = NULL;
}

插入

接下来实现一个函数，在指定结点的前面插入新的结点。函数的声明如下：

void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);

好家伙，二级指针又来了。确实，这玩意挺烦人，但不能没有，因为万一是头插，是一定要改变头指针的。

可以分2种情况讨论：

1. 若*pplist==pos，则复用头插函数。
2. 否则，找到pos的前一个结点prev，在prev和pos中间插入新结点即可。

函数需要检查pplist和pos，*pplist就没必要检查了，因为如果头指针为NULL，pos也必然为NULL。

void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(pos);

	// 判断是不是头插
	if (*pplist == pos)
	{
		// 头插
		SListPushFront(pplist, x);
	}
	else
	{
		// 不是头插，即pos前面至少有一个结点
		// 找pos前面的结点
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		// 开辟新结点
		SListNode* newnode = BuySListNode(x);
		// 在prev和pos中间插入newnode
		// 链接newnode和pos
		newnode->next = pos;
		// 链接prev和newnode
		prev->next = newnode;
	}
}

删除

下面我们来实现一个函数，删除指定的结点，函数的声明如下：

void SListErase(SListNode** pplist, SListNode* pos);

大家又看到二级指针应该不意外了吧，因为这次可能涉及到头删，分类讨论：

1. 若*pplist==pos，则头删。
2. 否则，找到pos的前一个结点prev和后一个结点next，删除pos，链接prev和next。

同理还是检查pplist和pos，*pplist就没必要检查了，因为若头指针为NULL，pos也一定为NULL。

void SListErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(pos);

	// 判断是不是头删
	if (*pplist == pos)
	{
		// 头删
		SListPopFront(pplist);
	}
	else
	{
		// 不是头删
		// pos前面至少还有一个结点
		// 找pos前面的结点
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		// 链接prev和pos->next
		prev->next = pos->next;
		// 删除pos
		free(pos);
		pos = NULL;
	}
}

销毁

有始有终，我们还需要销毁链表，函数声明如下：

void SListDestroy(SListNode** pplist);

依次遍历并且删除即可。注意删除前要保存next，否则就找不到下一个了。

注意检查pplist的有效性，但是不用检查*pplist，因为链表为空也是可以销毁的。

void SListDestroy(SListNode** pplist)
{
	assert(pplist);

	// 遍历链表，并销毁结点
	SListNode* cur = *pplist;
	while (cur)
	{
		// 保存下一个
		SListNode* next = cur->next;
		// 释放空间
		free(cur);
		// 迭代
		cur = next;
	}

	*pplist = NULL;
}

总结

我们实现的链表结构有3个特点：单向+不带头+不循环。这个结构是有缺陷的，具体体现为：尾插、尾删效率较低，因为需要先找尾结点。但是反过来，头插、头删效率非常高，所以在需要大量头插、头删，并且不需要尾插、尾删的场景中，非常适合使用这种链表。

如果你认为链表就这样了，那就大错特错了。链表中有一种王者结构：双向+带头+循环链表，这种链表非常强大，至于具体有多强大，又应该如何实现，欲知后事如何，且听下回分解。

感谢大家的阅读！文章来源地址https://www.toymoban.com/news/detail-451290.html

到了这里，关于指针穿梭，数据流转：探秘C语言实现单向不带头不循环链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！