List的两种实现

前置知识:

数组

baseAddress:数组的首地址

dataTypeSize:数组中元素类型的大小,如int为4字节

为什么数组索引从0开始,假如从1开始不行吗?

在根据数组索引获取元素的时候,会用索引和寻址公式来计算内存所对应的元素数据,寻址公式是:数组的首地址+索引*存储数据的类型大小

这样对于CPU来说,增加了一个减法指令,影响性能

时间复杂度

随机查找(通过下标)时间复杂度O(1)

查找元素(未知下标)时间复杂度O(n)

查找元素(未知下标但排序)通过二分查找的时间复杂度O(logn)

插入元素和删除元素的时候,为了保证数组的内存连续性,需要挪动数组元素,平均时间复杂度为O(n)

ArrayList

源码分析【jdk8】

elementData 为数组,我们所有的操作都在该数组上

无参构造的时候调用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA

有参构造的时候调用的是EMPTY_ELEMENTDATA

以上两个集合虽然都为空集合,但是在后续判断的时候用来做区分【下面有代码】

区分我这个集合是通过有参(大小为0)创建的还是无参创建的,如果是无参的,那么我第一次计划会和default_capacity(10)进行比较,如果是有参的,则直接返回size+1

第一次添加数据的时候,即假设我们是通过无参构造生成的ArrayList【数组容量为0,因为空数组,size为0】,然后往里面第一次加数据的时候,会先去调用ensureCapacityInternal方法,将成员变量elementData和minCapacity传进去,因为elementData是通过无参构造器(赋的值),所以此时elementData == defaultCapacity_EMPTY_elmentdata,所以判断,如果size+1比10(默认的)小,则计划容量为10,否则计划至size+1。计划完成之后,还需要确保容量是否够,调用ensureExplicitCapacity,够用则不会扩容,正常情况下1-10次add都不会扩容,第十一次的时候,每次扩容为原来的1.5(接近)倍(增加原来的一半,如果是奇数会缺失小数部分)

ArrayList底层的实现原理:

ArrayList list = new ArrayList(10) 中list扩容了几次?

该语句中只是声明和实例了一个ArrayList,指定了容量为10,未扩容。

如何实现数组和List之间的转换?


数组转换成List:调用数组的静态方法 Arrays.asList(数组名) 【该方法转成的集合不可变】

使用JDK中java.util.Arrays工具类的asList方法

List转换成数组:使用List的toArray方法。toArray方法返回Object数组,传入类型和长度。

Arrays.asList转换List之后,如果修改了数组的内容,list会受到影响,因为它的底层集合的构造器中,把我们传入的这个集合进行了包装而已,最终它们指向的都是同一个内存地址。

toArray转数组后,如果修改了list内容,数组不会受影响,当调用toArray后,底层进行了数组的拷贝,跟原来的元素没关系(new了一个新的)

ArrayList和LinkedList区别?

底层数据结构:

ArrayList是动态数组的数据结构实现【动态是因为进行扩容,然后进行拷贝】

LinkedList是双向链表的数据结构实现

操作数据效率:

ArrayList按照下标查询的时间复杂度O(1)【内存是连续的,根据寻址公式】,LinkedList不支持下标查询

查找(未知索引):ArrayList需要遍历,链表也需要遍历,时间复杂度都是O(n)

新增和删除

ArrayList尾部插入和删除,时间复杂度未O(1);其他部分增删需要挪动数组,时间复杂度为O(n)

LinkedList头尾接待你增删时间复杂度是O(1)【双向链表】,其他都需要遍历链表,时间复杂度O(n)

内存空间占用

ArrayList底层是数组,内存连续,节省内存

LinkedList是双向链表需要存储数据和两个指针,更占用内存

线程安全

ArrayList和LinkedList都不是线程安全的

如果需要保证线程安全,有两种方案

1.在方法内使用,局部遍历是线程安全的

2.使用线程安全的ArrayList和LinkedList【使用Collections下的synchroniedList封装】当然性能会低

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

网络安全之DHCP详解

DHCP:Dynamic Host Configration Protocol 动态主机配置协议 某一协议的数据是基于UDP封装的,当它想确保自己的可靠性时,这个协议要么选确认重传机制,要么选周期性传输。 DHCP是确认重传,【UDP|DHCP】,当DHCP分配完地…

这个Python库Streamlit,5分钟内搭建可视化WEB应用

在数据科学的世界里,将分析结果快速、直观地呈现给非技术背景的决策者,是一项重要的技能。而Streamlit,这个开源的Python库,正是为此而生。它允许数据科学家和工程师通过少量的代码,快速创建和分享数据应用。今天&…

citylava:城市场景中VLMs的有效微调

citylava:城市场景中VLMs的有效微调 摘要IntroductionRelated WorkVision-Language ModelsVLMs in Driving Methodology CityLLaVA: Efficient Fine-Tuning for VLMs in City Scenario 摘要 在城市广阔且动态的场景中,交通安全描述与分析在从保险检查到事故预防的各…

QGraphicsItem的prepareGeometryChange 和 update方法区别

prepareGeometryChange 这个函数用于为图形的几何形状变化做准备。在改变一个项目的边界矩形之前调用此函数,以保持 QGraphicsScene 的索引是最新的。如果必要的话,prepareGeometryChange() 会调用 update()。QGraphicsScene认为所有图元的boundingRect…

一个圈圈的机制玩法

什么是一个圈圈,说白了就是一个撸广告的平台,只是引入了减产机制,九维机制和分成机制,再加上有央企背景,做的一个区块链平台。 玩法很简单,就是撸广告获取能量,然后获取绿色能量,等…

AI绘画Stable DIffusion 室内设计—普通人秒变精装设计师,轻松接单!

AI 绘画赚 300 块不算多,但只用了10分钟。 大家好,我是灵魂画师向阳 一直以来精装设计师对专业特别是美学的把握,是我们普通人无法启迪的。但是AI时代来了,普通人只要把房子毛坯的照片交给AI绘图工具,10分钟轻松就能…

区块链 | NFT 相关论文:Preventing Content Cloning in NFT Collections(三)

🐶原文: Preventing Content Cloning in NFT Collections 🐶写在前面: 这是一篇 2023 年的 CCF-C 类,本博客只记录其中提出的方法。 F C o l l N F T \mathbf{F_{CollNFT}} FCollNFT​ and Blockchains with Native S…

11.偏向锁原理及其实战

文章目录 偏向锁原理及其实战1.偏向锁原理2.偏向锁案例代码演示2.1.偏向锁案例代码2.2.1.无锁情况下状态2.1.2.偏向锁状态2.1.3.释放锁后的状态 2.2.偏向锁的膨胀和撤销2.2.1.偏向锁撤销的条件2.2.2.偏向锁的撤销 2.2.3.偏向锁的膨胀 2.3.全局安全点原理和偏向锁撤销性能问题2.…

“王翦五讨赏地,萧何三贬其身”的背后,正是智者安身的处世之道

冯子曰:智者,术所以生也;术者,智所以转也。 智慧的人,从不蛮行横性,而是懂得如何在世道和自我之间谋得最佳的处境。 01、王翦五讨赏地 战国时期,秦始皇派王翦率六十万大军攻打楚国&#xff0…

AI换脸原理(3)——人脸对齐介绍

人脸对齐简介 人脸对齐其实包含两个步骤:人脸关键点检测、人脸对齐,英文术语有facial landmark和face alignment,主要用于精确标识眉毛、眼睛、鼻子、嘴巴以及人脸轮廓等特征部位。不同数据集对于关键点的数量有不同的设定,最少的是标记5个关键点,通常包括两只眼睛的瞳孔…

通过 Java 操作 redis -- list 列表基本命令

目录 使用命令 lpush,lrange,rpush 使用命令 lpop 和 rpop 使用命令 blpop,brpop 使用命令 llen 关于 redis list 列表类型的相关命令推荐看Redis - list 列表 要想通过 Java 操作 redis,首先要连接上 redis 服务器&#xff…

线程理论篇1

本章问题:什么是线程?线程的使用场景?什么是线程池?线程池是如何工作的?线程池共享了哪些资源?线程安全代码怎么写?什么是线程安全? 什么是线程? 线程是为了提高进程的效率。进程的地址空间中保存了cpu…

软件合规 安全可控 | 企业软件合规化管理方案

软件合规,安全可控,这是当下企业运营中不可或缺的两个关键词。随着信息技术的迅猛发展,企业对于软件的需求与日俱增,然而,如何确保软件的合规性和安全性,却成为了摆在企业面前的一大难题。Ping32企业软件合…

WinForm中防页面假死的loading提示

如果在WinForm中执行一个长时间操作时,窗体就会被锁死,直到操作完成,对于操作者的体验就是死锁状态,那在.NET(.net 5以后)中,怎么实现一个并发,等待,且同步操作信息窗口呢…

【接地故障保护】剩余电流继电器及监控产品解决方案

安科瑞电气股份有限公司 祁洁 15000363176 一、产品型号 二、产品功能 1、对直接接触电击事故的防护 对直接接触电击事故的防护中,剩余电流继电器(RCD)只作为直接接触电击事故基本防护措施的补充保护措施(不包括对相与相、相…

使用Linux命令时,前面加sudo和不加有什么区别?

在使用cmake命令编译时,前面加上sudo和不加主要有以下区别: 权限: 使用sudo:当您在命令前加上sudo时,表示您以超级用户的权限执行该命令。这通常用于需要访问受限制的系统文件或执行需要更高权限的操作。不使用sudo&am…

Java面试八股文(MySQL篇)

数据库三范式 数据库事务介绍 索引介绍 SQL优化手段 mysql union 与 union all 语法及用法 并发事务带来的问题 大表如何优化 索引类型介绍 MYSQL数据库锁介绍

数据库数据恢复—SQL Server数据库ndf文件变为0KB的数据恢复案例

SQL Server数据库故障: 存储设备损坏导致存储中SQL Server数据库崩溃。对数据库文件进行恢复后,用户发现有4个ndf文件的大小变为0KB。该SQL Server数据库每10天生成一个大小相同的NDF文件,该SQL Server数据库包含两个LDF文件。 SQL Server数据…

2024年数维杯数学建模B题思路

文章目录 1 赛题思路2 比赛日期和时间3 竞赛信息4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间:2024…

带你快速掌握Spring Task

Spring Task ⭐Spring Task 是Spirng框架提供的任务调度工具,可以按照约定的时间自动执行某个代码逻辑 📌一款定时任务框架 应用场景 信用卡信息银行贷款信息火车票信息 只要是需要定时处理的场景都可以使用Spring Task 只要有定时,就会有…