【数据结构】二、线性表:6.顺序表和链表的对比不同(从数据结构三要素讨论:逻辑结构、物理结构(存储结构)、数据运算(基本操作))

文章目录

      • 6.对比:顺序表&链表
        • 6.1逻辑结构
        • 6.2物理结构(存储结构)
          • 6.2.1顺序表
          • 6.2.2链表
        • 6.3数据运算(基本操作)
          • 6.3.1初始化
          • 6.3.2销毁表
          • 6.3.3插入、删除
          • 6.3.4查找

6.对比:顺序表&链表

6.1逻辑结构

顺序表和链表都是线性结构。

6.2物理结构(存储结构)
6.2.1顺序表

顺序存储

请添加图片描述

优点:

  1. 使用顺序存储,每个数据元素大小相同,所以可以随机访问,即可以在O(1)时间内找到第i个元素。
  2. 存储密度高,每个节点只存储数据元素。

缺点:

  1. 拓展容量不方便,使用大片连续的空间,即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高。
  2. 插入、删除操作不方便,需要移动大量元素
6.2.2链表

链式存储

请添加图片描述

优点:

  1. 离散分配空间,分配方便,改变容量方便。
  2. 单链表的节点是通过指针来连接的,因此在插入、删除节点时不需要移动其他节点,只需要修改指针的指向即可。

缺点:

  1. 由于链表每个节点只存储了指向下一个节点的指针,只能顺序存储,不可随机存储,所以访问节点时需要从头指针开始依次遍历访问,直到找到需要的节点,或者到达链表的结尾。
  2. 存储密度低,每个结点除了存储数据元素,还存储了指针。
6.3数据运算(基本操作)

6个基本操作:创销增删改查

顺序表链表
数据弹性(可扩容)
增、删
查找
6.3.1初始化

顺序表:

需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源。

  • 静态分配:静态数组,容量不可以改变。
  • 动态分配:动态数组(malloc、free):容量可改变,但需要移动大量元素,时间代价高。

链表:

只需分配一个头结点(也可以不要头结点,只声明一个头指针),之后方便拓展。

6.3.2销毁表

顺序表:

  1. 修改Length = 0
  2. 释放空间
    • 静态分配:静态数组,系统自动回收空间。
    • 动态分配:动态数组(malloc、 free),需要手动free。

链表:

依次删除各个结点(free)。

6.3.3插入、删除

顺序表:

插入/删除元素要将后续元素都后移/前移。

时间复杂度O(n),时间开销主要来自移动元素

链表:

插入/删除元素只需修改指针即可。

时间复杂度O(n),时间开销主要来自查找目标元素

若元素占用空间很大,那么移动元素花费的时间要比查找元素花费是时间代价更大。

6.3.4查找

顺序表:

按位查找:使用顺序存储,每个数据元素大小相同,所以可以随机访问,即可以在**O(1)**时间内找到第i个元素。

按值查找:O(n)。若表内元素有序,可在 O(log_2n) 时间内找到。

链表:

按位查找:由于单链表每个节点只存储了指向下一个节点的指针,只能顺序存储,不可随机存储,所以访问节点时需要从头指针开始依次遍历访问,直到找到需要的节点O(n)。

按值查找:只能遍历O(n)

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

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

相关文章

基于pytest的证券清算系统功能测试工具开发

需求 1.造测试数据:根据测试需要,自动化构造各业务场景的中登清算数据与清算所需起来数据 2.测试清算系统功能: 自动化测试方案 工具设计 工具框架图 工具流程图 实现技术 python, pytest, allure, 多进程,mysql, 前端 效果 测…

Web开发介绍,制作小网站流程和需要的技术【详解】

1.什么是web开发 Web:全球广域网,也称为万维网(www World Wide Web),能够通过浏览器访问的网站。 所以Web开发说白了,就是开发网站的,例如网站:淘宝,京东等等 2. 网站的工作流程 1.首先我们需…

【Godot4自学手册】第二十一节掉落金币和收集

这一节我们主要学习敌人死亡后随机掉落金币,主人公可以进行拾取功能。 一、新建金币场景 新建场景,节点选择CharacterBody2D,命名为Coins,将场景保存到Scenes目录下。 1.新建节点 为根节点依次添加CollisionShape2D节点&#…

阿里云服务器使用教程_2024建站教程_10分钟网站搭建流程

使用阿里云服务器快速搭建网站教程,先为云服务器安装宝塔面板,然后在宝塔面板上新建站点,阿里云服务器网aliyunfuwuqi.com以搭建WordPress网站博客为例,来详细说下从阿里云服务器CPU内存配置选择、Web环境、域名解析到网站上线全流…

Dubbo基础入门二

8、Dubbo协议 服务调用 8.1 服务端 启动过程深入分析 我们查看一下服务启动的过程 ProtocolFilterWrapper.export 好我们进入DubboProtocol.export 创建服务 分析我们的Handler 我们接着返回刚才位置 下面的super方法里面会创建服务,ChannelHandlers.wrap会对hand…

2024年3月8日蚂蚁新村今日答案:以下哪一项传统武术项目入选了人类非物质文化遗产代表作名录?太极拳还是咏春拳

蚂蚁新村是一个虚拟社区。在这个虚拟社区中,用户可以参与各种活动,比如生产能量豆、做慈善捐赠等。同时,蚂蚁新村也提供了一些知识问答环节,用户在参与的过程中可以增进知识。这些问答内容往往涉及广泛的主题,如文化、…

idea Gradle 控制台中文乱码

如下图所示,idea 中的 Gradle 控制台中文乱码: 解决方法,如下图所示: 注意:如果你的 idea 使用 crack 等方式破解了,那么你可能需要在文件 crack-2023\jetbra\vmoptions\idea.vmoptions 中进行配置&#xf…

git分布式管理-头歌实验标签

一、创建标签 任务描述 现在你已经成了项目负责人,由你负责发布版本,你需要在发布一个版本之前,给该版本对应的代码打上标签,以便于管理和标识。 本关任务:为最近一次提交打上标签。 相关知识 在开发过程中&#xff0c…

Android14之禁止vbmeta.img签名校验(一百九十)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…

七彩虹八渐变 外贸建站公司wordpress模板

进出口水果wordpress外贸模板 漂亮水果wordpress外贸模板,做水果进出品生意的外贸公司自建站官网模板。 https://www.jianzhanpress.com/?p3516 玩具wordpress外贸模板 简洁玩具wordpress外贸模板,适合做跨境电商外贸公司使用的wordpres外贸s网站主题…

追寻工作与生活的和谐之道

在现代社会,人们往往被快节奏的工作和生活所困扰,如何在这两者之间找到平衡点,成为许多人关注的焦点。本文将为您介绍一些实用的方法和建议,帮助您实现工作与生活的和谐共处。 一、合理规划时间,提高工作效率 时间是实…

day37 贪心算法part6

738. 单调递增的数字 中等 提示 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。 给定一个整数 n &#xff0c;返回 小于或等于 n 的最大数字&#xff0c;且数字呈 单调递增 。 不知道怎么讲思路……以9287举例&#xff0c;…

CorelDRAW2024中文版正式发布!老户升级可享大额折扣!CDR2024下载安装 CorelDRAW2024更新内容有哪些

CorelDRAW 全称“CorelDRAW Graphics Suite“&#xff0c;也就是众所周知的”CDR“&#xff0c;是一款智能高效的平面设计软件&#xff0c;广泛应用于排版印刷、矢量图形编辑及网页设计等领域&#xff0c;30多年来无数优秀的设计师通过CorelDRAW大胆展现真我&#xff0c;交付了…

学习408之数据结构--链表-单链表的增删查改的实现-如何解决顺序表增容后空间浪费问题?

顺序表的问题及思考问题&#xff1a; 中间/头部的插入删除&#xff0c;时间复杂度为O(N)增容需要申请新空间&#xff0c;拷贝数据&#xff0c;释放旧空间。会有不小的消耗。增容一般是呈2倍的增长&#xff0c;势必会有一定的空间浪费。例如当前容量为100&#xff0c;满了以后增…

#QT(智能家居界面-布局)

1.IDE&#xff1a;QTCreator 2.实验&#xff1a; 水平布局&#xff0c;垂直布局&#xff0c;栅格布局&#xff08;弹簧&#xff09; 界面自动调整 3.记录 注意弹簧不是拖拽拉长&#xff0c;而是使用栅格布局 运行发现窗口放大缩小可以自动调整 如果想要重新布局&#xff0c;需…

ubuntu20.04安装ros并配置相关环境以及驱动AUBO i5机械臂

ubuntu20.04安装ros并配置相关环境以及驱动AUBO i5机械臂 安装ros安装rosdep(小鱼的rosdepc,又快又好用)环境配置下载并编译aubo roslib库环境变量配置aubo gazeboaubo rviz驱动真实机械臂 安装ros 搜索鱼香ros网站https://fishros.com/&#xff0c;根据一键安装ros里提供的指…

某讯滑块动态明文数组构造

声明&#xff1a; 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01;若有侵权&#xff0c;请添加&#xff08;wx&#xff1a;wyqlxl99&#xff09;联系删除 …

R语言,实现MACD指标计算:股票技术分析的利器系列(1)

R语言&#xff0c;实现MACD指标计算&#xff1a;股票技术分析的利器系列&#xff08;1&#xff09; MACD指标代码完整代码介绍代码EMA函数calculate_DEA 函数calculate_MACD 函数 运行结果 MACD指标 先看看官方介绍&#xff1a; MACD (平滑异同平均线&#xff09; 指标说明 DI…

智引未来:2024年科技革新引领工业界变革与机遇

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

苍穹外卖技术栈

Day5 Redis_Spring Data Redis使用方法 Spring Data Redis Spring Date Redis 是Spring的一部分&#xff0c; 对Redis底层开发包进行了高度封装&#xff0c;在Spring项目中&#xff0c;可以使用Spring Data Redis来简化操作。 操作步骤 导入Spring Data Redis 的maven坐标配置…