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

news/2024/12/18 1:45:29/

引言:

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

单链表

一. 初识单链表

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. 综上所述,顺序表和链表各有千秋,这也是我们为什么两个都要学的原因,所以今后在遇到问题时,用哪个合适就用哪个就可以了


http://www.ppmy.cn/news/1556009.html

相关文章

计算机网络知识点全梳理(二.HTTP知识点总结)

目录 HTTP基本概念 HTTP优缺点 HTTP优点(1.1) HTTP缺点 HTTP与HTTPS HTTP 与 HTTPS 的区别 HTTPS 解决 HTTP 的哪些安全问题? HTTPS 如何解决安全问题? HTTPS 连接建立的过程: HTTP/1.1、HTTP/2、HTTP/3 演…

C++之一:基础

相关代码:cpp/month12/test_12/main.cpp Hera_Yc/bit_C_学习 - 码云 - 开源中国 C面向对象的语言 C兼容C:因此,C亦可以是面向过程的语言。 C的基础知识是特别碎的,但这并不意味着这些知识并不重要,这些碎片化的内容…

[Effective C++]条款33 继承, 重载与作用域

本文初发于 “天目中云的小站”,同步转载于此。 条款33 : 避免遮掩继承而来的名称 本条款并非和继承有关, 而是在讨论由继承引发的作用域问题, 其有可能破坏条款32所确定的法则, 因此我们在其之后介绍本条款。 我们知道在不同作用域下如果有相同名称的事物, 无论其功…

海康威视监控web实时预览解决方案

海康威视摄像头都试rtsp流,web页面无法加载播放,所以就得转换成web页面可以播放的hls、rtmp等数据流来播放。 一:萤石云 使用萤石云平台,把rtsp转化成ezopen协议,然后使用组件UIKit 最佳实践 萤石开放平台API文档 …

使用 imageio 库轻松处理图像与视频

使用 imageio 库轻松处理图像与视频 imageio 是一个 Python 库,用于读取和写入多种图像和视频格式。它功能强大、易于使用,广泛应用于图像处理、视频编辑和数据可视化等领域。本篇文章将介绍 imageio 的基础功能、常见用法以及高级操作。 一、安装 imag…

亚远景-ASPICE实施策略:构建高效汽车软件质量保证体系

ASPICE(Automotive SPICE)是一个针对汽车行业软件过程改进的国际标准,它旨在提高汽车软件的质量和可靠性。实施ASPICE通常需要一个系统性的策略,以下是一些关键的步骤和策略: 一、了解ASPICE 基本概念与要求&#xff…

智能家居WTR096-16S录放音芯片方案,实现语音播报提示及录音留言功能

前言: 在当今社会的高速运转之下,夜幕低垂之时,许多辛勤工作的父母尚未归家。对于肩负家庭责任的他们而言,确保孩童按时用餐与居家安全成为心头大事。此时,家居留言录音提示功能应运而生,恰似家中的一位无形…

鸿蒙NEXT开发案例:九宫格随机

【引言】 在鸿蒙NEXT开发中,九宫格抽奖是一个常见且有趣的应用场景。通过九宫格抽奖,用户可以随机获得不同奖品,增加互动性和趣味性。本文将介绍如何使用鸿蒙开发框架实现九宫格抽奖功能,并通过代码解析展示实现细节。 【环境准…