当前位置: 首页 > news >正文

【数据结构】链表与顺序表的比较

不同点:

顺序表和链表是两种常见的数据结构,他们的不同点在于存储方式和插入、删除操作、随机访问、cpu缓存利用率等方面。

一、存储方式不同:

顺序表:

顺序表的存储方式是顺序存储,在内存中申请一块连续的空间,通过下标来进行存储;

链表:

链表的存储方式是链式存储,申请的空间是未必连续的,以节点的形式连接,每个节点会有一个next指针,指向下一个节点,通过指针来访问元素;

二、插入、删除的效率不同:

顺序表:

插入删除元素时,需要移动元素的位置也就是搬移元素,导致效率低下

链表:

插入删除时只需要修改指针指向。

三、内存利用率:

顺序表:

需要扩容,创建空间大小是固定的,当空间不够时需要进行扩容,以2倍的关系扩增的,你少一个空间,我增大到原来的2倍,还会有多余空间未使用,所以扩容会造成空间浪费的现象。

但是注意我们因为用的realloc扩容,所以扩容本身会有消耗!!👉👉👉

由于realloc扩容的特性,不确定是原地还是异地扩容,这个与编译器有点关系

原地扩容:扩容的空间地址与原来地址相同

异地扩容:扩容的空间地址与原来地址不同(将原来的数据拷贝过来,还要销毁原来的空间)

链表:

按需申请的空间,不会存在空间浪费现象,利用率极高

四、随机访问:

顺序表:

支持用下标随机访问

链表:

不支持,因为空间在物理上就不是连续的,next找到下一个节点,在用该节点的next找一个,找起来比较麻烦

五、缓存利用率:

缓存👉CPU高速缓存🧑‍🎓🧑‍🎓 内存在带电的情况下存储,当断电后未保存的数据会丢失(就像我们在用画板时,画了画,你给电脑关机,下次进去就找不到了)但其速度快,而硬盘可以不带电存储,但是速度慢。

🤔🤔为啥有寄存器和三级缓存??

✨✨主要是cpu的运行速度很快,看不上内存日常不会去访问内存,但是寄存器和三级缓存的速度还是能入下眼✨✨

我们写的代码时,变量存在内存里面,当你要修改变量时会将数据放到寄存器,然后cpu对其接收指令进行修改

看下面代码的反汇编,mov 是将 i 放到 eax(寄存器)中,然后对寄存器的数据进行inc指令也就是加1, 在讲寄存器的数据放到可i中

但是寄存器个数有限,一般对于4个 8个字节会放到寄存器,数据比较大会加载到缓存,( 缓存里面还要涉及到三级缓存的调用,有点深奥,不讲这么难的,可以自己去查资料)

cpu访问数据会先访问数据是否在缓存中,在---》缓存命中,直接访问。

                                                                不在---》不命中,先将数据加载到缓存中,再进行访问。

🤔怎么加载到缓存的??

cpu会按cpu字长去读,会认为你访问当前数据后面(连续在一起的)都不在缓存中,给它加载进去

举个例子:数组为例子,下面的20个人就是一个数组。度假村相当于缓存,领导是cpu,大巴车也是cpu,cpu给你加载到缓存,再访问

注意:缓存有一定的范围,新进来的过多,放不下了,就给旧的清理掉!


对于链表了,你的物理空间是不连续,拉的数据太多,会把缓存区之前的一些数据排挤走了

顺序表:

 CPU缓存利用率高。

链表:

CPU缓存利用率低。

六、总结:

不同点顺序表单链表
存储空间物理上一定连续(底层是数组)只是逻辑上连续,物理上并不连续
随机访问下标访问 O(1)不支持:要遍历O(N)
任意位置的增删需要搬运元素,效率低O(N)无需搬运,只需要修改指针指向
插入动态顺序表,需要扩容(成倍扩容,可能会造成空间浪费)按需申请,没有扩容这一说法
应用场景元素的高效存储+频繁的访问任意位置插入+删除频繁
CPU缓存利用率缓存利用率高缓存利用率低

链表和顺序表各有优势,互相弥补各自的缺点

总之,顺序表用于数据元素较少、读取操作频繁的场景,而链表更适用于数据元素较多、插入、删除操作频繁的场景。

  就到               这吧  ❤️🫰

相关文章:

【数据结构】链表与顺序表的比较

不同点: 顺序表和链表是两种常见的数据结构,他们的不同点在于存储方式和插入、删除操作、随机访问、cpu缓存利用率等方面。 一、存储方式不同: 顺序表: 顺序表的存储方式是顺序存储,在内存中申请一块连续的空间,通…...

dart 基本语法

//入口方法 main() 或 void main() //数据类型 原生数据类型 String int double bool null 注意:String 包函 ‘’ “” ‘’’ ‘’’ 三种形式复杂数据类型 list Set Map自定义数据类型 class inheritance动态数据类型 var 注:dart 是静态类型语言&a…...

【经验分享】嵌入式入坑经历(选段)

文章目录 你现在的工作中所用到的专业知识有哪些呢?为什么想转行了?后来为什么从事了嵌入式行业呢?你对嵌入式的兴趣是何时培养起来的?你是怎么平衡兴趣爱好和工作的关系的?平时做的事情对你现在的工作有哪些帮助?对于有志学习嵌入式开发的在校大学生…...

Docker面试整理-Docker与虚拟机的区别是什么?

Docker 容器和传统的虚拟机(VM)都是提供隔离的运行环境以部署和运行应用程序的技术,但它们在架构和性能上存在显著的不同。了解这些差异可以帮助你选择最适合特定需求的解决方案: 基础架构:虚拟机:每个虚拟机都包括完整的操作系统、应用程序、必需的库和二进制文件,运行在…...

Java:JDK8 GC中ParNew和CMS的问题说明

JDK8中常用如下的垃圾收集器,它们分别运用在年轻代和老年代: ParNew : 年轻代垃圾收集器,多线程,采用标记—复制算法。 CMS:老年代的收集器,全称(Concurrent Mark and Sweep)&#…...

学单片机前先学什么?

先学c语言和数字电路 这里默认你说的单片机是51单片机,通过你的问题,我猜你的单片机应该还没有入门,如果是入门的话,一般都是从51单片机开始的。刚好我有一些资料,是我根据网友给的问题精心整理了一份「单片机的资料从…...

数据可视化:Matplotlib 与 Seaborn

数据可视化是数据分析中至关重要的一部分,它能帮助我们直观地理解数据的分布、趋势和关系。Python 中,Matplotlib 和 Seaborn 是两个最常用的可视化库。本文将详细介绍如何使用 Matplotlib 和 Seaborn 进行数据可视化,包括基本图形、图形定制…...

【linux】自定义快捷命令/脚本

linux自定义快捷命令 场景自定义命令自定义脚本 场景 深度学习经常要切换到自己环境,conda activate mmagic,但是又不想每次重复打这么多字,想使用快捷命令直接切换。 自定义命令 使用别名(alias)或自定义脚本来创建…...

使用onnxruntime加载YOLOv8生成的onnx文件进行目标检测

在网上下载了60多幅包含西瓜和冬瓜的图像组成melon数据集,使用 LabelMe 工具进行标注,然后使用 labelme2yolov8 脚本将json文件转换成YOLOv8支持的.txt文件,并自动生成YOLOv8支持的目录结构,包括melon.yaml文件,其内容…...

QT 信号和槽 一对多关联示例,一个信号,多个槽函数响应,一个信号源如何绑定多个槽函数

在窗体里放置一个单行文本编辑控件(QLineEdit)、一个标签控件(QLabel)和一个文本浏览控件(QTextBrowser),在单行文 本编辑控件里的文本被编辑时,标签控件和文本浏览控件都会同步显示…...

C++ AVL树 详细讲解

目录 一、AVL树的概念 二、AVL树的实现 1.AVL树节点的定义 2.AVL树的插入 3.AVL树的旋转 4.AVL树的验证 三、AVL树的性能 四、完结撒❀ 一、AVL树的概念 二叉搜索树虽可以缩短查找的效率,但 如果数据有序或接近有序二叉搜索树将退化为单支树,查 …...

Faster R-CNN:端到端的目标检测网络

本文回顾了由微软研究人员开发的 Faster R-CNN 模型。Faster R-CNN 是一种用于物体检测的深度卷积网络,在用户看来,它是一个单一的、端到端的统一网络。该网络可以准确快速地预测不同物体的位置。为了真正理解 Faster R-CNN,我们还必须快速概…...

如何给 MySQL 表和列授予权限?(官方版)

目录 授予表级别权限 授予列级别权限 如何给MySQL表和列授予权限是MySQL数据操作中非常重要的步骤,也是企业级使用MySQL数据库的起步点,以下分别参照官方教程整理的MySQL数据库的权限操作。 以下的语句可以直接使用MySQL的命令行进行操作(如何…...

攻防世界testre做法(考点:base58)

在做这道题目之前,我们先来简单了解一下base64加密和base58加密,先来说一些预备知识,bit为1个位,即一个0或1,八个位组成一个字节,即八个二进制数。 base64编码原理:1,在使用base64加…...

计算机视觉与模式识别实验1-1 图像的直方图平衡

文章目录 🧡🧡实验流程🧡🧡1.读入图像‘rice.png’,在一个窗口中显示灰度级n64,128和256的图像直方图。2.调解图像灰度范围,观察变换后的图像及其直方图的变化。3.分别对图像‘pout.tif’和‘ti…...

【C++课程学习】:C++入门(函数重载)

🎁个人主页:我们的五年 🔍系列专栏:C课程学习 🎉欢迎大家点赞👍评论📝收藏⭐文章 目录 🌈函数重载: 🍉1.参数个数不同: 🍉2.参数…...

skywalking介绍及搭建

链路追踪框架比对: skywalking安装部署: 下载地址:Downloads | Apache SkyWalking 配置微服务与skywalking整合: copy agent/optional-plugins/apm-spring-cloud-getway-xx.jar到plugins,然后重启skywalking 监控界面…...

分析示例 | Simufact焊接工艺仿真变形精确预测汽车结构

导语 焊接是汽车制造过程中一个关键环节,白车身、发动机、底盘和变速箱等都离不开焊接工艺的应用,主要涉及气保焊、电阻点焊、激光焊、电子束焊等多种焊接工艺。由于汽车车型众多、成形结构复杂、汽车制造质量、效率、成本等方面的综合要求。如何高效、…...

模式识别选择题

影响K-均值聚类算法效果的主要因素之一是什么? A. 初始聚类中心的选取 B. 样本输入顺序 C. 模式相似性测度 D. 分类准则 答案:A支持向量机(SVM)在处理非线性问题时,通常使用什么方法? A. 引入核函数 B. 增加…...

【Java基础】线程方法

start():启动线程,使线程进入就绪状态。 run():线程执行的代码逻辑,需要重写该方法。 停止线程 void interrupt() 中断线程,让它重新去争抢cpu 如果目标线程长时间等待,则应该使用interrupt方法来中断等待…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...