【数据结构】单链表的层层实现!! !

news/2024/4/19 12:55:57/文章来源:https://blog.csdn.net/2301_79448270/article/details/136308397

在这里插入图片描述
关注小庄 顿顿解馋(●’◡’●)

上篇回顾
我们上篇学习了本质为数组的数据结构—顺序表,顺序表支持下标随机访问而且高速缓存命中率高,然而可能造成空间的浪费,同时增加数据时多次移动会造成效率低下,那有什么解决之法呢?这就得引入我们链表这种数据结构

文章目录

  • 一.何为链表
    • 🏠 链表概念
    • 🏠 链表的分类![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/6102a54bc82c4f25abb7816d1d2d0ebc.png)
  • 二.单链表的实现
    • 🏠 链表的打印
    • 🏠 链表的头插和尾插
    • 🏠 链表的尾删和头删
    • 🏠 链表指定位置的插入和删除
    • 🏠 链表的查找
    • 🏠 链表的销毁
    • `注: 这里要保存好下一个结点地址,销毁后就能继续遍历`
  • 三.单链表的分析以及与顺序表的比较
    • 🏠 单链表的优缺点
    • 🏠 单链表与顺序表的比较

一.何为链表

🏠 链表概念

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

特点:物理结构不一定连续,逻辑结构连续
在这里插入图片描述
我们的链表结构类似我们的火车,有头有尾,中间每个结点被有序链接;与火车不同的是,链表的结点可能不是紧挨着的。

在这里插入图片描述

类似这样,我们可以得出:
1.每个结点由数据和下一结点地址两部分组成,而每个结点构成了一个链表。
2.每个结点保存的是下一个结点的地址,这样就能找到下一个结点,最后为空就停止
3.每个结点的地址不是连续的,可以体现出链表的物理结构不一定连续

注:我们的结点一般是在堆区开辟的,因为此时你在程序结束前不free就会一直存在这块空间,同时可根据需要灵活申请结点存数据。

这样我们就可以用一个结构体封装每个结点:

typedef int Datatype;
typedef struct ListNode
{Datatype x;struct ListNode* next;
}Node;

注: 这里我们可以用typedef来重命名我们要存储的数据类型,这样对于不同数据的操作我们只要改typedef即可。

🏠 链表的分类在这里插入图片描述

我们根据链表三个特点:1.带头不带头 2.单向还是双向 3.循环还是不循环 组合成了如上的8种链表
本篇博客,我们要实现的是单向不带头不循环链表(单链表),至于什么是带头,双向,循环我们下回双链表再进行讲解


二.单链表的实现

无头+单向+不循环链表的增删差改

🏠 链表的打印

  • 链表数据的打印

这个接口就很好的体现了结点结构保存指针的妙处了~

//链表的打印
void SLTPrint(Node* phead)
{asser(phead);Node* cur = phead;while (cur){printf("%d ", cur->x);cur = cur->next;}
}

🏠 链表的头插和尾插

  • 链表的尾插

在这里插入图片描述
对于链表的尾插要注意几个问题:1.申请新结点 2.链表是否为空

解决方法:1.对于链表为空,直接让申请的新节点作为头节点 2.对于不为空的链表,首先要找到尾结点,再进行插入 3.对于申请新节点,我们后续的头插也要使用我们可以封装成一个接口,同时结点在堆区申请,调用完接口就不会释放了。

//申请新节点
Node* BuyNode(Datatype x)
{Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc failed");return;}newnode->next = NULL;newnode->x = x;return newnode;
}void SLTPushBack(Node** pphead, Datatype x)
{assert(pphead);//申请新节点Node* newnode = BuyNode(x);//链表为空if (NULL == *pphead){*pphead = newnode;return;}//链表不为空:1.找尾巴结点2.插入新节点Node* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

思考:这里为什么传二级指针?如果不传二级指针呢?

void SLTNPushBack(Node* pphead, Datatype x)
{//申请新节点Node* newnode = BuyNode(x);//链表为空if (NULL == pphead){pphead = newnode;return;}//链表不为空:1.找尾巴结点2.插入Node* ptail = pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}
int main()
{Node* n1 = NULL;SLTNPushBack(n1,1);return 0;
}

在这里插入图片描述
经过观察传一级指针版本的调用前后,我们发现n1这个指针变量存储的值并没发生改变,究其原因如下图
在这里插入图片描述

  • 链表的头插
    ,在这里插入图片描述
    *对于链表的头插要注意的问题:1.申请新节点 2.链表释放为空 *

解决方法:1.链表为空时,申请的新结点作为头结点 2.链表不为空时,让newnode->next指向原来头节点,再让newnode成为新的头节点。

void SLTPushFront(Node** pphead, Datatype x)
{assert(pphead);//申请新节点Node* newnode = BuyNode(x);//链表为空if (NULL == *pphead){*pphead = newnode;return;}newnode->next = *pphead;*pphead = newnode;
}

🏠 链表的尾删和头删

  • 链表的尾删
    在这里插入图片描述
    对于链表的尾删,我们需要分三种情况!

1.链表为空时此时删不了直接退出
2.链表只有一个结点时,释放头节点,置phead为空
3.链表有多个结点时,我们需要遍历链表找到尾结点的前置结点,先释放尾节点再将前置结点的next置为空
注:不能先将前置结点的next置为空,再释放尾结点,此时就找不到尾结点的地址了。

//链表的尾删和头删
void SLTPopBack(Node** pphead)
{assert(pphead);assert(*pphead);//判断链表不为空if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}Node* pre = *pphead;while (pre->next->next){pre = pre->next;}free(pre->next);pre->next = NULL;
}
  • 链表的头删

在这里插入图片描述
对于链表的头删,分为两种情况就可以了,因为有了phead很方便~

1.链表为空时,删不了直接断言下
2.链表不为空时,记录头节点的下一个位置,先释放头节点,再更换phead指向的位置

注:这里也不能先更新phead再释放头结点

void SLTPopFront(Node** pphead)
{assert(pphead);assert(*pphead);Node* pNext = (*pphead)->next;free(*pphead);*pphead = pNext;
}

🏠 链表指定位置的插入和删除

在这里插入图片描述

1.链表为空时,无法插入
2.pos位置结点刚好是头结点,直接头插或头删
3.pos位置结点不是头节点,需要找到pos位置的前置结点,记录位置。

void NodeInpos(Node** pphead, Node* pos, Datatype x)
{assert(pphead);//pos不为空 -》 链表一定不能为空assert(pos);assert(*pphead);//建立一个新节点Node* newnode = BuyNode(x);//pos刚好是头结点的情况if (*pphead == pos){//运用头插NodeinFront(pphead,x);return;}//pos刚好不是头结点//1.先找出pos前面的结点pre  2.newnode->next = pre->next 3.pre-<next = newnodeNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}newnode->next = pre->next;pre->next = newnode;
}void NodeDelpos(Node** pphead, Node* pos)
{assert(pphead);assert(pos);assert(*pphead);//pos刚好是第一个结点 执行头删if (*pphead == pos){NodeDelFront(pphead);return;}//pos不是第一个结点 1.先找到那个pos前面结点pre 2.pre->next = pos->next 3.freeNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = pos->next;free(pos);pos = NULL;
}

🏠 链表的查找

Node* NodeFind(Node** phead, Datatype x)
{assert(phead);//遍历链表Node* pcur = *phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//找不到则返回NULL
}

这里建议用一个临时变量来遍历~

🏠 链表的销毁

void NodeDestroy(Node** pphead)
{assert(pphead);assert(*pphead);//1.创一个临时变量存pcur->next的地址Node* pcur = *pphead;while (pcur){Node* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

注: 这里要保存好下一个结点地址,销毁后就能继续遍历

三.单链表的分析以及与顺序表的比较

🏠 单链表的优缺点

通过实现我们的单链表,我们发现单链表有以下优点

1.单链表不存在空间浪费(根据需求灵活在堆上申请新结点)
2.单链表的任意插入和删除效率高
(分析: 这里是已经确定插入的位置,对于链表只需改变指针的指向就能实现插入和删除,时间复杂度是O(1),而数组插入和删除需要遍历数组,时间复杂度是O(N)

单链表也不是万能的,它在一些应用场景也发挥不出来作用

1.不支持随机访问
2.缓存命中率低
3.查找效率低

总结:链表适用于频繁任意插入和删除的场景,不适用于随机访问和查找

🏠 单链表与顺序表的比较

单链表顺序表
物理空间不一定连续物理空间一定连续
不支持随机访问支持下标随机访问
插入和删除效率高 O(1)插入和删除效率低 O(N)
缓存命中率低缓存命中率高
无空间的浪费可能造成数据丢失和空间浪费
缓存利用率高

综上 我们可以根据场景需求选择不同的结构,灵活运用数据~


本次分享到这结束了,下篇我们将讲解双向链表,不妨来个一键三连捏

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

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

相关文章

特种车日常检修VR虚拟互动培训软件节省大量的教学资源和成本

随着科技的不断发展&#xff0c;虚拟现实(VR)技术已经逐渐融入了各行各业&#xff0c;其中特种车辆的养护教学也从中受益匪浅。VR虚拟仿真教学在特种车辆养护领域的应用&#xff0c;不仅创新了教学方式&#xff0c;还为提高学员的学习效果和实际操作技能提供了强有力的支持。 特…

c# combox 行间距调整

初始化combox comboBox1.DropDownStyle ComboBoxStyle.DropDownList;comboBox1.ItemHeight 25; // 设置 combox 的行高comboBox1.DrawMode DrawMode.OwnerDrawVariable; 添加 DrawItem 事件 private void comboBox1_DrawItem(object sender, DrawItemEventArgs e){if (…

ArrayList常用API

常见方法 add 增remove 删set 改get 查clear 清空元素size 长度isEmpty 为空判断 用法 // String就是泛型 这种使用方法对于限制类型很有用 ArrayList<String> arrayList new ArrayList<>();// add 添加元素 返回的是boolean 代表是否添加成功 arrayList.add(&qu…

【Neo4j系列】Neo4j之CQL语句和函数介绍

本文将对Neo4j中的CQL语句和CQL函数进行详细介绍。 作者&#xff1a;后端小肥肠 目录 1. 前言 2. CQL语句 2.1. CQL简介 2.2. CREATE命令 2.3. MATCH命令 2.4. RETURN命令 2.5. MATCH和RETURN 2.6. CREATEMATCHRETURN命令 2.7. 关系基础 2.8. CREATE创建标签 2.9. WH…

Unity 让角色动起来(动画控制器)

下载素材&#xff1a; 导入后&#xff0c;找到预制体和动画。 新建动画控制器&#xff0c;拖动到预制体的新版动画组件上。 建立动画关系 创建脚本&#xff0c;挂载到预制体上。 using System.Collections; using System.Collections.Generic; using UnityEngine;public c…

AIGC启示录:深度解析AIGC技术的现代性与系统性的奇幻旅程

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

Cloud-Eureka服务治理-Ribbon负载均衡

构建Cloud父工程 父工程只做依赖版本管理 不引入依赖 pom.xml <packaging>pom</packaging><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.9.RELEA…

【C语言】数据类型和变量

前言&#x1f49e;&#x1f49e; 啦啦啦~这里是土土数据结构学习笔记&#x1f973;&#x1f973; &#x1f4a5;个人主页&#xff1a;大耳朵土土垚的博客 &#x1f4a5; 所属专栏&#xff1a;C语言笔记 &#x1f4a5;欢迎大家&#x1f973;&#x1f973;点赞✨收藏&#x1f49…

二维码门楼牌管理系统在教育领域的应用及其优势

文章目录 前言一、二维码门楼牌管理系统概述二、教育领域的应用场景三、二维码门楼牌管理系统的优势四、结语 前言 随着信息技术的快速发展&#xff0c;二维码门楼牌管理系统在教育领域的应用越来越广泛。该系统不仅提高了地址信息的准确性&#xff0c;还为学校、家长和教育工…

分库分表

分库分表 1 分库分表介绍1.1、分库分表概述1.2、分库分表场景示例1.3、大数据存储下数据库性能分析1.4、小结 2 分库分表方式2.1、垂直分表2.2、垂直分库2.3、水平分表2.4、水平分库2.5、分库分表带来的问题2.6、分库分表小结 1 分库分表介绍 1.1、分库分表概述 分库分表本质…

k8s常用命令大全

k8s常用的命令 下面是一些常用的Kubernetes&#xff08;K8s&#xff09;命令&#xff0c;以及它们的简要说明。这些命令可以帮助您管理和操作Kubernetes集群中的资源。 集群管理命令&#xff1a; kubectl cluster-info: 显示集群的基本信息。 kubectl config use-context &l…

QT:用opencv的KNN识别图片中的LED数字(一)

前言 一款功能测试的软件demo,使用了QT作为界面,主要使用了opencv的KNN识别,使用gstreamer作为管道,用来打开图片。后期会写一篇打开摄像头实时识别的文章。 (正在写,未完成,稍候) 效果一预览: 效果二预览: 效果三预览: 正在写。。。 设计思路 1. 软件UI设计 2. …

TCP重传机制、滑动窗口、拥塞控制

一、总述 TCP&#xff0c;Transmission Control Protocol&#xff0c;是一个面向连接、基于流式传输的可靠传输协议&#xff0c;考虑到的内容很多&#xff0c;比如数据包的丢失、损坏、分片和乱序等&#xff0c;TCP协议通过多种不同的机制来实现可靠传输。今天&#xff0c;重点…

专访天谋科技谭新宇:我与 IoTDB 的这些年

从清华大学到天谋科技&#xff1a;一名 IoTDB 深度参与者的转换与成长。 自 2020 年以来&#xff0c;在数字化、国产化浪潮叠加下&#xff0c;中国信创产业得以高速发展&#xff0c;从基础硬件到基础软件、应用软件再到信息安全层面均涌现出一批领先的项目和厂商。 聚焦到基础软…

20240308-1-校招前端面试常见问题CSS

校招前端面试常见问题【3】——CSS 1、盒模型 Q&#xff1a;请简述一下 CSS 盒模型&#xff1f; W3C 模式&#xff1a;盒子宽widthpaddingbordermargin 怪异模式&#xff1a;盒子宽widthmargin Q&#xff1a;inline、block、inline-block 元素的区别&#xff1f; inline&am…

使用Go的encoding/asn1库处理复杂数据:技巧与最佳实践

使用Go的encoding/asn1库处理复杂数据&#xff1a;技巧与最佳实践 引言ASN.1 基础ASN.1与Go语言的关系ASN.1数据类型 encoding/asn1库概览主要功能和特性关键API应用场景 基本使用方法序列化&#xff08;编码&#xff09;反序列化&#xff08;解码&#xff09;处理复杂数据结构…

AAC ADTS格式

AAC⾳频格式&#xff1a;Advanced Audio Coding(⾼级⾳频解码)&#xff0c;是⼀种由MPEG-4 标准定义的有损⾳频压缩格式&#xff0c;由Fraunhofer发展&#xff0c;Dolby, Sony和AT&T是主要的贡献者。 ADIF&#xff1a;Audio Data Interchange Format ⾳频数据交换格式。这…

算法---双指针练习-6(查找总价格为目标值的两个商品)

查找总价格为目标值的两个商品 1. 题目解析2. 讲解算法原理3. 编写代码 1. 题目解析 题目地址&#xff1a;点这里 2. 讲解算法原理 算法的基本思想是首先初始化两个指针begin和end&#xff0c;分别指向数组的起始位置和末尾位置。 接下来&#xff0c;算法使用一个循环来移动e…

鸿蒙实战开发Camera组件:【相机】

相机组件支持相机业务的开发&#xff0c;开发者可以通过已开放的接口实现相机硬件的访问、操作和新功能开发&#xff0c;最常见的操作如&#xff1a;预览、拍照和录像等。 基本概念 拍照 此功能用于拍摄采集照片。 预览 此功能用于在开启相机后&#xff0c;在缓冲区内重复采集…

Axure Cloud如何给每个原型配置私有域名

需求 在原型发布之后&#xff0c;自动给原型生成一个独立访问的域名&#xff0c;类似http://u591bi.axshare.bushrose.cn&#xff0c;应该如何配置呢&#xff1f; 准备事项 已备案域名 如何备案&#xff1f;阿里云备案流程 已安装部署Axure Cloud 如何安装部署&#xff0c;请…