探索数据结构:单链表的实战指南


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯,先赞后看哦~🎈🎈

所属专栏:数据结构与算法
贝蒂的主页:Betty‘s blog

前言

在上一章节中我们讲解了数据结构中的顺序表,知道了顺序表的空间是连续存储的,这与数组非常类似,为我们随机访问数据提供了便利的条件。但是同时当插入数据时可能存在移动数据与扩容的情况,这大大增加我们的时间与空间成本。为了解决这个问题,就要学习我们今天要讲解的链表。

1. 什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。与顺序表不同,链表的存储数据在内存是随机分布的。

2. 链表的分类

链表的种类多种多样,其中最常见的有八种,它们大致可以分为三类:

2.1 单向或者双向

2.2 带不带头节点

2.3 循环不循环

本专栏将选择其中两种常见链表进行讲解,那就是无头单向非循环链表与与带头双向循环链表,这两种优点主要有:

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

3. 单链表的功能

单链表的主要功能有以下几个:

  1. 打印单链表中的数据。
  2. 对单链表进行头插(开头插入数据)。
  3. 对单链表进行头删(开头删除数据)。
  4. 对单链表进行尾插(末尾插入数据)。
  5. 对单链表进行尾删(末尾删除数据)。
  6. 对单链表进行查找数据。
  7. 对单链表数据进行修改。
  8. 任意位置的删除和插入数据。
  9. 销毁单链表。

4. 单链表的定义

单链表的结点定义方式与我们以往定义的方式都不同,它是一个结构体中包含两个成员。一个是存储数值,一个存放下一个结点的地址。

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

实际内存存储结构:

5. 单链表功能实现

5.1 打印单链表

打印链表需要对函数传参指向链表的指针,首先为了保证链表不为空(NULL),需要对其进行断言。

(1) 代码实现
void PrintSList(SListNode* plist)
{SListNode* cur = plist;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
(2) 复杂度分析
  • 时间复杂度:因为需要遍历整个链表,显然时间复杂度为O(N)。
  • 空间复杂度:打印链表不需要格外的空间,所以空间复杂度为O(1).

5.2 单链表头插

(1) 创建结点

单链表每次插入都需要插入一个节点,所以我们最好写一个创建节点的函数方便后续调用。

SListNode* SListCreatNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail:");return;}newnode->data = x;newnode->next = NULL;return newnode;
}
(2) 头插代码实现

单链表的头插与顺序表头插最大的不同就是单链表传参需要二级指针。因为头插数据需要改变一级指针plist的指向,而形参的改变无法影响实参,所以需要二级指针才能改变一级指针plist的指向。

void SListPushFront(SListNode** plist, SLTDataType x)
{assert(plist);SListNode* newnode = SListCreatNode(x);newnode->next = *plist;*plist = newnode;
}
(3) 复杂度分析
  • 时间复杂度:不需要额外时间的消耗,时间复杂度为O(1)。
  • 空间复杂度:固定创造一个节点,空间复杂度为O(1)。

5.3 单链表头删

头删与头插类似,都可能需要改变plist的指向,所以也需要二级指针。并且也需要防止链表为空的情况发生。

(1) 代码实现
void SListPopFront(SListNode** plist)
{assert(plist);assert(*plist);SListNode* cur = (*plist)->next;free(*plist);*plist = cur;
}
(2) 复杂度分析
  • 时间复杂度:不需要额外时间的消耗,时间复杂度为O(1)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

5.4 单链表尾插

当链表为空时,单链表尾插就会变成单链表头插,也需要改变plist的指向。其余情况即可通过循环寻找尾节点。

(1) 代码实现
void SListPushBack(SListNode** plist, SLTDataType x )
{assert(plist);if (*plist== NULL){*plist = SListCreatNode(x);}else{SListNode* ptail = *plist;while (ptail->next){ptail = ptail->next;}ptail->next = SListCreatNode(x);}
}
(2) 复杂度分析
  • 时间复杂度:需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:固定创造一个节点,空间复杂度为O(1)。

5.5 单链表尾删

与单链表尾插类似,当链表只有一个头结点时需要将plist置为空,所以也需要二级指针。并且也需要防止链表为空的情况发生。

(1) 代码实现
void SListPopBack(SListNode** plist)
{assert(plist);assert(*plist);//防止链表为空if ((*plist)->next == NULL){free(*plist);*plist = NULL;}else{SListNode* ptail = *plist;while (ptail->next->next){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;}	
}
(2) 复杂度分析
  • 时间复杂度:需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

5.6 单链表的查找

如果找到就返回这个节点的地址,否则就返回空指针NULL

(1) 代码实现
SListNode* SListSearch(SListNode* plist, SLTDataType x)
{assert(plist);SListNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
(2) 时间复杂度
  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

5.6 单链表的修改

单链表的修改可以与查找配套使用。

(1) 代码实现
void SListModify(SListNode*plist, SListNode* pos, SLTDataType x)
{assert(plist);assert(pos);SListNode* cur = plist;while (cur){if (cur == pos){cur->data = x;break;}cur = cur->next;}
}
(2) 复杂度分析
  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

5.7 单链表任意位置的插入

(1) 代码实现

某个位置之前插入,当链表为空或者在头节点插入时使用头插。

void SListInsertF(SListNode** plist, SListNode* pos, SLTDataType x)
{assert(plist);assert(pos);if (*plist == pos || *plist == NULL){SListPushFront(plist, x);//头插}else{SListNode* newnode = SListCreatNode(x);SListNode* prev = *plist;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

某个位置之后插入,当链表为空或者在尾节点插入时使用尾插。

void SListInsertB(SListNode** plist, SListNode* pos, SLTDataType x)
{assert(plist);assert(pos);if (*plist == NULL||pos->next==NULL){SListPushBack(plist, x);//尾插}else{SListNode* tmp = pos->next;SListNode* newnode = SListCreatNode(x);pos->next = newnode;newnode->next = tmp;}
}
(2) 复杂度分析
  • 时间复杂度:无论向前插入还是向后插入都可能需要遍历整个链表,所以时间复杂度为O(N)。
  • 空间复杂度:固定创造一个节点,空间复杂度为O(1)。

5.8 任意位置的删除

任意位置的删除需要提前保存好前一个节点与后一个节点的位置。

(1) 代码实现
void SListErase(SListNode** plist, SListNode* pos)
{assert(plist);assert(*plist);assert(pos);if (*plist == pos){SListPopFront(plist);//头删}SListNode* prev = *plist;while (prev->next!=pos){prev = prev->next;}SListNode* tmp = pos->next;prev->next = tmp;free(pos);pos = NULL;
}
(2) 复杂度分析
  • 时间复杂度:可能需要遍历整个链表,所以时间复杂度为O(N)。
  • 空间复杂度:固定创造一个节点,空间复杂度为O(1)。

5.9 销毁链表

销毁链表需要依次遍历释放节点。

(1) 代码实现
void SListDestroy(SListNode** plist)
{assert(plist);assert(*plist);SListNode* cur = *plist;while (cur){SListNode* tmp = cur->next;free(cur);cur =tmp;}*plist = NULL;//防止野指针
}
(2) 复杂度分析
  • 时间复杂度:需要遍历整个链表,所以时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

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

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

相关文章

【校园导航小程序】2.0版本 静态/云开发项目 升级日志

演示视频 【校园导航小程序】2.0版本 静态/云开发项目 演示 首页 重做了首页,界面更加高效和美观 校园指南页 新增了 “校园指南” 功能,可以搜索和浏览校园生活指南 地图页 ①弃用路线规划插件,改用SDK开发包。可以无阻通过审核并发布…

吴恩达机器学习-可选实验室:特征工程和多项式回归(Feature Engineering and Polynomial Regression)

文章目录 目标工具特征工程和多项式回归概述多项式特征选择功能备用视图扩展功能复杂的功能 恭喜! 目标 在本实验中,你将:探索特征工程和多项式回归,它们允许您使用线性回归的机制来拟合非常复杂,甚至非常非线性的函数。 工具 您将利用在以…

【vue2基础教程】vue指令

文章目录 前言一、内容渲染指令1.1 v-text1.2 v-html1.3 v-show1.4 v-if1.5 v-else 与 v-else-if 二、事件绑定指令三、属性绑定指令总结 前言 Vue.js 是一款流行的 JavaScript 框架,广泛应用于构建交互性强、响应速度快的现代 Web 应用程序。Vue 指令是 Vue.js 中…

cf火线罗技鼠标宏最细教程(鬼跳,上箱,一键顺,usp速点,雷神三连发及压枪,AK火麒麟压枪.lua脚本)

一.前言 因为我发现火线的鼠标宏非常多,想着自己也有罗技鼠标,看能不能自己写一写让游玩的时候更方便操作一些,可能不一定有什么帮助,但也是一个学习的过程,下面就把我自己的心得和代码详细的记录下来,好多…

注意力机制(代码实现案例)

学习目标 了解什么是注意力计算规则以及常见的计算规则.了解什么是注意力机制及其作用.掌握注意力机制的实现步骤. 1 注意力机制介绍 1.1 注意力概念 我们观察事物时,之所以能够快速判断一种事物(当然允许判断是错误的), 是因为我们大脑能够很快把注意力放在事物…

C语言从入门到精通 第十一章(文件操作)

写在前面: 本系列专栏主要介绍C语言的相关知识,思路以下面的参考链接教程为主,大部分笔记也出自该教程。除了参考下面的链接教程以外,笔者还参考了其它的一些C语言教材,笔者认为重要的部分大多都会用粗体标注&#xf…

算法刷题day25:多路归并

目录 引言概念一、鱼塘钓鱼二、技能升级三、序列 引言 关于这个多路并归蓝桥杯考的不是很多,如果要出的话,可能模型都会差不多,因为不会出太难的题,难题基本上都是贪心、DP之类的,所以好好刷题刷熟练就行了&#xff0…

Vue事件处理:.passive修饰符与应用场景

.passive修饰符 passive这个修饰符会执行默认方法。你们可能会问,明明默认执行为什么会设置这样一个修饰符。这就要说一下这个修饰符的本意了。 浏览器只有等内核线程执行到事件监听器对应的JavaScript代码时,才能知道内部是否会调用preventDefa…

一次电脑感染Synaptics Pointing Device Driver病毒的经历,分享下经验

没想到作为使用电脑多年的老司机也会电脑中病毒,周末玩电脑的时候突然电脑很卡,然后自动重启,奇怪,之前没出现这个情况。 重启后电脑开机等了几十秒,打开任务管理器查看开机进程,果然发现有个Synaptics Po…

【计网】TCP协议安全与风险:深入探讨网络通信的基石

🍎个人博客:个人主页 🏆个人专栏:Linux ⛳️ 功不唐捐,玉汝于成 目录 🌐前言 🔒正文 TCP (Transmission Control Protocol): UDP (User Datagram Protocol): HTTP (Hypertext Transfer …

【动态规划.3】[IOI1994]数字三角形 Number Triangles

题目 https://www.luogu.com.cn/problem/P1216 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7→3→8→7→5 的路径产生了最大权值。 分析 这是一个动态规划…

3.8 动态规划 背包问题

一.01背包 46. 携带研究材料(第六期模拟笔试) (kamacoder.com) 代码随想录 (programmercarl.com) 携带研究材料: 时间限制:5.000S 空间限制:128MB 题目描述: 小明是一位科学家,他需要参加一场重要的国际科学大会…

杨辉三角(附html,Python,c++杨辉三角代码)

1、前言 杨辉三角很早学编程就知道,但不知道杨辉是古人! 一次偶然的机会,和杨辉三角对上了眼神——杨辉!究竟你是怎么发现杨辉三角的呢? 于是经过了长达3个月锲而不舍的探究。 终究也没发现自己想要的最终结果。 …

【YOLO v5 v7 v8 v9小目标改进】AFPN 渐进式特征金字塔网络:解决多尺度特征融合中,信息在传递过程丢失

AFPN 渐进式特征金字塔网络:解决多尺度特征融合中,信息在传递过程丢失 提出背景AFPN 多尺度特征金字塔 非邻近层次的直接特征融合 自适应空间融合操作 小目标涨点YOLO v5 魔改YOLO v7 魔改YOLO v8 魔改YOLO v9 魔改 提出背景 论文:https:…

数据库原理实验课(1)

目录 实验内容 安装头歌中的相关内容 具体过程 完结撒花~ 我也是第一次接触oracle的相关软件和操作,所以是一次傻瓜式教学记录 实验内容 安装头歌中的相关内容 具体过程 这是我在百度网盘中下载解压出来的oracle文件夹内的全部内容(可能有因为安装完…

神州大地人类来源猜想

在公元前2000年以前,伟大的中华民族还是石器时代,我们有很多美好的神话和传说,三皇五帝就是这个时代伟大部落或者部落首领的故事。 关于人类的历史,从基因学上最新的研究成果大概是这样的,虽然从300万年前就诞生了人类…

[Buuctf] [MRCTF2020]Transform

1.查壳 64位exe文件,没有壳 2.用64位IDA打开 找到主函数,F5查看伪代码 从后往前看,有一个判断语句,是两个数组进行比较的,我们双击byte_40F0E0查看里面的内容 所以能够推出byte_414040的内容,byte_4140…

Window下编写的sh文件在Linux/Docker中无法使用

Window下编写的sh文件在Linux/Docker中无法使用 一、sh文件目的1.1 初始状态1.2 目的 二、过程与异常2.1 首先获取标准ubuntu20.04 - 正常2.2 启动ubuntu20.04容器 - 正常2.3 执行windows下写的preInstall文件 - 报错 三、检查和处理3.1 评估异常3.2 处理异常3.3 调整后运行测试…

手写分布式配置中心(三)增加实时刷新功能(短轮询)

要实现配置自动实时刷新,需要改造之前的代码。代码在https://gitee.com/summer-cat001/config-center​​​​​​​ 服务端改造 服务端增加一个版本号version,新增配置的时候为1,每次更新配置就加1。 Overridepublic long insertConfigDO(…

06. Nginx进阶-Nginx代理服务

proxy代理功能 正向代理 什么是正向代理? 正向代理(forward proxy),一个位于客户端和原始服务器之间的服务器。 工作原理 为了从原始服务器获取内容,客户端向代理发送一个请求并指定目标(即原始服务器…