初阶数据结构——链表专题——单链表详解

目录

什么是链表

链表的语法结构

初始化链表

链表的打印  SLTPrint

链表中要用到的二级指针（简单说明）

动态创建节点  SLTBuyNode

链表的尾插  SLTPushBack

链表的头插  SLTPushFront

链表的尾删  SLTPopBack

链表的头删  SLTPopFront

链表的查找  SLTFind

指定位置之前插入数据  SLTInsert

指定位置之后插入数据  SLTInsertAfter

删除指定位置 ( pos ) 节点  SLTErase

删除指定位置 ( pos ) 之后的节点  SLTEraseAfter

销毁链表  SListDesTroy

总代码

结语

什么是链表

我们设想一个场景：假如现在有一排连在一起的房间，而我们现在在第一个房间里，每个房间都有一扇通往下一个房间的门，但是上了锁，每个锁都不一样，如下：

问：我们如何从第一间房间走到最后一间房间呢？

答：在每一间房间里都放上通往下一间房间的钥匙就可以了

链表的核心原理就是如此

我们的链表里面不仅存着其应该带的数值，还存放着指向下一个节点的地址，地址连着地址，就像一根链子一样把数据都串起来，所以才叫链表

链表的语法结构

typedef int SLTDataType;
 
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
    //链表的内容
 
	struct SListNode* next;
    //存放下一个链表节点地址的指针
}SLTNode;

首先，我们不清楚链表里面的元素未来需不需要修改，假如未来有一天，你突然需要将链表里面的全部元素都从  int  修改为  char ，这时你可就犯难了，因为如果链表很长的话，那么一个一个地修改将会是一个大工程

所以我们可以在创建出链表之前就先把要放进链表里的数据类型给 typedef 起来，这样，我们要转换类型的时候，我们就可以直接改，如下：

typedef int SLTDataType;

而我们的链表里面除了他要带的数据之外，还需要再带一个指针，该指针里面存放的是下一个链表节点的地址

初始化链表

我们先来看一个简单的链表

我们可以看到，链表节点一个接着一个，最后一个链表连着的是空（NULL）

所以，我们只需要先将结构体指针在 mian 函数中定义出来，接着将其置为  NULL  就可以了，后续的数据可以通过头插、尾插来添加

SLTNode* plist = NULL; 

你可以理解成：plist 是一个指向链表头节点的指针

但是现在还没有数据插入进来，所以 plist 就指向 NULL

链表的打印  SLTPrint

由于我们的链表仅仅只是逻辑上连续，所以没法像顺序表一样顺下去将其全部打印出来，我们需要找到一个链表打印一次，接着通过地址找到下一个节点，如此往复，直到碰到 NULL

SLTNode* plist = NULL; 

同时，我们的 plist 指向的就是头节点。但是，我们不能直接拿 plist 去遍历链表，因为遍历到最后我们的 plist 会指向 NULL，到时我们就找不到头节点了（虽然改变的只是形参，但我们还是养成好习惯吧）

所以，我们需要重新定义一个指针，用该指针来接收 plist 的值，拿这个指针去遍历链表

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

链表中要用到的二级指针（简单说明）

我们在顺序表中，头插尾插都是拿一级指针来接受的，这是因为顺序表里面我们要改变的数据是整形。由于形参是实参的一份临时拷贝，如果我们拿整形来接收的话，我们改变的只是形参，并没有影响到实参

同理，我们的链表头插，我们要改变的是一级指针的指向，因为我们需要有一个指针一直指向头节点，而头插的话我们需要在插入数据之后，将指向原头节点的指针改为指向新的头

所以，我们才需要使用二级指针

如果指向的是一个无效的空间，我们就需要传一个二级指针改变其指向，而如果已经指向了一个有效的空间（哨兵位），那么我们就不需要传二级指针，一级指针即可

如果不理解的话，各位不妨试一下：头插用二级指针，尾插用一级指针，现在 main 函数内使用头插，再尾插，你会发现数据都能打印出来

动态创建节点  SLTBuyNode

由于后面会频繁地用到如下操作，所以就将其单独封装为一个函数，方便我们后续使用

我们使用该函数时，必然是要插入数据到里面给链表扩列的，既然要扩列，就会有要放进去的数

因此，我们在动态开辟完空间之后，我们可以再顺带将开辟好的空间初始化一下

代码如下：

SLTNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

如上，我们用 newnode 接收开辟出来的空间，判断 newnode 是否为空，不为空就初始化该空间，最后返回 newnode

链表的尾插  SLTPushBack

我们先来看一下尾插的核心思想：

假如我现在有一个新的节点要从尾部插入链表

如上，我们先改变尾节点的指向，让其指向的下一个节点变为新节点，而我们的新节点就变成了新的尾节点，接着让其的下一个节点指向 NULL

我们可以用一个 while 循环遍历链表，如果遍历链表的指针的下一个节点为空（NULL），那么此时该指针指向的就是尾节点，代码如下：

//找尾节点
while (ptail->next)
{
	ptail = ptail->next;
}

在开始尾插之前，我们需要有怎么一块空间，所以我们需要用到我们上文实现过的  SLTBuyNode  函数，用该函数来创建节点

接着，我们还需要分情况：原链表有节点 & 原链表无节点

如果原链表无节点，那我们直接插入新节点即可

如果有节点，那么我们就按如上操作，走正常程序尾插代码即可

代码如下：

//链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
 
	SLTNode* newnode = SLTBuyNode(x);
 
	//链表为空，新节点作为phead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空，找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptail就是尾节点
	ptail->next = newnode;
}

链表的头插  SLTPushFront

头插相对尾插会简单很多，我们先来看一下其核心原理：

如下，现在有一串链表和一个待插入的节点

想要实现头插，我们只需要让新的节点指向原来的头节点，然后让 plist 指向新的头节点，至此，我们链表的头插功能就实现完成啦

代码如下：

//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
 
    //此处判断省略，一般情况下不会开辟失败
    //看官可自行添加
    
	newnode->next = *pphead;//新节点指向原头节点
	*pphead = newnode;//新的头节点
}

链表的尾删  SLTPopBack

我们先来看一下尾删的核心思想：

如下，假如我们要将下图尾节点（3）给删除

如上，我们需要先找到尾节点和尾节点的前一个节点，分别标记！！！

如果我们找到尾节点的前一个节点之后，就直接将其指向的下一个节点置为 NULL 的话，那么该节点指向的下一个节点就不是尾节点了，换言之，我们找不到原尾节点了！

我们假设  指针A  指向的是尾节点的前一个节点

指针A -> next = NULL

接着我们应该去找原尾节点，因为是动态开辟的空间，在堆区上，需要 free

按理说我们可以用 指针A -> next 找到原尾节点的，但是现在置空了

所以我们需要提前将两个节点都用指针标记好，方便操作

同时我们还需要分一分情况，如果该链表只有一个节点的话，那我们就直接将其  free  掉即可

如果成员大于等于两个的话，我们再按照如上方法尾删节点

我们有两种方法可以找到，虽然有点殊途同归，两个指针——prev  和  ptail

1.  我们先让  prev  指向头节点，ptail  指向头节点的下一个节点，接着让两个指针同时向后走，当  ptail  的下一个节点指向  NULL 时，循环结束，此时 prev 指向尾节点的前一个节点，ptail 指向尾节点

2. 我们先让  ptail  指向头节点，prev  置空，接着，我们先让  prev  的值等于  ptail，然后  ptail  往后走一个节点，这样当  ptail  的下一个节点为  NULL  时，再回到循环条件判断，发现为空，退出循环，prev  刚好在尾节点的前一个节点

这里拿 法二 来实现，代码如下：

//链表尾删
void SLTPopBack(SLTNode** pphead) {
	//链表存在
	assert(pphead);
	//链表不能为空
	assert(*pphead);
 
	//链表不为空
	//链表只有一个节点，有多个节点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
 
	prev->next = NULL;
	//销毁尾结点
	free(ptail);
	ptail = NULL;
}

链表的头删  SLTPopFront

对于链表的头删，我们只需要做两件事：

1. 将指向原头节点的指针赋值为新的头节点

2. 释放头节点的动态空间

这里我们需要注意，我们的顺序不能搞反！我们应该先完成 1 再完成 2

如果我们先完成 2 的话，那我们在将头节点释放了之后，我们就找不到新的头节点的位置了，这就会造成内存泄漏

步骤演示如下：

代码如下：

//链表头删
void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);
 
	//让第二个节点成为新的头
	//把旧的头结点释放掉
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

链表的查找  SLTFind

链表的查找部分较为简单，我们要做的就是遍历链表，一一比对，如果有相同的，我们就将指向该位置的指针返回，如果没有，就返回一个空指针（NULL）

代码如下：

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
 
	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur) //等价于pcur != NULL
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

指定位置之前插入数据  SLTInsert

我们先来看一下步骤演示

假如我们要在 3 之前插入数据：（注：此时 3 的位置我们是知道的）

注意！！！我们一定要先让新节点指向指定位置的节点

如上，如果我们先让 2 的下一个节点指向 6 的话，那么我们就无法通过 （2 节点 -> next ）找到 3，那么就会造成内存泄漏

如上，我们的 3 需要先找到传给   指定位置之前插入数据  的函数，假设指向该位置的指针叫 pos，我们如果要插入数据，就会设计到指定位置节点和指定位置的前一个节点，所以我们需要找到这两个节点

指定位置节点会传给函数，但是前一个节点需要我们自己找，我们可以通过遍历链表，当指向节点的下一个节点为 pos 的话，就代表我们找到了，代码如下：

//从头开始遍历
while (prev->next != pos)
{
	prev = prev->next;
}

要添加节点，我们就需要开辟动态空间并对其进行初始化，这项功能我们在上文中已经实现过了—— SLTBuyNode

接着我们还要分一下情况：（注：传过来的链表不能无节点）

1. 如果链表中仅有一个节点，那么指定位置之前插入数据就是头插，我们直接使用上文中实现过的头插函数即可

2. 如果链表中不止一个数据，那么我们就按正常程序插入数据：找节点，改指向

代码如下：

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);
 
	SLTNode* newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}
 
	//pos不是头结点的情况
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
 
	//改变指向
	prev->next = newnode;
	newnode->next = pos;
}

指定位置之后插入数据  SLTInsertAfter

指定位置之后插入数据相对指定位置之前会简单很多

我们先来看一看其核心思想：（假设我们要在 2 之后插入数据，此时 2 的位置是知道的）

为什么说在之后插入会简单很多，因为我们不像之前插入一样，需要用 while 循环找到前一个节点，我们的后一个节点可以通过 （ 2 节点 -> next ）直接找到

SLTBuyNode 是我们上文实现的开辟动态空间的函数

代码如下：

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
 
	SLTNode* newnode = SLTBuyNode(x);
 
	//改变指向
    //先让新节点指向下一个节点
    //指定位置节点再指向新节点
	newnode->next = pos->next;
	pos->next = newnode;
}

删除指定位置 ( pos ) 节点  SLTErase

对于删除指定位置节点，我们需要分两种情况：

1. 如果要删除的是头节点，那么我们直接使用头删函数  SLTPopFront

2. 如果不是头节点，那么我们就走正常程序，核心思路如下：（假如我们要删除 2 ）

如上，pos 节点是我们的指定节点，会作为参数传到函数中，是已知条件

如上我们可以知道，要实现删除指定位置节点，我们需要先找到指定位置的前一个结点

我们可以用一个 while 循环来实现，如果指向的节点的下一个节点是 pos，就退出循环

在改变了节点的指向之后，我们就将 pos 指针 free 掉，最后将 pos 指针置为空指针，放置野指针的出现

代码如下：

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	//pos刚好是头结点，没有前驱节点，执行头删
	if (*pphead == pos) {
		//头删
		SLTPopFront(pphead);
		return;
	}
 
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

删除指定位置 ( pos ) 之后的节点  SLTEraseAfter

我们删除指定位置之后的节点会相对简单

我们同样需要找三个节点，是 pos 节点及其后两个节点，如下：

假如我们现在要删除 2 节点之后的节点 —— 3

2 节点我们是知道的，3 节点我们可以通过（ 2 节点 -> next ）找到，4 节点我们可以通过（2 节点 -> next -> next ）找到

代码如下：

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	//pos->next不能为空
	assert(pos->next);
 
	//pos  pos->next  pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

销毁链表  SListDesTroy

要销毁链表的话，我们无法像顺序表一样一整块直接 free 掉，因为我们的链表在逻辑上连续，但在物理上是不连续的

所以我们需要 while 循环，直到找到 NULL 才结束循环

同时我们需要两个指针，一个指向要删除的节点，一个指向要删除节点的下一个节点

因为当我们将该节点删除了之后，我们无法找到下一个节点了，所以我们需要提前将下一个节点准备好

代码如下：

//销毁链表
void SListDesTroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
 
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

总代码

各位可以点开如下链接，里面是放在 gitee 里单链表的全部代码，需要的可以自取

初阶数据结构——单链表

结语

至此，我们单链表的相关知识就讲完啦！！接下来为各位带来的是双链表的相关知识

另外，如果觉得对你有帮助的话，希望可以多多支持喔！！！