《数据结构之美-- 单链表》

引言:

首先由上次我们实现的顺序表聊起,我们在实现顺序表的时候会发现,在每次插入数据时当空间不够时就会涉及到扩容,而顺序表的扩容一般都是呈二倍的形式来进行,因此这就有可能造成空间的浪费,那该如何解决这个问题呢,接下来要学到的链表就可以完美地解决这个缺点。

单链表

一. 初识单链表

1. 概念与结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据结构的逻辑顺序是通过链表中的指针链接次序实现的。
所以说单链表也是线性表的一种

2. 直观感受链表

在这里插入图片描述
其实我们可以由上图中的火车来类比链表,火车由火车头与一节一节的车厢链接起来,就组成了火车这个整体,其实链表也是像火车这样,是由一个一个的节点来链接起来的,火车的各节车厢是由挂钩链接的,而链表中的各个节点是由指针来链接的。

3. 链表的形式

(1)画图理解:

在这里插入图片描述

(2)代码实现:

在这里插入图片描述

二. 手搓单链表

1. 手动实现链表

在这里插入图片描述

2. 打印链表实现

(1)声明:--------------------------------------------------------------

在这里插入图片描述

(2)逻辑实现:

在这里插入图片描述

解析:打印链表,避免不了要遍历链表,所以这里的打印函数要将链表的首节点传过去,不然无法遍历链表,并且这里我们希望后面再找首节点的时候可以直接找到,所以这里在遍历链表时候我们定义了另外一个指针pcur来代替首节点来遍历链表,这里while循环的条件就是利用了链表最后一个节点的指针域为空的特性来实现的遍历,每次循环之后让指针移动到下一个节点,依次完成打印。

(3)测试:

在这里插入图片描述

三. 链表各项功能的实现

1. 尾插

(1)声明:

在这里插入图片描述

(2)思路整理:

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

(3)代码实现:
申请新节点

在这里插入图片描述
这里我们把申请新节点封装成了一个函数,方便后面我们在插入数据时进行直接调用

尾插实现

在这里插入图片描述
注意: 这里需要注意的是因为在逻辑实现中我们会改变指针的指向,因此这里必须为传址操作,因此这里传过去的是二级指针

(4)测试:

在这里插入图片描述

通过测试我们可以发现达到了尾插的效果

2. 头插

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3)代码实现:

在这里插入图片描述
写到这里,有同学可能会有一些疑惑:你这不是只写了第二种情况的逻辑吗?为什么说已经写完了呢? 其实这个逻辑就同时满足了这两种情况,下面我们来看看

在这里插入图片描述

通过上图,相信同学们就对头插逻辑实现理解透彻了吧

(4)测试:

![在这里插入图片描述](https://i-blog.csdnimg.cn/direc在这里插入图片描述
通过测试,可以看到我们的头插实现了预期的效果

3. 尾删

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3)逻辑实现:

在这里插入图片描述

(4)测试:

在这里插入图片描述
通过测试我们可以看到我们的尾删实现了预期的效果

4. 头删

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3)代码实现:

在这里插入图片描述

(4)测试:

在这里插入图片描述
*通过运行结果我们可以看到实现了头删的效果

5. 查找

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3)代码实现:

在这里插入图片描述

(4) 测试:

在这里插入图片描述
通过测试我们可以直观地看到我们的查找实现了预期效果

6. 在指定位置之前插入数据

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3)代码实现:

在这里插入图片描述

(4) 测试:

在这里插入图片描述

通过测试结果我们可以看到我们预期的结果已经实现了

7. 在指定位置之后插入数据

(1) 声明:

在这里插入图片描述

这里要注意这里的参数少了一个,因为在POS之后插入数据的话并不会影响POS之前的节点,就没必要再传原链表的首节点了

(2)思路整理:

在这里插入图片描述
但其实这里也会出现尾插的情况,但是也是满足这种逻辑的

(3)代码实现:

在这里插入图片描述

(4)测试:

在这里插入图片描述
通过测试我们看到特定位置之后插入数据也达到了预期的效果

8. 删除POS节点

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3)代码实现:

在这里插入图片描述

(4)测试:

在这里插入图片描述
通过代码运行结果我们可以看到达到了我们预期的效果

9. 删除POS之后的节点

(1) 声明:

在这里插入图片描述
这里注意这里的参数就只有一个了,因为要删除的是POS之后的数据,因此就不会用到头结点了

(2)思路整理:

在这里插入图片描述
分析完之后可能有同学还会担心会不会出现尾删的情况,其实尾删也可以有上述分析的逻辑来实现

(3) 代码实现:

在这里插入图片描述

(4)测试:

在这里插入图片描述

通过上面测试我们可以看到实现了删除POS位置之后的数据的效果

10. 链表的销毁

(1)声明:

在这里插入图片描述

(2)思路整理:

在这里插入图片描述

(3) 代码实现:

在这里插入图片描述

(4)测试:
销毁之前:

在这里插入图片描述

销毁之后:

在这里插入图片描述

关于顺序表和链表的思考

1. 顺序表中中间/头部的插入和删除的时间复杂度为O(n) 而在链表中的时间复杂度为O(1)
2. 顺序表的增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗,但是链表不需要频繁增容
3. 增容一般是呈两倍的形式增长,势必会有一定的空间浪费,而链表中是插入几个数据就申请几个节点的空间,不会存在空间的浪费
4. 但是综上几点也不能证明链表一定优于顺序表,比如在顺序表中的尾插/尾删的时间复杂度都为o(1),而在链表中的时间复杂度为o(n)
5. 综上所述,顺序表和链表各有千秋,这也是我们为什么两个都要学的原因,所以今后在遇到问题时,用哪个合适就用哪个就可以了

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

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

相关文章

NVR小程序接入平台/设备EasyNVR深度解析H.265与H.264编码视频接入的区别

随着科技的飞速发展和社会的不断进步,视频压缩编码技术已经成为视频传输和存储中不可或缺的一部分。在众多编码标准中,H.265和H.264是最为重要的两种。今天我们来将深入分析H.265与H.264编码的区别。 一、H.265与H.264编码的区别 1、比特率与分辨率 H.…

JPG 转 PDF:免费好用的在线图片转 PDF 工具

JPG 转 PDF:免费好用的在线图片转 PDF 工具 在日常工作和生活中,我们经常需要将图片转换为 PDF 格式。无论是制作电子文档、准备演示材料,还是整理照片集,将图片转换为 PDF 都是一个常见的需求。今天为大家介绍一款完全免费、无需…

RabbitMQ 整合 SpringBoot

概述 大多应用中,可通过消息服务中间件来提升系统异步通信、扩展解耦能力、流量削峰消息服务中两个重要概念: 消息代理(`message broker`)和目的地(`destination`) 当消息发送者发送消息以后,将由消息代理接管,消息代理保证消息传递到指定目的地。消息队列主要有两种形…

Docker的初识

目录 1. 容器技术发展史1.1 Jail 时代1.2 云时代1.3 云原生时代1.3.1 Google & Docker 竞争1.3.2 k8s 成为云原生事实标准 2. 虚拟化和容器化的概念2.1 什么是虚拟化、容器化2.2 为什么要虚拟化、容器化?2.3 虚拟化实现方式2.3.1 应用程序执行环境分层2.3.2 虚拟…

MySQL 索引解析:让查询速度飙升

1.前言 之前几篇文章,小编和大家分享了mysql innodb的内存结构,这次小编准备用两篇文章来和大家分享下mysql innodb的索引: mysql的基础知识 和 基于索引的sql优化 。 2. 什么是索引? 定义:索引是数据库中用于快速查找数据的机…

记录 idea 启动 tomcat 控制台输出乱码问题解决

文章目录 问题现象解决排查过程1. **检查 idea 编码设置**2. **检查 tomcat 配置**3.检查 idea 配置文件4.在 Help 菜单栏中,修改Custom VM Options完成后保存,并重启 idea 问题现象 运行 tomcat 后,控制台输出乱码 解决排查过程 1. 检查 id…

MySQL有哪些高可用方案?

大家好,我是锋哥。今天分享关于【MySQL有哪些高可用方案?】面试题。希望对大家有帮助; MySQL有哪些高可用方案? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 MySQL 高可用方案旨在确保数据库系统的高可靠性、低宕机时间、以及在硬件故障…

基于STM32的火灾烟雾报警器设计开题报告

开题报告 题目:基于STM32的火灾烟雾报警器Proteus仿真设计 一、研究背景与意义 随着现代城市化进程的加快,火灾安全问题日益凸显,火灾的早期预警对于减少人员伤亡和财产损失至关重要。传统的火灾报警系统往往依赖于烟雾或温度的单一检测&a…

《机器学习》3.7-4.3end if 启发式 uci数据集klda方法——非线性可分的分类器

目录 uci数据集 klda方法——非线性可分的分类器 计算 步骤 1: 选择核函数 步骤 2: 计算核矩阵 步骤 4: 解广义特征值问题 と支持向量机(svm) 目标: 方法: 核技巧的应用: 区别: 使用 OvR MvM 将…

【蓝桥杯选拔赛真题93】Scratch青蛙过河 第十五届蓝桥杯scratch图形化编程 少儿编程创意编程选拔赛真题解析

目录 Scratch青蛙过河 一、题目要求 编程实现 二、案例分析 1、角色分析 2、背景分析 3、前期准备 三、解题思路 1、思路分析 2、详细过程 四、程序编写 五、考点分析 六、推荐资料 1、入门基础 2、蓝桥杯比赛 3、考级资料 4、视频课程 5、python资料 Scratc…

基于Qwen2-VL模型针对LaTeX OCR任务进行微调训练 - 多图推理

基于Qwen2-VL模型针对LaTeX OCR任务进行微调训练 - 多图推理 flyfish 基于Qwen2-VL模型针对LaTeX_OCR任务进行微调训练_-_LoRA配置如何写 基于Qwen2-VL模型针对LaTeX_OCR任务进行微调训练_-_单图推理 基于Qwen2-VL模型针对LaTeX_OCR任务进行微调训练_-_原模型_单图推理 基于Q…

好玩的汇编编译器NASM:一款基于x86架构的汇编与反汇编软件

好玩的汇编编译器NASM This is the project webpage for the Netwide Assembler (NASM), an asssembler for the x86 CPU architecture portable to nearly every modern platform, and with code generation for many platforms old and new. Netwide Assembler(…

Bootstrap-HTML(六)Bootstrap按钮

Bootstrap按钮与按钮组 前言一、Bootstrap按钮(一)、内置按钮样式(二)、按钮边框设置(三)、按钮尺寸调整(四)、块级按钮创建(五)、活动 / 禁用按钮设置 二、B…

储能技术方案综述

全球电量浪费现状 根据国际可再生能源机构(IRENA)和其他研究机构的数据,全球范围内光伏和风电的电量浪费主要表现为发电弃风弃光、输电损耗和储能不足等方面。 弃风弃光现象 弃风率:指风电场在有风时未能发出的电量占总发电量的比…

深入探索:createThread与cancelThread的用法及实例

在多线程编程领域,线程的创建与管理是核心技能之一。本文将详细介绍两个关键函数:createThread(用于创建新线程)和cancelThread(用于取消已存在的线程),并通过具体实例展示它们的用法。需要注意的是,不同的编程语言和线程库可能有不同的API设计,但基本概念是相通的。本…

Java基础学习:java常用启动命令

一、java -jar 1、系统属性传递 使用形式:java -DpathD:\jacoco -jar 获取方式:System.getProperties() 2、系统参数传递 使用形式:java -jar application.jar --jacocoPathD:\tomcat 获取方式:通过启动方法入口main的参数arg…

guava 整合springboot 自定义注解实现接口鉴权调用保护

文章目录 一、简要概述二、实现过程1. pom引入依赖2. 自定义注解3. 定义切面4. 定义权限检查逻辑 三、注解使用四、运行结果五、源码放送 一、简要概述 Guava Cache是一个全内存的本地缓存实现,它提供了线程安全的实现机制。我们借助expireAfterWrite过期时间设置和…

nginx 部署 ModSecurity3

一、查看本地nginx版本 nginx是yum安装的 # nginx -v nginx version: nginx/1.26.2 二、安装依赖工具 # yum install -y gcc-c flex bison yajl lmdb lua curl-devel curl GeoIP-devel zlib-devel pcre-devel pcre2-devel libxml2-devel ssdeep-devel libtool autoconf aut…

threejs——无人机概念切割效果

主要技术采用着色器的切割渲染,和之前写的风车可视化的文章不同,这次的切割效果是在着色器的基础上实现的,并新增了很多可调节的变量,兄弟们,走曲儿~ 线上演示地址,点击体验 源码下载地址,点击下载 正文 从图中大概可以看出以下信息,一个由线组成的无人机模型,一个由…

【LeetCode】每日一题 2024_12_13 K 次乘运算后的最终数组 I(暴力)

前言 每天和你一起刷 LeetCode 每日一题~ 小聊两句 1、今天是 12.13 南京大屠杀国家公祭日。铭记历史,勿忘国耻。 2、今天早上去看了 TGA 年度游戏颁奖,小机器人拿下了年度最佳游戏,所有人都震惊了,大伙纷纷问到,谁…