• 【初阶数据结构】单链表(C语言实现+动图演示)

    文章目录

    链表的概念及结构

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

    结构：
    在这里插入图片描述
    注意：

    1. 从图中可以看出，链表在逻辑上是连续的，但是物理上不一定连续
    2. 现实中结点一般是从堆上申请出来的

    链表的分类

    实际中链表的结构非常多样，以下情况组合起来就有8中链表结构

    1. 单向或双向

    在这里插入图片描述

    1. 带头或不带头

    在这里插入图片描述

    1. 循环或非循环

    在这里插入图片描述

    虽然有这么多的链表的结构，但我们实际中最常用的就是两种结构：无头单向非循环链表 和 带头双向循环链表
    在这里插入图片描述

    1. 无头单向非循环链表（单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

    今天我们就介绍实现在面试中常考的一种 —— 单链表

    链表的实现

    链表的单个结点的定义

    首先我们需要对单个结点进行定义

    typedef int SLTDataType;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述
    就像这个图一样，一个空间存放数据，一个空间存放下一个结点的地址

    单链表的接口

    我们把链表的主要接口写出来，然后我们一 一去实现这些接口：

    //打印单链表
void SListPrint(SLTNode* phead);
//销毁链表
void SListDestory(SLTNode** pphead);
//创建结点
SLTNode* BuySLTNode(SLTDataType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SListPopFront(SLTNode** pphead);
//尾删
void SListPopBack(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);

//在pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置之后插入
void SListInsertAftre(SLTNode* pos, SLTDataType x);

// 删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
// 删除pos后面位置
void SListEraseAfter(SLTNode* pos);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    创建结点

    因为我们在头插、尾插以及在pos位置前后进行插入结点之前，都必须申请一个结点，所以我将创建结点也封装成一个函数接口，在需要创建结点时直接调用，代码实现如下：

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

	return newnode;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    注意： 我们创建结点，由于需要自己手动申请内存，所以我们的结点是在堆上开辟的

    单链表的头插

    首先，我们来实现一个头插的接口，头插就是在链表的头部插入一个结点
    在进行头插的时候我们需要考虑一个问题：

    1. 这个接口接收的形参应该是一级指针还是二级指针？
    2. 此时链表 为空 或者 不为空，是否有区别？

    为了更好理解头插，我们先看一个动图展示

    请添加图片描述

    看完动图我们可以知到上面的问题。
    形参应该是二级指针。为什么呢？（只要涉及到头结点改变的都是，后面不重复说明）

    当我们需要进行头插时，我们需申请一个结点，且这个结点要变为头结点。就如上面动图所展示，head开始指向头结点d1,然后指向d3，最后指向d4，d4成为新的头结点。期间我们head指针的指向发生了改变。
    因为head本身是一个一级指针，若我们的形参还是一级指针，那么由于形参是实参的一份临时拷贝，形参的改变不会影响实参，所以需使用传参来改变指针的指向只能通过二级指针来改变，一级指针是不行的。

    要改谁就传谁的地址

    对于头插而言，链表是否为空是不需要考虑的，只需考虑到传二级指针就可以很好实现了 。

    代码实现如下：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    单链表的尾插

    尾插就是在链表的尾部插入一个结点，听起来很简单，但我们需要考虑的问题有：

    1. 此时链表是否为空，如果为空，我们需要怎么做，不为空有应该怎么做，这里需要分两种情况讨论。
    2. 也需要传二级指针

    动图展示：

    链表为空时：
    请添加图片描述
    链表不为空时：
    请添加图片描述
    代码实现如下：

    //尾插
void SListPushBack(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;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    单链表的头删

    头删时链表不能为空，否则就不能进行删除

    动图展示：
    请添加图片描述

    代码实现如下：

    //头删
void SListPopFront(SLTNode** pphead)
{
	assert(pphead);

	assert(*pphead != NULL);//暴力解决方式
	/*if (*pphead == NULL)
	{
		return;//温柔解决
	}*/

	SLTNode* tmp = *pphead;
	*pphead = tmp->next;
	free(tmp);
	tmp = NULL;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    单链表的尾删

    尾删就是删除链表的最后一个结点，听起来很简单，但我们仍需要注意几点：

    1. 只有一个结点
    2. 多个结点

    注意：尾删时链表不能为空，否则无法进行删除

    动图演示：

    只有一个结点：
    请添加图片描述
    多个结点
    请添加图片描述
    代码实现：

    //尾删
void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	//链表不能为空，否则无法进行删除
	assert(*pphead != NULL);

	//1.只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//2.多个节点
	else
	{
		//找尾 -- 删除尾结点，但要记录尾结点的前一个节点的位置		
		SLTNode* tail = *pphead;
		SLTNode* prev = *pphead;//记录尾结点的前一个结点

		//方法一
		//while (tail->next != NULL)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}
		//free(tail);
		//tail = NULL;
		//prev->next = NULL;

		//方法二
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    单链表的打印

    完成尾插尾删、头插头删，我们就可以实现打印接口了。

    链表的打印就是遍历一遍链表，链表遍历和数组有点不一样，链表的遍历是判断当前位置是否为NULL，是就不打印了，不是就打印，通过·cur = cur->next·来移动当前位置。

    代码实现如下：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    单链表的查找

    查找也是相当于遍历链表，从头开始遍历，如果找到该数据，则返回该结点的地址，没找到则返回NULL。

    由于仅仅时遍历链表，并没有涉及到头结点的改变，所以不需要传二级指针。

    代码实现如下：

    //查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;

	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    单链表在pos位置之前插入结点

    我们在pos位置之前插入结点，需要考虑以下几点：

    1. pos位置是头结点该如何插入？
    2. pos位置不是头结点该如何插入？
    3. pos需要检查是否为空，为空就不能进行操作
    4. 若是pos不在链表内则使用断言中断程序

    1 . pos位置是头结点：
    当pos位置是头结点时，我们在其前面插入结点就相当于头插，调用头插接口即可

    	if (pos == *pphead)//pos位置在头节点，相当于头插
	{
		//代码复用
		SListPushFront(pphead, x);
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    2 . pos位置不是头结点：
    如果pos位置不是头结点，那我们就需要遍历链表找到pos结点的前一个结点，在进行插入

    	SLTNode* newnode = BuySLTNode(x);

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;

		//暴力检查，若pos不在链表中，则prev为空,pos传错了
		assert(prev);
	}
	prev->next = newnode;
	newnode->next = pos;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    完整代码如下：

    //在pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)//pos位置在头节点，相当于头插
	{
		/*SLTNode* newnode = BuySLTNode(x);
		newnode->next = *pphead;
		*pphead = newnode;*/

		//代码复用
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySLTNode(x);

		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;

			//暴力检查，若pos不在链表中，则prev为空,pos传错了
			assert(prev);
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    单链表在pos位置之后插入结点

    在pos位置之后插入结点就简单很多了，只需判断pos位置是否为空，甚至不需要传链表的指针请添加图片描述

    代码实现如下：

    //在pos位置之后插入
void SListInsertAftre(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    单链表删除pos位置的结点

    在删除pos位置的结点时，我们需要考虑pos位置是否在头结点
    是头结点时，等于头删
    不是头结点，那我们就需要遍历链表找到pos结点的前一个结点，在进行删除

    代码实现如下：

    void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);//pos位置不能为空

	if (pos == *pphead)//头删
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL; //无意义，因为传过来的不是二级指针，形参的改变不影响实参
		//可以在使用的时候，自己置空
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    单链表删除pos位置之后的结点

    删除pos位置下一个的结点，只需将pos->next指向下一个的下一个即可，但我们要注意的是，pos位置不能是尾结点，否接就会造成内存非法访问问题。

    代码实现如下：

    // 删除pos后面位置
void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next != NULL);

	SLTNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    单链表的销毁

    链表的销毁也是依靠遍历来完成的，一个一个的销毁。

    //销毁
void SListDestory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;

	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    总结

    单链表在逻辑上是连续的，但在物理上不一定连续，可以做到按需所取，但不支持随机访问。

    上述实现单链表是传的二级指针，若不想传二级指针，可以使用以下两种方法：

    1.使用带头结点的链表，链表没有元素时头指针指向头结点，不需要对头指针修改
    2. 调用函数时以返回值的形式返回头指针，让头指针在调用时赋值（非常麻烦）

    完整代码

    代码保存在码云上：单链表

  • 相关阅读:
    mysql的常见的外键约束
    AVProVideo☀️十、来给视频设置封面
    【深度学习笔记】计算机视觉——单发多框检测（SSD）
    Biotin-PEG-NHS 生物素PEG活性酯
    C语言：二叉树的遍历以及遇到的问题
    力扣记录：Hot100（10）——461-739
    VS Code插件 — Settings Sync ： 设置和同步用户配置
    QT-事件循环机制
    iOS代码混淆-从入门到放弃
    4.9 GHz异帧隔离间距研究
  • 原文地址：https://blog.csdn.net/m0_58124165/article/details/126512452