【数据结构】链表及无头单向非循环链表实现

1.顺序表的问题

2.链表的概念、结构及分类

3.无头+单向+非循环链表实现

3.1创建节点

3.2头插数据

3.3头删数据

3.4尾插

3.5尾删

3.6链表销毁

3.7查找一个元素

3.8在pos之前插入

3.9在pos之后插入

3.10删除pos位置

3.11删除pos之后的位置

1.顺序表的问题

顺序表的缺点：

中间和头部插入数据的时间复杂度为O(N)
增容需要申请空间，realloc函数可能会进行异地扩容，拷贝数据并释放旧空间存在消耗
增容一般是呈两倍的增长，势必会有一部分空间的浪费

顺序表问题的改进：链表

对于顺序表，其在物理内存上的存储是连续的，而链表通过指针访问，物理存储不一定连续，并且链表结构的节点可以按需申请和释放

2.链表的概念、结构及分类

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

📖Note:

由上图，链式结构在逻辑结构上是连续的，但在物理结构上不一定连续
一般情况下节点都是在堆区申请的
从堆区申请空间，两次申请的空间可能连续，也可能不连续

链表分类：

1️⃣单向或者双向

2️⃣带头或者不带头

3️⃣循环或者非循环：

以上三类排列组合可以形成8种不同类型的链表

实际中最常用的两种为：无头单向非循环链表和带头双向循环链表

🔅无头单向非循环链表：结构简单，一般不会用来单独存储数据。实际中更多是作为其他数据结构的子结构，，如哈希桶，图的邻接表等

🔅带头双向循环链表：结构最复杂，一般单独存储数据，。实际中使用的链表数据结构，都是带头双向循环链表。虽然该结构复杂，但使用代码实现却更简单

3.无头+单向+非循环链表实现

首先创建一个节点结构：
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode,*PSLTNode;
//PSLTnode是一个结构体指针，指向下一个节点
📖Note :

单链表不需要初始化，可以直接定义一个空链表
SLTNode* plist = NULL;//定义一个空链表

3.1创建节点

由于创建新节点的操作在接下来的函数中也会进行，并且在函数中创建的节点为局部节点，出了作用域就会销毁，所以可以将创建节点操作封装成函数

//创建一个节点
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;
}

创建的节点如下：

📖Note :

这是一个独立的节点，此时与链表不存在任何联系

新节点与链表建立联系即插入数据的过程

3.2头插数据

头插数据，我们需要创建一个新节点再进行头插

对于指向链表头的指针phead,我们需要让它指向新的链表头

即需要改变phead中存放的地址，因为形参只是实参的临时拷贝，所以在函数中传值调用改变形参的值并不会影响实参，所以对phead需要传址调用；phead是一个指针类型，指向phead的指针是一个二级指针

单链表存在两种状态：空链表和非空链表

对链表的操作都应该分情况讨论

1️⃣对于非空链表，头部插入数据的步骤如下

2️⃣对于空链表，头插数据的步骤如下：

可以发现，空链表和非空链表的头插步骤是相同的，因此可以归并为一类

头插函数SListPushFront的参数问题：

头插数据，我们需要改变phead，phead是一个结构体指针，指向第一个节点，当我们向头插函数传入参数phead后，我们在头插函数中完成了头插操作，但形参只是实参的一份临时拷贝，我们在头插函数中对形参的修改并不会影响实参的值，即头插操作出了函数实际并没有完成，如下图解释

函数完成头插操作如上图，当头插函数调用结束，其创建的函数栈帧也随之销毁，plist便不能找到我们要插入的节点，因此头插失败

以上为传值调用的过程，即将phead的值传给函数，但实参和形参之间没有实质性的联系，对形参的改变并不会改变实参，因此我们需要传址调用，即将phead的地址传给头插函数，在头插函数内通过访问phead的地址改变其实际值

phead是一个结构体指针，它的类型是SLTNode*，所以它的地址是一个二级指针，类型是SLTNode**，以下为代码实现

//头插
void SListPushFront(SLTNode** phead, SLTDataType x)
{
	//创建一个节点
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *phead;
	*phead = newnode;//头插之后新节点为头节点

}

为了便于观察，我们可以封装一个函数来打印链表

打印链表只是访问数据，不会改变链表中的值，所以phead传值调用即可

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

3.3头删数据

对于指向链表头的指针phead,我们需要让它指向删除原头节点后新的链表头

头删也需要改变phead中存放的地址，所以形参应为二级指针

空链表和非空链表应该分情况讨论

1️⃣对于非空链表

2️⃣当链表中的所有元素删除完之后，该链表为空链表，空链表不能进行删除操作，所以应该对phead的值进行检查，为空则不能删除，以下代码采用的是暴力检查的方法，链表为空则不能删除并且报错误信息

//头删
void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//空链表则不能删除

	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	//释放被删除节点所用占用的空间
	free(del);
	del = NULL;	
}

3.4尾插

尾插操作首先需要我们找到尾节点的位置，尾节点tail的特征是tail->next=NULL;通过遍历查找尾节点，再将新节点和尾节点链接即可

1️⃣对于非空链表，我们不需要改变头节点指针plist的值，可以理解为非空链表尾插时改变的是结构体成员变量，我们只需要结构体指针就能访问结构体成员变量

2️⃣对于空链表，我们需要改变头节点指针plist的值，可以理解为空链表尾插时要改变结构体指针，只能通过二级指针访问

空链表需要传址调用，非空链表传值调用即可，为了代码的简洁，我们统一采用传址调用

具体实现如下:

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

3.5尾删

尾删操作也需要我们找到尾节点的位置，尾节点tail的特征是tail->next=NULL;

同时尾删操作需要找到尾节点的前一个节点，并将其指针域置空

因此我们需要两个指针prev和tail进行迭代

1️⃣对于非空链表，尾删步骤如下：

2️⃣对于只有一个节点的链表，尾删只需要直接释放发、该节点，将phead置空

3️⃣对于空链表，则不能进行删除，采用暴力检查即可

实现如下：

//尾删
void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表为空则不能删除
	//对于只有一个节点的链表
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//对于多于一个节点的链表
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}	
}

3.6链表销毁

我们对链表的操作并不是每次都能将其节点删除完，因此当程序运行结束时，就可能存在内存泄漏问题，我们需要在每次程序退出之前对链表进行销毁，将其节点所占用的内存空间释放，可以将这个操作封装成一个函数

由于链表结构的特殊性，它并不能像顺序表一样一次性释放所有空间，只能每次释放一个节点，所以我们通过遍历依次释放所有节点

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

3.7查找一个元素

查找一个元素，需要遍历链表，查找元素并不会改变链表结构，所以传值调用即可

📖Note

1️⃣当链表为空则不进行查找，暴力检查

2️⃣链表遍历结束，没找到对于元素，则返回空指针NULL

//查找一个元素 
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);//空链表不能进行查找
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

3.8在pos之前插入

给定一个位置pos,在该位置之前插入一个节点

1️⃣对于pos不等于头指针phead的情况，不会改变头指针phead,步骤如下图：

由上图可以看出前插需要pos位置的前一个节点的指针，这样新节点才能与链表建立联系

使用两个指针进行迭代，找到pos节点及其前一个节点，链接新节点即可

2️⃣当pos恰好等于头指针phead时，其前一个节点不存在，但这时可以认为这是头插操作，直接调用头插函数即可，此时需要二级指针

所以我们统一使用二级指针

//在pos之前插入
void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);//创建一个新节点
    //pos恰好等于头指针phead
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			//检查pos的正确性，即pos可能不存在于链表中
			assert(prev);
		}
		prev->next = newnode;
		newnode->next = pos;
	}	
}

pos位置前插函数需要与查找函数配合使用，从而能给定pos的位置

    //pos之前插入
	SLTNode* pos = SListFind(plist, 1);
    //在1之前插入元素5
	if (pos)
	{
		SListInsertBefore(&plist, pos, 5);
	}
	SListPrint(plist);

3.9在pos之后插入

在pos之后插入，pos恰好等于头指针phead时插入和pos不等于头指针phead时插入的步骤是相同的，为了保证代码统一性，pos后插函数也使用二级指针

📖Note

上图中是①②的顺序不能调换，如果先执行②，再执行①，newnode指向其本身，插入失败

//在pos之后插入
void SListInsertAfter(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);//创建一个新节点

	newnode->next = pos->next;
	pos->next = newnode;
}

pos位置前插函数需要与查找函数配合使用，从而能给定pos的位置

//pos之后插入
	SLTNode* pos = SListFind(plist, 4);
	//元素4之后插入元素5
	if (pos)
	{
		SListInsertAfter(&plist, pos, 5);
	}
	SListPrint(plist);

3.10删除pos位置

删除pos的位置，需要分类讨论

1️⃣pos不等于头指针phead

2️⃣pos等于头指针phead，使用二级指针，此时即头删操作，调用头删函数即可

//删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	//pos等于头指针，相当于头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			//检查pos的正确性
			assert(prev);
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除pos位置函数需要与查找函数配合使用，从而能给定pos的位置

//删除pos位置
	SLTNode* pos = SListFind(plist, 4);
	
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);

3.11删除pos之后的位置

删除pos之后的位置，pos为尾节点时删除和不是尾节点时删除相同

//删除pos之后的位置
void SListEraseAfter(SLTNode* phead, SLTNode* pos)
{
	assert(pos);
    //对于只有一个节点的链表，不能进行后删
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next = pos->next;
		pos->next = next->next;
		free(next);
	}	
}

删除pos位置之后元素函数需要与查找函数配合使用，从而能给定pos的位置

//删除posz之后位置
	SLTNode* pos = SListFind(plist, 3);

	if (pos)
	{
		SListEraseAfter(&plist, pos);
	}
	SListPrint(plist);

【数据结构】链表及无头单向非循环链表实现

1.顺序表的问题

2.链表的概念、结构及分类

3.无头+单向+非循环链表实现

3.1创建节点

3.2头插数据

3.3头删数据

3.4尾插

3.5尾删

3.6链表销毁

3.7查找一个元素

3.8在pos之前插入

3.9在pos之后插入

3.10删除pos位置

3.11删除pos之后的位置

相关文章

Linux操作系统——第五章进程信号

C语言——指针详解（进阶）

Kubernetes - HPA-VPA - metrics介绍和安装 - HPA实验

小研究 - 面向 Java 的高对抗内存型 Webshell 检测技术（四）

《TCP IP网络编程》第七章

windows10 搭建hadoop环境，并且使用hadoop命令

数据结构（王道）——数据结构之二叉树

Kubernetes - kubeadm部署

走进Vue2飞入Vue3

“掌握更多的快速排序技巧：三路划分、双路快排和非递归的深入理解”

【Matlab】智能优化算法_麻雀搜索算法SSA

Http host 标头攻击

高精尖领域数据暴增，分布式存储渐当大任

[NGINX] NGINX下载、安装编译、启动检查停止命令

InsCode Stable Diffusion使用教程【InsCode Stable Diffusion美图活动一期】

使用 uiautomator2+pytest+allure 进行 Android 的 UI 自动化测试

RabbitMQ保证消息的可靠投递，Java实现RabbitMQ消息的可靠投递，Springboot实现RabbitMQ消息的可靠投递

laravel 的SQL使用正则匹配

【kubernetes系列】Kubernetes之调度器和调度过程

AI智能助手的未来：与人类互动的下一代人工智能技术