当前位置: 首页 > 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;。现在工…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...