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

【数据结构】二、线性表: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)

相关文章:

【数据结构】二、线性表: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逻辑结构 顺…...

Golang单例模式学习笔记

前言 单例模式是常用的一种设计模式,一般用于比如客户端、连接的创建等,防止创建多个导致性能消耗。所以我认为单例模式的核心,就是“防止重复”。本文将在Golang中进行单例模式的实现。 实现 版本1——检测-创建 最基础的版本&#xff0…...

Leetcode HOT150

55. 跳跃游戏 给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1 …...

仿牛客项目Day1

SpringMVC 架构 spring的前端控制器是DispatcherServlet 模板引擎Thymeleaf 这个还不知道干嘛的 mvc演示 get请求 RequestMapping:声明访问路径和http方法get或set什么的 ResponseBody:java对象转为json格式的数据,表示该方法的返回结…...

Effective C++ 学习笔记 条款17 以独立语句将newed对象置入智能指针

假设我们有个函数用来揭示处理程序的优先权&#xff0c;另一个函数用来在某动态分配所得的Widget上进行某些带有优先权的处理&#xff1a; int priority();void processWidget(std::st1::shared_ptr<Widget> pw, int priority);由于谨记“以对象管理资源”&#xff08;条…...

通过Electron打包前端项目为exe

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;爱蹦跶的大A阿 &#x1f525;当前正在更新专栏&#xff1a;《JavaScript保姆级教程》、《VUE》、《Krpano》 ✨ 正文 1、 拉取electron官网上的demo&#xff0c;拉下来之后安装依赖&#xff0c;项目跑起来之后&#xff0c;就…...

大模型时代企业知识全生命周期管理解决方案

©作者|Zhongmei 来源|神州问学 摘 要 越来越多的企业开始意识到数据的重要性。同时意识到&#xff0c;企业想保持长远的发展&#xff0c;还需要协调组织协作、利用现有的数据沉淀经验知识、累积数据资产。据IDC调查&#xff0c;目前企业结构化数据仅占到全部数据量的20%…...

C#冒泡排序算法

冒泡排序实现原理 冒泡排序是一种简单的排序算法&#xff0c;其原理如下&#xff1a; 从待排序的数组的第一个元素开始&#xff0c;依次比较相邻的两个元素。 如果前面的元素大于后面的元素&#xff08;升序排序&#xff09;&#xff0c;则交换这两个元素的位置&#xff0c;使…...

【前端寻宝之路】总结学习使用CSS的引入方式

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法|MySQL| ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-BNJBIEvpN0GHNeJ1 {font-family:"trebuchet ms",verdana,arial,sans-serif;f…...

Python中输入输出函数input和print用法

# 读入一个字符串 s input() print(s)abcdef abcdef# 读入一个整数 n int(input()) print(n)5 5# 读入两个整数(空格间隔) # input()表示读入一行字符串 # split()表示以空格间隔切分出多个字符串序列&#xff0c;如果逗号间隔可以加参数split(,) # map()将序列每个元素转为整…...

简单认识Linux

今天带大家简单认识一下Linux&#xff0c;它和我们日常用的Windows有什么不同呢&#xff1f; Linux介绍 Linux内核&发行版 Linux内核版本 内核(kernel)是系统的心脏&#xff0c;是运行程序和管理像磁盘和打印机等硬件设备的核心程序&#xff0c;它提供了一个在裸设备与…...

javascript正则深入

文章目录 一、前言二、高级`API`2.1、模式匹配的用法`(x)`2.2、非捕获括号的模式匹配`(?:x)`2.3、先行断言`x(?=y)`2.4、后行断言`(?<=y)x`2.5、正向否定查找`x(?!y)`2.6、反向否定查找`(?<!y)x`2.7、字符集合和反向字符集合的用法 `[xyz] / [^xyz]`2.8、词边界和非…...

React-封装自定义Hook

1.声明函数 说明&#xff1a;声明一个以use打头的函数 function useToggle(){} 2.封装 说明&#xff1a;在函数体内封装可复用的逻辑 const [value,setValue]useState(true)const toggle()>{setValue(!value)} 3.返回 说明&#xff1a;把组件中用到的状态或者回调retu…...

Spark实战-基于Spark日志清洗与数据统计以及Zeppelin使用

Saprk-日志实战 一、用户行为日志 1.概念 用户每次访问网站时所有的行为日志(访问、浏览、搜索、点击)用户行为轨迹&#xff0c;流量日志2.原因 分析日志&#xff1a;网站页面访问量网站的粘性推荐3.生产渠道 (1)Nginx(2)Ajax4.日志内容 日志数据内容&#xff1a;1.访问的…...

Springboot中Redis的配置使用

新建 向pom.xml中添加依赖&#xff0c;这个可以不用标注版本号 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 配置yml文件&#xff08;文件名不可以错…...

【node版本问题】运行项目报错 PostCSS received undefined instead of CSS string

最近该项目没有做任何修改&#xff0c;今天运行突然跑不起来报错了 PostCSS received undefined instead of CSS string 【原因】突然想起来期间有换过 node 版本为 16.17.1 【解决】将 node 版本换回之前的 14.18.0 就可以了...

Spring揭秘:BeanDefinitionRegistry应用场景及实现原理!

内容概要 BeanDefinitionRegistry接口提供了灵活且强大的Bean定义管理能力&#xff0c;通过该接口&#xff0c;开发者可以动态地注册、检索和移除Bean定义&#xff0c;使得Spring容器在应对复杂应用场景时更加游刃有余&#xff0c;增强了Spring容器的可扩展性和动态性&#xf…...

蓝桥杯(3.5)

789. 数的范围 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int q sc.nextInt();int[] res new int[n];for(int i0;i<n;i)res[i] sc.nextInt();while(q-- ! 0) {int…...

434G数据失窃!亚信安全发布《勒索家族和勒索事件监控报告》

最新态势快速感知 最新一周全球共监测到勒索事件90起&#xff0c;与上周相比数量有所增加。 lockbit3.0仍然是影响最严重的勒索家族&#xff1b;alphv和cactus恶意家族也是两个活动频繁的恶意家族&#xff0c;需要注意防范。 Change Healthcare - Optum - UnitedHealth遭受了…...

7-18 彩虹瓶(Python)

彩虹瓶的制作过程&#xff08;并不&#xff09;是这样的&#xff1a;先把一大批空瓶铺放在装填场地上&#xff0c;然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。 假设彩虹瓶里要按顺序装 N 种颜色的小球&#xff08;不妨将顺序就编号为 1 到 N&#xff09;。现在工…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...

HTML版英语学习系统

HTML版英语学习系统 这是一个完全免费、无需安装、功能完整的英语学习工具&#xff0c;使用HTML CSS JavaScript实现。 功能 文本朗读练习 - 输入英文文章&#xff0c;系统朗读帮助练习听力和发音&#xff0c;适合跟读练习&#xff0c;模仿学习&#xff1b;实时词典查询 - 双…...