数据结构之单链表详解（C语言手撕）

​
在这里插入图片描述

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
——————————————————————————————————————————————

🎉文章简介：

🎉本篇文章对      用C语言实现单链表   学习的相关知识进行分享！🎉💕
如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉
————————————————

一.链表的概念及结构

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

在这里插入图片描述从图片中可以看出，链表的每个节点都是一个结构体，该结构体中有一个存储数据的变量和一个指向下一节点的结构体指针；
在逻辑上是连续的，但是在物理空间上不一定连续，因为链表节点都是每次插入数据时在堆上申请出来的；每次申请出来的空间不一定是连续的；

二.无头单向非循环链表的结构

在这里插入图片描述无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等；

二.无头单向非循环链表的结构及实现

一.结构：

在这里插入图片描述

二.功能函数的实现（含性能分析与图解）
  1. 打印链表
  2. 创建节点函数
  3. 头插节点函数
  4. 头删节点函数
  5. 尾插节点函数
  6. 尾删节点函数
  7. 查找函数
  8. 在一节点位置之前插入一个节点
  9. 在一节点位置之后插入一个节点
  10. 在一节点位置之前删除一个节点
  11. 在一节点位置之后删除一个节点
打印链表

图解：遍历访问
在这里插入图片描述先定义一个结点指针指向头节点，往后依次遍历，与数组不同的是，不是cur++，而是让cur指向下一个节点，即cur=cur->next;

代码实现：

void SLPrint(SLNode* pphead)
{
	assert(pphead);     //断言

	SLNode* cur = pphead;     //让cur指向头节点进行遍历
	while (cur)        //注意：条件不是cur->next，因为如果是cur->next为空就不进入循环的话，则最后一个节点就访问不到
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("NULL");    //最后打印一个NULL、方便观察
	printf("\n");
}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

创建节点函数

代码实现：

SLNode* BuySLnewnode(SLDateType x)
{

	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));   //注意：创建的是节点，一个结构体，而不是一个数据类型
	if (newnode == NULL)          //判断
	{
		perror("malloc fail");
		exit(-1);             //开辟失败，以异常退出程序
	}
	newnode->next = NULL;     //下一个节点置NULL
	newnode->val = x;         //赋值

	return newnode;           //返回该该结点指针
}
头插节函数

图解：
在这里插入图片描述

代码实现：

void SLPushFront(SLNode** pphead, SLDateType x)   
//注意：这里需要节点的二级指针，因为外面调用的时候，如果传的是头指针的话，是传值，
//函数里面改变不影响头指针的指向，所以这里需要二级指针，函数调用的时候需要传二级指针
{

	SLNode* newnode = BuySLnewnode(x);     //创建新节点
	if (*pphead == NULL)       //检查，如果为空链表
	{
		*pphead = newnode;      //直接将*pphead指向新节点
	}
	else
	{
		newnode->next = *pphead;    //第二种情况
		(*pphead) = newnode;
	}

}

性能分析：
时间复杂度：O(1)
空间复杂度：O（1）

头删节点函数

图解：
在这里插入图片描述

代码实现：

void SLPopFront(SLNode** pphead)
{
	assert(*pphead);    //头指针不能为空

	if((*pphead)->next==NULL)     //第一种情况
	{
		free(*pphead);     
		*pphead = NULL;

		return;
	}
	SLNode* tmp = (*pphead)->next;   //保存下一个节点
	free(*pphead);
	*pphead = tmp;

}

性能分析：
时间复杂度：O(1)
空间复杂度：O(1)

尾插节点函数

图解：
在这里插入图片描述

代码实现：

void SLPushBack(SLNode** pphead, SLDateType x)
{

	SLNode* newnode = BuySLnewnode(x);
	if (*pphead == NULL)     //空链表
	{ 
		*pphead = newnode;
		return;
	}

	SLNode* tail = *pphead;     //定义一个尾指针
	while (tail->next)
	{
		tail = tail->next;
	}                           //退出循环后tail->next为NULL；
	tail->next = newnode;       //链接

}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

尾删节点函数

图解：
在这里插入图片描述

代码实现：

在这里插入代码片void SLPopBack(SLNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)   //第一种情况
	{
		free(*pphead);
		*pphead = NULL;

		return;
	}

	SLNode* Prevtail = *pphead;    //记录尾指针前面的一个节点
	SLNode* tail = *pphead;        //尾指针
	while (tail->next)
	{
		Prevtail = tail;           
		tail = tail->next;
	}
	free(tail);             //释放掉尾节点
	Prevtail->next = NULL;   

}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

查找函数

代码实现：

SLNode* SLFind(SLNode* pphead, SLDateType x)
{
	assert(pphead);

	SLNode* cur = pphead;       //遍历查找
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;      //返回节点指针
		} 
		cur = cur->next;
	}

	return NULL;         //没找到，返回NULL
}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

在pos位置之前插入一个节点

图解：
在这里插入图片描述

代码实现：

//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{
	assert(*pphead);
	assert(pos);

	if (pos == *pphead)        //第一种情况：头插
	{
		SLPushFront(pphead, x);
		  
		return;
	}
	SLNode* newnode = BuySLnewnode(x);     
	
	SLNode* cur = *pphead;     //遍历，找到pos的前一个节点
	while (cur->next)
	{
		if (cur->next == pos)      //找到了
		{
			newnode->next = cur->next;    //链接
			cur->next = newnode;

			return;
		}
		cur = cur->next;
	}

}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

在pos位置之后插入一个节点

图解：
在这里插入图片描述

代码实现：

//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x)
{
	assert(pos);
	SLNode * newnode = BuySLnewnode(x);     

	newnode->next = pos->next;   //链接
	pos->next = newnode;

}

性能分析：

删除pos位置之前一个节点

图解：
在这里插入图片描述

代码实现：

//删除pos之前的节点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pos);
	assert(pos != *pphead);
	if (pos== (*pphead)->next)  //头删，第一种情况
	{
		free(*pphead);
		(*pphead) = pos;

		return;
	}
	SLNode* cur = *pphead;
	while (cur)
	{
		if (cur->next->next == pos)   //找到pos前面的第二个节点
		{
			free(cur->next);
			cur->next = pos;     //链接

			return;
		}
		cur = cur->next;
	}

}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

删除pos位置之后一个节点

图解：
在这里插入图片描述

代码实现：

//删除pos之后的节点
void SLEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);   //当pos后无节点，无意义

	if (pos->next->next == NULL)   //尾删
	{
		pos->next = NULL;
		return;
	}
	SLNode* cur = pos->next->next;   
	free(pos->next);   
	pos->next = cur;   //链接
	cur = NULL;

}

性能分析：
时间复杂度：O(1)
空间复杂度：O(1)

二.总代码

```cpp
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDateType;

typedef struct SListNode
{
	SLDateType val;
	struct SListNode* next;
}SLNode;

SLNode* BuySLnewnode(SLDateType x);
void SLPrint(SLNode* pphead);

void SLPushBack(SLNode** pphead, SLDateType x);
void SLPushFront(SLNode** pphead, SLDateType x);

void SLPopFront(SLNode** pphead); 
void SLPopBack(SLNode** pphead);

SLNode* SLFind(SLNode* pphead,SLDateType x);

//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos,SLDateType x);

//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x);

//删除pos之后的节点
void SLEraseBack(SLNode* pos);

//删除pos之前的节点
void SLErase(SLNode** pphead,SLNode* pos);



```cpp
#include"SList.h"


SLNode* BuySLnewnode(SLDateType x)
{

	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;

	return newnode;
}

void SLPrint(SLNode* pphead)
{
	assert(pphead);

	SLNode* cur = pphead;
	while (cur)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
}

void SLPushFront(SLNode** pphead, SLDateType x)
{

	SLNode* newnode = BuySLnewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		newnode->next = *pphead;
		(*pphead) = newnode;
	}

}
void SLPushBack(SLNode** pphead, SLDateType x)
{

	SLNode* newnode = BuySLnewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	SLNode* tail = *pphead;
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next = newnode;

}

void SLPopFront(SLNode** pphead)
{
	assert(*pphead);

	if((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;

		return;
	}
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;

}
void SLPopBack(SLNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;

		return;
	}

	SLNode* Prevtail = *pphead;
	SLNode* tail = *pphead;
	while (tail->next)
	{
		Prevtail = tail;
		tail = tail->next;
	}
	free(tail);
	Prevtail->next = NULL;

}
SLNode* SLFind(SLNode* pphead, SLDateType x)
{
	assert(pphead);

	SLNode* cur = pphead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}


//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{
	assert(*pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLPushFront(pphead, x);

		return;
	}
	SLNode* newnode = BuySLnewnode(x);
	
	SLNode* cur = *pphead;
	while (cur->next)
	{
		if (cur->next == pos)
		{
			newnode->next = cur->next;
			cur->next = newnode;

			return;
		}
		cur = cur->next;
	}

}

//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x)
{
	assert(pos);
	SLNode * newnode = BuySLnewnode(x);

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

}


//删除pos之后的节点
void SLEraseBack(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	if (pos->next->next == NULL)
	{
		pos->next = NULL;
		return;
	}
	SLNode* cur = pos->next->next;
	free(pos->next);
	pos->next = cur;
	cur = NULL;

}

//删除pos之前的节点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pos);
	assert(pos != *pphead);
	if (pos== (*pphead)->next)
	{
		free(*pphead);
		(*pphead) = pos;

		return;
	}
	SLNode* cur = *pphead;
	while (cur)
	{
		if (cur->next->next == pos)
		{
			free(cur->next);
			cur->next = pos;

			return;
		}
		cur = cur->next;
	}

}
三.性能分析

与顺序表相比：
优点：
1.按需申请，没有空间浪费；
2.头插头删效率高

缺点：
1.不支持下标随机访问
2.尾插尾删效率低

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/439428.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python与Go代码转换库之grumpy使用详解

Python与Go代码转换库之grumpy使用详解

概要 在软件开发领域，Python 和 Go 是两种备受欢迎的编程语言，它们各自拥有独特的优势和特点。Python 以其简洁、易学和强大的生态系统而闻名，而 Go 则以其高效、并发和简洁的语法而受到广泛青睐。然而，在某些情况下，开发人员可能会希望将 Python 代码转换为 Go 代码，以…
阅读更多...
西门子S120故障报警F30003的解决办法总结

西门子S120故障报警F30003的解决办法总结

西门子S120故障报警F30003的解决办法总结 如下图所示&#xff0c;压机在回程时突然出现报警&#xff0c;故障代码为&#xff1a;30003&#xff0c; 如下图所示&#xff0c;查找手册可以看到F30003的报警分析为&#xff1a;直流母线欠压 如下图所示&#xff0c;本来想测量输入端…
阅读更多...
升工作效率，确保公文准确性——爱校对软件的职场革命

升工作效率，确保公文准确性——爱校对软件的职场革命

在当今快节奏的工作环境中&#xff0c;效率和准确性成为了每个职场人士的追求目标。尤其是在处理官方文件和公文材料时&#xff0c;一点小小的错误都可能造成沟通障碍甚至误解&#xff0c;给工作带来不必要的困扰。这时&#xff0c;一款高效、精准、易用的校对软件就显得尤为重…
阅读更多...
Nginx配置http访问转https

Nginx配置http访问转https

场景: 我们通常使用http://www.xxx.com访问自己后台或网站时,浏览器会提示不安全,这就让上层领导看着认为我们做的网站不安全,而通过https访问就没有不会出现这样的问题 配置https前提条件:我们去申请ssl证书, 看自己的域名是在哪个平台购买的 可去 阿里云 或 腾讯云申请免费的…
阅读更多...
rocketmq学习笔记（一）安装部署

rocketmq学习笔记（一）安装部署

初次使用rocketmq&#xff0c;记录一下全流程步骤。 1、下载安装包 首先在官网&#xff0c;下载安装包&#xff0c;可也根据官方文档进行部署&#xff0c;但有一些细节没说明&#xff0c;可能会有坑&#xff0c;本文会尽量详细的描述每个步骤&#xff0c;把我踩过的坑填补上。…
阅读更多...
P5149 会议座位 题解 归并排序 逆序对

P5149 会议座位 题解 归并排序 逆序对

会议座位 传送门 题目背景 话说校长最近很喜欢召开全校教职工大会&#xff0c;让老师们强行听他装逼 题目描述 现在校长在校园网上公布了一份座位表&#xff0c; n n n 位老师从左到右依次排成一行。老师们都对这个座位很满意。 然而到了开会时&#xff0c;校长不小心把座…
阅读更多...
开源的前端思维导图库介绍

开源的前端思维导图库介绍

在开源社区中&#xff0c;有许多优秀的思维导图库可供开发者使用。这些库通常具有丰富的功能和灵活的API&#xff0c;可以满足不同需求的前端开发。以下是一些流行的开源前端思维导图库&#xff0c;以及它们的特点和区别。 1. **MindMap** 特点&#xff1a; - 基于原生…
阅读更多...
c1-第三周

c1-第三周

文章目录 1月份2.定义一个整形数组arr2.定义整形栈s3.输入一个字符串包括大小写和数字&#xff0c;将其中的大写英文字母改为小写&#xff0c;并且输出数字个数4.根据下面数据&#xff0c;编程实现要求功能&#xff1a; 9月1.编写程序实现以下功能或问题3.完成以下功能4.对运算…
阅读更多...
义乌慧鼎思是做什么的？

义乌慧鼎思是做什么的？

根据天眼查的信息&#xff0c;我们可以对其进行一番探究。义乌慧鼎思(义乌市慧鼎思商务信息咨询有限公司)成立于2021年&#xff0c;注册地位于我国浙江省义乌市。从其名称来看&#xff0c;“慧鼎思”寓意着智慧、重量和思考&#xff0c;这三个词汇也许能为我们揭示企业的经营理…
阅读更多...
基于JAVA+ springboot实现的抗疫物质信息管理系统

基于JAVA+ springboot实现的抗疫物质信息管理系统

基于JAVA springboot实现的抗疫物质信息管理系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 …
阅读更多...
IR 召回测试数据集（中文测试集）——T2Ranking

IR 召回测试数据集（中文测试集）——T2Ranking

文章排名包括两个阶段&#xff1a;文章检索和文章重排序&#xff0c;这对信息检索&#xff08;IR&#xff09;领域的学术界和业界来说都是重要而具有挑战性的课题。然而&#xff0c;常用的文章排名数据集通常集中在英语语言上。对于非英语场景&#xff0c;如中文&#xff0c;现…
阅读更多...
简单实现微信机器人-接入ChatGPT3.5

简单实现微信机器人-接入ChatGPT3.5

前端基于开源项目&#xff1a;wechaty实现微信网页版功能&#xff0c;感兴趣的小伙伴可以自行研究。 前端代码已开源&#xff1a;https://github.com/labi-xiaoxin/wechat-bot-wechat4u.git 本项目搭建愿景&#xff1a; 1、在无法科学上网的情况下&#xff0c;实现ChatGPT对话…
阅读更多...
unicloud 云数据库概念及创建一个云数据库表并添加记录(数据)

unicloud 云数据库概念及创建一个云数据库表并添加记录(数据)

云数据库概念 uniCloud提供了一个 JSON 格式的文档型数据库。顾名思义&#xff0c;数据库中的每条记录都是一个 JSON 格式的文档。 它是 nosql 非关系型数据库&#xff0c;如果您之前熟悉 sql 关系型数据库&#xff0c;那么两者概念对应关系如下表&#xff1a; 关系型JSON 文…
阅读更多...
基于React的低代码开发：探索应用构建的新模式

基于React的低代码开发：探索应用构建的新模式

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法|MySQL| ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-OywB1Epu30PrvOJQ {font-family:"trebuchet ms",verdana,arial,sans-serif;f…
阅读更多...
华为“仓颉”不是中文编程：中文编程早有所属，势如破竹

华为“仓颉”不是中文编程：中文编程早有所属，势如破竹

“何时能见证中国自主研发的编程语言崛起&#xff1f;”这是我们这些对IT生态心怀关切的人常常深思的问题。 语言&#xff0c;作为文化的灵魂&#xff0c;总是与特定的环境和人群紧密相连。无论是中文还是英语&#xff0c;它们都不仅仅是交流的工具&#xff0c;更是各自文化背…
阅读更多...
SL3038宽电压降压恒压 72V降12V，110V降压12V 开关型降压芯片

SL3038宽电压降压恒压 72V降12V，110V降压12V 开关型降压芯片

SL3038宽电压降压恒压开关型降压芯片是一款高效、稳定的电源管理芯片&#xff0c;广泛应用于各种电子设备中。它能够将高电压降至所需的低电压&#xff0c;并保持输出电压的稳定&#xff0c;从而确保设备的正常运行。本文将详细介绍SL3038的工作原理、特点、应用以及使用注意事…
阅读更多...
5分钟 electron 入门

5分钟 electron 入门

文章目录 番茄钟应用起步安装初始化启动 electron 项目nodemon 启动项目 主进程 app 和窗口管理 BrowserWindowapp 、BrowserWindowready 事件webContent&#xff1a;主进程控制网页退出应用 装载网页到窗口资源来源安全声明SPA 单页应用 进程的环境Chromium 沙盒Electron 主进…
阅读更多...
vs2022方法上面看不到引用条数

vs2022方法上面看不到引用条数

vs2022 Win11 开发过程中经常要查看方法的引用情况&#xff0c;这个功能一直好好的&#xff0c;但是有一天突然不行了&#xff0c;看不到引用了&#xff0c;这就让人很难受&#xff0c;从网上查找资料说需要设置CodeLens&#xff0c;这个一直是勾着的&#xff0c;没动过这个设…
阅读更多...
JVM-对象创建与内存分配机制深度剖析 3

JVM-对象创建与内存分配机制深度剖析 3

JVM对象创建过程详解 类加载检查 虚拟机遇到一条new指令时&#xff0c;首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用&#xff0c;并且检查这个 符号引用代表的类是否已被加载、解析和初始化过。如果没有&#xff0c;那必须先执行相应的类加载过程。 new…
阅读更多...
好用的便签软件，好用便签排行榜

好用的便签软件，好用便签排行榜

在生活和工作中&#xff0c;便签软件的使用已经成为我们日常不可或缺的工具。随着技术的发展&#xff0c;便签软件的功能越来越强大&#xff0c;用户也有了更多选择。好用的便签软件有哪些&#xff0c;希望大家能从好用便签排行榜中找到适合自己的工具。 ##1.好用便签 好用便签…
阅读更多...
最新文章

Copyright @ 2022~2023