单链表（增删改查）【超详细】

目录

单链表

1.单链表的存储定义

2.结点的创建

3.链表尾插入结点

4.单链表尾删结点

 5.单链表头插入结点 

6.单链表头删结点

7.查找元素，返回结点

 8.在pos结点前插入一个结点

​编辑

 9.在pos结点后插入一个结点

10.删除结点

11.删除pos后面的结点

12.修改链表结点的值

13.打印链表

 14.销毁链表

线性表的链式存储：链表

前言:

之前介绍过线性表的顺序存储方式：顺序表  发现顺序表在 插入删除操作需要移动大量元素；当静态顺序表长度变化较大时，难以确定存储空间的容量；造成存储空间的碎片。

数据结构中： 

注意 这里的是没有哨兵卫的链表。 

单链表

1.单链表的存储定义

单链表的存储与顺序表的存储不一样，单链表不仅仅存放数值，还要存放下一个结点的地址

代码 

typedef int SLNDataType;

typedef struct SListNode 
{
	SLNDataType val;	//存放单链表的值
	struct SListNode* next; //存放下一个单链表的地址
}SLNode;

当有了单链表的存储定义，我们就可以对单链表进行存放结点。 

2.结点的创建

这里使用malloc函数进行创建

代码

//创建一个结点
SLNode* CreateNode(SLNDataType x) 
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("CreateNode->malloc");
		exit(-1);
	}
	newnode->val = x;  //结点赋值
	newnode->next = NULL; //结点下一个结点为NULL
	return newnode;
}

3.链表尾插入结点

尾插结点：这里需要考虑两方面。

1、单链表为空，插入结点的情况，这里直接让头指针指向创建的新结点即可。

2、单链表不为空时，例如下图要尾插结点4

这里只需创建一个尾指针tail 遍历到第三个结点,把 第三个结点的next 指向 第四个结点即可

代码

//尾插结点
void SListPushBack(SLNode** pphead, SLNDataType x) 
{
    assert(pphead);
	SLNode* newnode = CreateNode(x);    //创建一个结点
	if (*pphead == NULL)	//单链表为空直接指向新结点
	{
		*pphead = newnode;
	}
	else  
	{
		SLNode* tail = *pphead;	//定义一个尾指针
		while (tail->next != NULL)	//找到表尾
		{
			tail = tail->next;	//指向下一个结点
		}
		//找到表尾后指向新结点即可
		tail->next = newnode;
	}
}

注意这里的二级指针。*pphead == phead,指向第一个结点。 

4.单链表尾删结点

单链表尾部删除结点：分两种情况。1)只有一个结点的情况   2)多个结的情况

因为平时删除结点，对于单链表，我们需要找到前面的结点。所以这里采取经典的双指针的方法

定义一个指向当前的结点(cur)，一个指向前面的结点(pre)，当遍历到表尾时，释放cur指向的结点后，把pre->next = NULL，这样就完成了尾删一个结点。

但是我们发现只有一个结点时

这里free(cur) ,但是pre指向NULL, 这条语句 pre->next = NULL 就是错的。

当然有些人会可能想到，为什么不让pre也指向第一个结点，如果这样想，这里显然是对free()这知识点模糊不清 。因为free(cur) 时 第一个结点的内存空间已经释放返还给操作系统了，所以pre此时指向的内存空间，属于访问野指针了。

所以我们对 1)只有一个结点的情况   2)多个结点的情况 分别处理

1）一个结点的情况

	if ((*pphead)->next == NULL)  //只有一个结点的情况
	{
		free(*pphead);
		*pphead = NULL;
	}

2) 多个结点的情况

定义一个指向当前的结点(cur)，一个指向前面的结点(pre)，当遍历到表尾时，释放cur指向的结点后，把pre->next = NULL，这样就完成了尾删一个结点。

		SLNode* cur = *pphead;
		SLNode* pre = NULL;
		while (cur->next != NULL)
		{
			pre = cur;
			cur = cur->next;
		}

		free(cur);
		cur = NULL;
		pre->next = NULL;

 代码

//尾删结点
void SListPopBack(SLNode** pphead) 
{
    assert(pphead);
	assert(*pphead); //避免链表为空
	if ((*pphead)->next == NULL)  //只有一个结点的情况
	{
		free(*pphead);
		*pphead = NULL;
	}
	else  //多个结点的情况
	{
		SLNode* cur = *pphead;
		SLNode* pre = NULL;
		while (cur->next != NULL)
		{
			pre = cur;
			cur = cur->next;
		}
		free(cur);
		cur = NULL;
		pre->next = NULL;
	}
}

当然上方代码也可以不用定义pre,来实现

//尾删结点
void SListPopBack(SLNode** pphead) 
{
	assert(*pphead); //避免链表为空
	if ((*pphead)->next == NULL)  //只有一个结点的情况
	{
		free(*pphead);
		*pphead = NULL;
	}
	else  //多个结点的情况
	{
		SLNode* cur = *pphead;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}

 5.单链表头插入结点 

首先创建一个新结点，然后让新结点指向 头指针指向的结点，头指针再指向新结点。

注意先后指向的顺序不能变。

代码

//头插结点
void SListPushFront(SLNode** pphead, SLNDataType x) 
{
    assert(pphead);
	SLNode* newnode = CreateNode(x);	//创建一个新结点
	newnode->next = *pphead;	//新结点指向 头指针指向的结点
	*pphead = newnode;	//再让头指针指向新结点
}

这样就变成

 如果指向的顺序变了，那就会出现这种错误

结点的next指向自己,这样是错误的

6.单链表头删结点

单链表头删除结点时，先临时创建一个next指针来指向第一个结点的下一个结点，然后释放第一个结点，再让头指针指向next，这样就完成删除第一个结点。

代码

//头删结点
void SListPopFront(SLNode** pphead) 
{
    assert(pphead);
	assert(*pphead);
	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

方法二

当然也可以先临时存放第一个结点，让*pphead指向第二个结点，然后再删除第一个结点。

代码

//头删结点
void SListPopFront(SLNode** pphead) 
{
    assert(pphead);
	assert(*pphead);
    SLNode* tmp = *pphead;
    *pphead = (*pphead)->next;
	free(tmp);
}

7.查找元素，返回结点

代码

//查找元素，返回结点
SLNode* SListFind(SLNode* phead, SLNDataType x) 
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
			return cur;	//查找成功返回当前结点
		cur = cur->next;
	}
	return NULL; //查找失败返回NULL
}

 8.在pos结点前插入一个结点

assert(phead&&pos); 这里的意思是避免是空指针的情况

 首先，在某结点前插入结点，当在第一个结点前插入结点时，这相当于表头插入结点；当在不是第一个结点前插入结点时，定义一个pre的指针遍历找到pos结点的前一个结点。

代码

//在pos结点前插入一个结点
void SListInsert(SLNode** pphead, SLNode* pos, SLNDataType x) 
{
    //避免指针为空
	assert(pphead);
    assert(*pphead); 
    assert(pos);
	if (*pphead == pos)
	{
		SListPushFront(pphead,x);
		return;
	}
	SLNode* newnode = CreateNode(x);
	SLNode* pre = *pphead;  //定义一个指向第一个结点的指针
	while (pre->next != pos)
	{
		assert(pre);//避免空指针
		pre = pre->next;
	}
	pre->next = newnode;
	newnode->next = pos;
}

图解

注意更改顺序 

上述说的是在有头指针的情况下进行在pos结点前插入一个结点。

题目变形 

当在没有给头指针的情况下，在pos的结点前如何插入一个结点？

解析：这里给出一个取巧的方法，即，先在pos后面插入结点，然后再把pos的值和新插入结点的值交换一下。这样就完成了在没有头指针的情况下在pos前插入一个结点。

代码

//在pos结点前插入一个结点
void SListInsert(SLNode* pos, SLNDataType x) 
{
    //避免指针为空
    assert(pos);
    SLNode* newnode = CreateNode(x);
    //先在pos后插入结点
    newnode->next = pos->next;
    pos->next = newnode;
    //交换两个结点的值
    SLNDataType tmp = pos->val;
    pos->val = newnode->val;
    newnode->val = tmp;
}

图解

 9.在pos结点后插入一个结点

这里定义一个指针next用于记录pos后面结点的地址，pos指向newnode, newnode指向next。

 代码

//在pos结点后插入结点
void SListInsertAfter(SLNode* pos, SLNDataType x) 
{
	assert(pos);
	SLNode* next = pos->next;	//先记录pos后面的结点
	SLNode* newnode = CreateNode(x);
	pos->next = newnode;
	newnode->next = next;
}

 

也可以这样写,注意顺序，避免指向自己。

  代码

//在pos结点后插入结点
void SListInsertAfter(SLNode* pos, SLNDataType x) 
{
	assert(pos);
	SLNode* newnode = CreateNode(x);
	newnode->next = pos->next;
    pos->next = newnode;
}

10.删除结点

例：删除结点pos, 在只有一个结点中删除结点，在多个结点中删除结点。

在只有一个结点中删除，那就相当于头删结点。

在多个结点中删除结点，那就需要知道被删除结点的前一个结点。这里采用双指针的思想进行删除结点。pre指针负责记录pos的前一个结点，next指针记录pos后面的结点。这样释放pos结点后，pre指向next，就完成了pos结点的删除。

 代码

//删除结点pos
void SListErase(SLNode** pphead, SLNode* pos) 
{
	assert(pphead);
    assert(pos);
	assert(*pphead);
	//pos为第一个结点且是第一个结点
	if (*pphead == pos)
	{
		//相当于头删结点
		SListPopFront(pphead);
	}
    else
    {
       	//在多个结点中删除结点pos
	    SLNode* pre = *pphead;
	    SLNode* next = pos->next;
	    while (pre->next != pos)
	    {
		    pre = pre->next;
	    }
	    free(pos);
	    pos = NULL;
	    pre->next = next; 
    }

}

图解 

11.删除pos后面的结点

首先断言一下，避免头指针和pos后面的结点为空。（assert(phead && pos->next);）

 代码

//删除pos之后的一个结点
void SListEraseAfter(SLNode* pos) 
{
    assert(pos);
	assert(pos->next); //避免为空指针
	//先使用next记录pos后面的结点
	SLNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

图解

12.修改链表结点的值

  代码

//修个pos结点中的值
void SListModify(SLNode* phead, SLNode* pos, SLNDataType x)
{
	assert(phead&&pos); //避免为空指针
	SLNode* cur = phead; //cur指向头指针
	while(cur != pos)
	{
		cur = cur->next;
	}
	cur->val = x; //修个值
}

13.打印链表

  代码

//打印结点
void SListPrint(SLNode* phead) 
{
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d->",cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

 14.销毁链表

这里因为是使用mallco开辟的空间，所以是需要进行手动释放的。

注意：可能是多个结点，也就是开辟了多个不连续内存空间，

所以，首先应该记录被释放结点的下一个结点的地址，避免释放后找不到下一个结点

释放完所有的结点,头指针置为NULL

 代码

//销毁链表
void SListDestory(SLNode** pphead) 
{
	assert(pphead);
	SLNode* p = *pphead;
	//注意结点的内存空间的释放，要释放多个
	while (p) 
	{
        //首先应该记录被释放结点的下一个结点的地址，避免释放后找不到下一个结点
		SLNode* tmp = p->next; 
		free(p);
		p = tmp; //指向下一个结点
	}
	//释放完所有的结点,头指针置为NULL
	*pphead = NULL;
}

总结：

单链表在找出位置的指针后，插入和删除时间复杂度为O(1),

但在查找方面上，单链表的时间复杂度为O(n),

当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构。

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

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

相关文章

科技改变农业：合成数据农业中的应用

科技改变农业：合成数据农业中的应用

介绍 农业在我们的生活中起着至关重要的作用，它为我们提供了生存的食物。如今，它遇到了各种困难，例如气候变化的影响、缺乏工人以及全球流行病造成的中断。这些困难影响了耕作用水和土地的供应，而这些水和土地正变得越来越稀缺。…
阅读更多...
小红书广州探店达人对接流程，小红书达人话术有哪些？

小红书广州探店达人对接流程，小红书达人话术有哪些？

很多时候，在刚开始接触这个行业时，许多人不知道如何对接达人，也不知道如何开口才能一下子打蛇打七寸，有事半功倍之效。今天我们为大家带来小红书广州探店达人对接流程，小红书达人话术有哪些？ 1. 自我介绍和…
阅读更多...
CAN总线记录诊断助手 CAN记录仪

CAN总线记录诊断助手 CAN记录仪

随着CAN总线的应用市场越来越多，不仅局限于汽车行业，工程车、特种车、消防、医疗等多行业都是以CAN总线通讯为主。总线的调试诊断也成为技术日常工作，有个好的工具能有效帮助发现问题、解决问题。 来可电子的CANLog-VCI是一款即插即用的CAN数…
阅读更多...
智汇云舟入选IDC《中国智慧园区解决方案2023年厂商评估》报告

智汇云舟入选IDC《中国智慧园区解决方案2023年厂商评估》报告

近日，全球领先的市场研究和咨询公司IDC发布报告《中国智慧园区解决方案2023年厂商评估》。报告内，IDC对中国市场具有代表性、且符合评估入围门槛要求的智慧园区解决方案厂商进行了综合评估。智汇云舟凭借在产品、技术等方面的综合优势，与大华…
阅读更多...
智汇云舟荣获2023轨道交通国际创新创业大赛“最具市场前景奖”

智汇云舟荣获2023轨道交通国际创新创业大赛“最具市场前景奖”

11月9日，由北京市科学技术委员会、中关村科技园区管理委员会、北京市经济和信息化局、北京市丰台区人民政府、中关村发展集团股份有限公司主办的2023中关村轨道交通国际创新创业大赛总决赛圆满收官。 智汇云舟提报的《视频孪生 改变视界》项目在数百个参赛项目中脱…
阅读更多...
IDEA取消git对项目的版本控制

IDEA取消git对项目的版本控制

前言 前几天新建项目的时候不小心选了个git仓库，导致这个测试项目一直被git管理着。 解决办法 1 右键项目 选择打开资源目录 2 删除.git文件 把目录下的.git文件删掉 3 删除idea中的git管理 删除完.git文件后，进入idea，右下角会有这样的提…
阅读更多...
GoLong的学习之路（二十三）进阶，语法之并发（go最重要的特点）（锁,sync包,原子操作）

GoLong的学习之路（二十三）进阶，语法之并发（go最重要的特点）（锁,sync包,原子操作）

这章是我并发系列中最后的一章。这章主要讲的是锁。但是也会讲上一章channl遗留下的一些没有讲到的内容。select关键字的用法，以及错误的一些channl用法。废话不多说。。。 文章目录 select多路复用通道错误示例并发安全和锁问题描述互斥锁读写互斥锁 syncsync.Wait…
阅读更多...
Device Partner 平台合作伙伴认证和数据安全保护

Device Partner 平台合作伙伴认证和数据安全保护

Device Partner 平台是面向 AIoT 产业链伙伴的一站式服务平台，伙伴可以通过平台获取最新的产品、服务与解决方案，实现智能硬件产品的开发、认证、量产和推广等全生命周期的管理，加入 HarmonyOS Connect 生态，共同提升消费者的智慧…
阅读更多...
基于减法平均算法的无人机航迹规划-附代码

基于减法平均算法的无人机航迹规划-附代码

基于减法平均算法的无人机航迹规划 文章目录 基于减法平均算法的无人机航迹规划1.减法平均搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要：本文主要介绍利用减法平均算法来优化无人机航迹规划。 …
阅读更多...
85.x的平方根（力扣）

85.x的平方根（力扣）

目录 问题描述 代码解决以及思想 知识点 问题描述 代码解决以及思想 class Solution { public:int mySqrt(int x) {int left 0; // 定义左边界int right x; // 定义右边界&#xff0c;初始值取 xwhile (left < right) { // 当左边界小于或等于…
阅读更多...
HiSilicon352 android9.0 适配红外遥控器

HiSilicon352 android9.0 适配红外遥控器

海思Android解决方案在原生Android基础上&#xff0c;基于传统电视用户使用习惯&#xff0c;增加了对红外遥控器和按键板的支持&#xff0c;使传统电视用户能更好适应智能电视方案。 一.功能描述&#xff1a; 在系统启动时&#xff0c;会先启动android_ir_user&#xff1b;vinp…
阅读更多...
SOLIDWORKS软件提供了哪些特征造型方法？硕迪科技

SOLIDWORKS软件提供了哪些特征造型方法？硕迪科技

SOLIDWORKS作为一款三维设计软件&#xff0c;为用户提供了多种特征造型方法&#xff0c;以下是其中几种常用的&#xff1a; 实体建模特征&#xff1a;SOLIDWORKS使用实体建模技术来创建和编辑三维几何体。通过使用基本几何体&#xff08;如立方体、圆柱体、圆锥体等&#xff09…
阅读更多...
四川芸鹰蓬飞商务信息咨询有限公司电商带货可信吗

四川芸鹰蓬飞商务信息咨询有限公司电商带货可信吗

今天&#xff0c;我们要向大家介绍的是四川芸鹰蓬飞商务信息咨询有限公司的电商带货服务&#xff0c;一个在电商领域独树一帜的服务项目。它的出现&#xff0c;不仅为电商行业注入了新的活力&#xff0c;也引领了行业发展的新趋势。 一、背景介绍 四川芸鹰蓬飞商务信息咨询有限…
阅读更多...
【1++的Linux】之线程（三）含生产者消费者模型

【1++的Linux】之线程（三）含生产者消费者模型

&#x1f44d;作者主页&#xff1a;进击的1 &#x1f929; 专栏链接&#xff1a;【1的Linux】 文章目录 一&#xff0c;可重入与线程安全二&#xff0c;死锁三&#xff0c;线程同步什么是线程同步&#xff1f;怎么实现线程同步条件变量 四&#xff0c;生产者与消费者模型1&…
阅读更多...
MySQL的安装使用（入学篇）

MySQL的安装使用（入学篇）

目录 1 MySQL安装 1.1 安装epel源 1.2 安装MySQL Repository 1.3 安装MySQL官方yum源 1.4 安装服务端、客户端 1.5 启动MySQL服务 2 MySQL 使用 2.1 获取初始登录密码 2.2 登录MySQL数据库 2.3 修改密码 2.4 退出数据库 2.5 使用新密码登录数据库 2.6 重启数据库 2.7 创建数据…
阅读更多...
【分享贴】需求变更、项目延误，项目经理应该如何应对？

【分享贴】需求变更、项目延误，项目经理应该如何应对？

案例分享&#xff1a; 项目经理小李跟进了一年半的项目&#xff0c;眼看着要到交付验收的阶段了&#xff0c;甲方的对接人却临时更换了&#xff0c;现在面临着一系列他无法处理的问题&#xff0c;项目目前推进困难。 案例背景&#xff1a; 小李在跟原甲方对接人合作时&#x…
阅读更多...
Qt 事件循环

Qt 事件循环

引出 UI程序之所叫UI程序&#xff0c;是因为需要与用户有交互&#xff0c;用户交互一般是通过鼠标键盘等的输入设备&#xff0c;那UI程序就需要有能随时响应用户交互的能力。 一个C程序的main函数大概是下面这样&#xff1a; int main() {...return 0; } 我们如何使程序能随…
阅读更多...
ECharts中rich的使用

ECharts中rich的使用

ECharts官方rich介绍 label: {// 在文本中&#xff0c;可以对部分文本采用 rich 中定义样式。// 这里需要在文本中使用标记符号&#xff1a;// {styleName|text content text content} 标记样式名。// 注意&#xff0c;换行仍是使用 \n。formatter: [{a|这段文本采用样式a},{b…
阅读更多...
使用Nginx和Spring Gateway为SkyWalking的增加登录认证功能

使用Nginx和Spring Gateway为SkyWalking的增加登录认证功能

文章目录 1、使用Nginx增加认证。2、使用Spring Gateway增加认证 SkyWalking的可视化后台是没有用户认证功能的&#xff0c;默认下所有知道地址的用户都能访问&#xff0c;官网是建议通过网关增加认证。 本文介绍通过Nginx和Spring Gateway两种方式 1、使用Nginx增加认证。 生…
阅读更多...
大模型+人形机器人，用AI唤起钢筋铁骨

大模型+人形机器人，用AI唤起钢筋铁骨

《经济参考报》11月8日刊发文章《多方布局人形机器人赛道,智能应用前景广》。文章称&#xff0c;工信部日前印发的《人形机器人创新发展指导意见》&#xff0c;按照谋划三年、展望五年的时间安排&#xff0c;对人形机器人创新发展作了战略部署。 从开发基于人工智能大模型的人…
阅读更多...
最新文章

Copyright @ 2022~2023