【初阶数据结构】探索数据的多米诺链：单链表

链表

概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链式结构的逻辑一般是连续的，但是在物理存储上不一定是连续的，因为每个节点都是从堆上申请来的，从堆上申请的空间要根据实际情况分配空间，两次申请可能是连续的也有可能不是连续的

简单来说，每个节点都存储了下一个节点的地址，即能找到下一个节点，就形成了链表

我们还需要了解几个概念：

🚩头结点

图中的plist就是头结点，位于链表的起始位置，但不存储实际的有效数据(有效数据指的是结构体的内的数据，而不是结构体地址)，主要作用是作为链表的入口，通过它的指针域来指向链表中的第一个实际存储数据的节点

🚩首节点

首节点就是跟在头节点后的链表中第一个存储实际有效数据的节点

🚩哨兵位

哨兵位和头结点类似，通常不存储实际数据，存储地址，哨兵位可以看成一个灵活的节点，可以在链表任何位置方便进行增删查改操作

每个节点的结构体：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

分类

链表有三种分类方式
🚩⑴单向或双向

🚩⑵带头或不带头

🚩⑶循环或者非循环

这三种情况能组合出8种链表，这里我们只介绍两种常用的链表

无头单向非循环链表： 结构简单，实现麻烦，通常在面试笔试中以题目形式出现比较多(因为其他出成题目太难了)，单链表也更多的作为底层结构来进行算法应用

带头双向循环链表： 结构复杂，实现简单，这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

单链表接口实现

单链表节点创建

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

顺序表中我们空间不够时需要不断扩容，链表中的节点申请函数就是这种类似的效果，但是顺序表是对它底层的数组进行二倍扩容，而节点申请函数一次性只能申请一个节点，用一个给一个，间接避免了空间浪费，注意返回的是新节点的地址

单链表打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while(cur->next != NULL)会遗漏最后一个数据
	//while(cur != NULL)也可以这样写
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++只有数组才这么写
	}
	printf("NULL\n");
}

先传入头结点，然后我们需要一个cur指针作为移动指针来遍历单链表中的数据，每个节点的next都存储了下一个节点的地址，所以循环赋值就可以实现单链表的移动，最后一个节点指向的是空指针

🔥值得注意的是： 顺序表的打印需要断言传入的结构体指针是因为该指针涉及到访问，万一传入的空指针，会造成非法访问；链表的打印有可能该链表本来就是空的，空链表也是能打印的，而且也不涉及指针访问，所以加断言反而不合理

单链表尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	//分没有节点，和有节点的情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

凡是涉及增加删除节点的操作，都要考虑是否为空的情况要不要特别考虑，因此这里为空时直接将头指针和新节点链接即可；不为空时循环遍历找到最后一个节点，将最后一个节点和新节点连接

🔥值得注意的是： 循环判断条件为tail->next != NULL，因为为空时可能要修改头指针存的地址，所以应该传二级指针

单链表头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头指针中存储的是第一个节点的地址，所以newnode->next = *pphead，然后newnode就成了第一个节点，那么当前头指针存的就是当前第一个节点newnode的地址

单链表尾删

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//*phead要指针访问所以要断言
	if ((*pphead)->next == NULL)//分没有节点，和有节点的情况
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找最后一个节点的前一个节点
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;//free之后可以赋值但不能指针访问
	}
}

当没有节点时，删除的就是头指针，直接释放即可；当有节点时，我们要给最后一个节点和倒数第二个节点做标记，因为最后一个节点要释放，倒数第二个节点需要把他的next置为NULL

单链表头删

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

先存储首节点的地址，便于把首节点的下一个节点传给头节点，注意不要先释放节点，避免非法访问

单链表查找

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

这个和顺序表一样，通过简单的遍历链表 一 一 对比值即可

单链表在pos位置插入x

pos前

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

同样是分为链表为空和链表不为空的情况，当链表为空时，相当于头插；当链表不为空时，prev找到pos的前一个位置，然后进行链接操作即可

pos后

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

从代码形式上来看，pos后的插入明显是比pos前插入更简单的，pos前需要多传一个头指针参数，找到pos前一个数的位置；pos后只需要在pos后直接链接即可

单链表在pos位置删除x

pos前

void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

和在pos位置删除其实是一样的，分为空和不空的链表，但是一般我们不在函数内将要删除的节点置为空，习惯性在函数外进行此操作

pos后

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	//del = NULL;
}

直接释放pos位置之后的节点即可，但是要注意需要断言pos->next，万一是最后一个节点的话，在其后删除会报错

单链表销毁

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* del = pcur;
		pcur = pcur->next;
		free(del);
	}
	*pphead = NULL;
}

销毁的方法也不难，就是遍历链表，只要链表不为空就循环释放节点，关键是我们在释放前要把下一个节点记录下来，如果直接释放了当前节点，那么就找不到下一个节点了，所以我们要把下一个节点保存下来才释放当前节点

代码展示

传送门：Gitee单链表代码

SList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);

SLTNode* BuySLTNode(SLTDataType x);

void SLTPushBack(SLTNode** pphead, SLTDataType x);

void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);

void SLTPopFront(SLTNode** pphead);

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

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);

void SLTInsertAfter(SLTNode* pos, SLTDataType x);

void SLTEraseAfter(SLTNode* pos);

void SLTDestroy(SLTNode** pphead);

SList.c

#include "SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//创建节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

//查找节点
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//pos前插入
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//pos前删除
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

//pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//pos后删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！