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

目录

单链表

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; //结点下一个结点为NULLreturn 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{//在多个结点中删除结点posSLNode* 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),

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

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

一文读懂RestCloud AppLink

一文读懂RestCloud AppLink

RestCloud AppLink是什么？ RestCloud AppLink 是一种应用程序集成解决方案，它提供了一套工具和技术，用于实现不同应用程序之间的无缝集成和交互。平台旨在解决企业中应用程序之间数据孤岛、信息孤立和业务流程不畅的问题，提高企业…
阅读更多...
每次重启完IDEA,application.properties文件里的中文变成?

每次重启完IDEA,application.properties文件里的中文变成?

出现这种情况，在IDEA打开Settings-->Editor-->File Encodings 然后，你需要将问号改为你需要的汉字。 重启IDEA，再次查看你的.properties文件就会发现再没有变成问号了
阅读更多...
XOR Construction

XOR Construction

思路： 通过题目可以得出结论 b1^b2a1 b2^b3a2 ....... bn-1^bnan-1 所以就可以得出 (b1^b2)^(b2^b3)a1^a2 b1^b3a1^a2 有因为当确定一个数的时候就可以通过异或得到其他所有的数，且题目所求的是一个n-1的全排列 那么求出a的前缀异或和arr之后…
阅读更多...
网页分析和xml.etree库

网页分析和xml.etree库

源代码： Lib/xml/etree/ElementTree.py 该xml.etree.ElementTree模块实现了一个简单高效的 API，用于解析和创建 XML 数据。 一、说明 这是一个简短的使用教程xml.etree.ElementTree（ET简而言之）。目标是演示该模块的一些构建块和基…
阅读更多...
送水服务预约小程序内容该如何做

送水服务预约小程序内容该如何做

无论小区还是办公楼等场景，送水服务往往有较高需求，同时该服务属于长期稳定性的，因此对品牌来说，如何打造品牌获取更多用户及转化非常重要，然而在实际订水过程中，又会面临着一些难题： 1、品牌传…
阅读更多...
代码随想录算法训练营第四十六天|139. 单词拆分、多重背包问题、总结

代码随想录算法训练营第四十六天|139. 单词拆分、多重背包问题、总结

第九章 动态规划part08 139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 关于字符串类型的题目还是…
阅读更多...
ElementUI之el-progress动态修改进度条里面文本颜色与进度条色块统一

ElementUI之el-progress动态修改进度条里面文本颜色与进度条色块统一

1.效果&#xff1a; 2.实现方式 通过行内style样式动态给整个progress赋颜色 再在样式里给进度条文字单独设置颜色为默认继承父级颜色就ok啦 <el-progress class"custom-progress" stroke-linecap"square" :style"{color:item.color}" :colo…
阅读更多...
使用电阻检测仪是否能满足生产车间防静电要求

使用电阻检测仪是否能满足生产车间防静电要求

在现代工业生产中&#xff0c;静电对产品质量和人员安全造成的影响越来越受到重视。特别是在电子、半导体、化工等领域&#xff0c;静电问题可能导致产品损坏、人员触电等严重后果。因此&#xff0c;生产车间的防静电工作显得尤为重要。而电阻检测仪作为一种常用的防静电工具&a…
阅读更多...
Java后端开发——JDBC入门实验

Java后端开发——JDBC入门实验

JDBC&#xff08;Java Database Connectivity&#xff09;是Java编程语言中用于与数据库建立连接并进行数据库操作的API&#xff08;应用程序编程接口&#xff09;。JDBC允许开发人员连接到数据库&#xff0c;执行各种操作&#xff08;如插入、更新、删除和查询数据&#xff09…
阅读更多...
OpenAI开发者大会大模型圈开卷AI Agent? 实在智能布局前瞻已下“先手棋”

OpenAI开发者大会大模型圈开卷AI Agent? 实在智能布局前瞻已下“先手棋”

“平地起惊雷&#xff0c;至今有余音。” 去年的11月&#xff0c;OpenAI发布ChatGPT给科技圈劈下了一道惊雷&#xff0c;引爆了全世界的AI大模型热潮&#xff0c;全球科技巨头公司争先恐后地推出通用大模型&#xff0c;探索产业应用的可能。 短短一年后&#xff0c;北京时间1…
阅读更多...
汇编-DUP操作符

汇编-DUP操作符

DUP操作符使用整数表达式作为计数器&#xff0c; 为多个数据项分配存储空间。 在为字符串或数组分配存储空间时&#xff0c;这个操作符尤其有用&#xff0c;并且可以使用初始化或非初始化数据&#xff1a; .data BYTE 20 DUP(0) ;20个字节&#xff0c;都等于0 BYTE 20 …
阅读更多...
电商项目之Java8函数式接口落地实践

电商项目之Java8函数式接口落地实践

文章目录 1 问题背景2 前言3 多处重复的重试机制代码4 优化后的代码5 进一步优化 1 问题背景 在电商场景中&#xff0c;会调用很多第三方的云服务&#xff0c;比如发送邮件、发起支付、发送验证码等等。由于网络存在抖动&#xff0c;有时候发起调用后会拿到500的状态码&#xf…
阅读更多...
Linux学习第38天：Linux I2C 驱动实验（二）：哥俩好

Linux学习第38天：Linux I2C 驱动实验（二）：哥俩好

Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味 思文短情长 本节笔记主要学习I2C设备驱动编写及硬件原理图分析。 先把整个本节的思维导图贴出来&#xff1a; 二、I.MX6U的I2C适配器驱动分析 适配器驱动一般都是由SOC厂商提…
阅读更多...
最新整理【剑侠情缘龙雀修复BGU版】linux服务端带授权后台+详细教程+包进游戏

最新整理【剑侠情缘龙雀修复BGU版】linux服务端带授权后台+详细教程+包进游戏

搭建资源下载地址&#xff1a;最新整理【剑侠情缘龙雀修复BGU版】linux服务端带授权后台详细教程包进游戏 - 海盗空间
阅读更多...
虚幻5 删除C盘缓存及修改缓存路径

虚幻5 删除C盘缓存及修改缓存路径

一.修改C盘缓存 C盘缓存路径为&#xff1a; C:\Users\xx(这里是你的用户名)\AppData\Local\UnrealEngine\Common\DerivedDataCache 注意&#xff0c;如果没有AppData文件夹&#xff0c;请依次点击查看-勾选显示隐藏的项目&#xff0c;即可 可删除里面的所有文件即可 二.修改…
阅读更多...
nanodet训练自己的数据集、NCNN部署到Android

nanodet训练自己的数据集、NCNN部署到Android

nanodet训练自己的数据集、NCNN部署到Android 一、介绍二、训练自己的数据集1. 运行环境2. 数据集3. 配置文件4. 训练5. 训练可视化6. 测试 三、部署到android1. 使用官方权重文件部署1.1 下载权重文件1.2 使用Android Studio部署apk 2. 部署自己的模型【暂时存在问题】2.1 生成…
阅读更多...
Win10 + VS017 编译SQLite3.12.2源码

Win10 + VS017 编译SQLite3.12.2源码

参考&#xff1a; [1] WIN10 VS2019下编译GDAL3.0PROJ6SQLite_gdal 3 win10编译-CSDN博客 [2] 如何编译SQLite-How To Compile SQLite-CSDN博客 如何生成静态库&#xff1a; 参考&#xff1a; WIN10 VS2019下编译GDAL3.0PROJ6SQLite_gdal 3 win10编译-CSDN博客 如何生成exe:…
阅读更多...
105.am40刷机（linux）折腾记1-前期的准备工作1

105.am40刷机（linux）折腾记1-前期的准备工作1

前段时间在某鱼上逛的时候&#xff0c;发现一款3399的盒子只要150大洋&#xff0c;内心就开始澎拜&#xff0c;一激动就下手了3台&#xff0c;花了450大洋&#xff08;现在想想&#xff0c;心都碎了一地&#xff09;。 然后自己又来来回回折腾了几天&#xff0c;目前能跑上fire…
阅读更多...
viple入门（四）

viple入门（四）

&#xff08;1&#xff09;行打印 主要用于在运行窗口中显示数据&#xff0c;打印完成后&#xff0c;自动换行。 注意事项&#xff1a;不可同时打印两个数据&#xff0c;例如 解决方案1&#xff1a;使用或并&#xff0c;使得每次进入行打印的数据只有一个&#xff0c;缺点&am…
阅读更多...
2020年五一杯数学建模B题基于系统性风险角度的基金资产配置策略分析解题全过程文档及程序

2020年五一杯数学建模B题基于系统性风险角度的基金资产配置策略分析解题全过程文档及程序

2020年五一杯数学建模 B题 基于系统性风险角度的基金资产配置策略分析 原题再现 近年来&#xff0c;随着改革开放程度的不断提高&#xff0c;我国经济运行中的各种风险逐渐暴露并集中传导和体现于金融领域。党的“十九大”报告提出“守住不发生系统性金融风险的底线”要求&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023