ArrayList与LinkedList的性能差别

2024-06-06 05:18

本文主要是介绍ArrayList与LinkedList的性能差别,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【转载】ArrayList还是LinkedList?使用不当性能差千倍

文章目录

  • 实现方式
    • ArrayList
    • LinkedList
  • 新增元素
    • ArrayList
    • LinkedList
  • 删除元素
    • ArrayList
    • LinkedList
  • 遍历元素

实现方式

ArrayList

size:集合元素个数,elementData.length:数组长度
ArrayList初始容量为0,一旦加入元素后,容量至少变为10;继续增加元素,当size=elementData.length时,容量增加到原来的1.5倍(int newCapacity = oldCapacity + (oldCapacity >> 1);)。扩容后,将原数组复制到新分配的内存地址上。
根据动态扩容的机制,可知当元素越多时,空闲的空间就越大。
序列化时只序列化size长度,而不会序列化数组长度。

如果采用外部序列化实现数组的序列化,会序列化整个数组。ArrayList为了避免这些没有存储数据的内存空间被序列化,内部提供了两个私有方法writeObject以及readObject来自我完成序列化与反序列化,从而序列化与反序列化数组时节省了空间和时间。因此使用transient修饰数组,是防止对象数组被其他外部方法序列化。

LinkedList

LinkedList是基于双向链表数据结构实现的,是由Node结构对象连接而成的一个双向链表。
由于LinkedList存储数据的内存地址是不连续的,而是通过指针来定位不连续地址,因此LinkedList不支持随机快速访问,LinkedList也就不能实现RandomAccess接口。
LinkedList也是自行实现readObject和writeObject进行序列化和反序列化。

新增元素

ArrayList

ArrayList 插入到指定位置:
先检查插入的位置是否在合理的范围之内,然后判断是否需要扩容,再把该位置以后的元素复制到新添加元素的位置之后,最后通过索引将元素添加到指定的位置。这种情况是非常伤的,性能会比较差。
如果已知存储数据的大小,并且添加的元素都是放到末尾,那么就可以在初始化ArrayList时指定大小,这种情况插入的速度不会差,反而要比其他的list性能更好.

LinkedList

LinkedList插入到指定位置:
添加元素操作只会改变前后元素的前后指针,指针将会指向添加的新元素,所以相比ArrayList的添加操作来说,LinkedList的性能优势明显。

删除元素

ArrayList

ArrayList的删除方法和添加任意位置元素的方法是有些相同的。ArrayList在每一次有效的删除元素操作之后,都要进行数组的重组,并且删除的元素位置越靠前,数组重组的开销就越大。

LinkedList

在LinkedList删除元素的操作中,首先要通过循环找到要删除的元素,如果要删除的位置处于List的前半段,就从前往后找;若其位置处于后半段,就从后往前找。

这样做的话,无论要删除较为靠前或较为靠后的元素都是非常高效的,但如果List拥有大量元素,移除的元素又在List的中间段,那效率相对来说会很低。

遍历元素

由于ArrayList是基于数组实现的,所以在获取元素的时候是非常快捷的。

LinkedList的获取元素操作实现跟LinkedList的删除元素操作基本类似,通过前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的
LinkedList循环遍历时,可以使用iterator方式迭代循环,直接拿到元素。

这篇关于ArrayList与LinkedList的性能差别的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1035188

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

黑神话,XSKY 星飞全闪单卷性能突破310万

当下,云计算仍然是企业主要的基础架构,随着关键业务的逐步虚拟化和云化,对于块存储的性能要求也日益提高。企业对于低延迟、高稳定性的存储解决方案的需求日益迫切。为了满足这些日益增长的 IO 密集型应用场景,众多云服务提供商正在不断推陈出新,推出具有更低时延和更高 IOPS 性能的云硬盘产品。 8 月 22 日 2024 DTCC 大会上(第十五届中国数据库技术大会),XSKY星辰天合正式公布了基于星

Java ArrayList扩容机制 (源码解读)

结论:初始长度为10,若所需长度小于1.5倍原长度,则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1:数组默认长度         2:这是一个共享的空数组实例,用于明确创建长度为0时的ArrayList ,比如通过 new ArrayList<>(0),ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动

PR曲线——一个更敏感的性能评估工具

在不均衡数据集的情况下,精确率-召回率(Precision-Recall, PR)曲线是一种非常有用的工具,因为它提供了比传统的ROC曲线更准确的性能评估。以下是PR曲线在不均衡数据情况下的一些作用: 关注少数类:在不均衡数据集中,少数类的样本数量远少于多数类。PR曲线通过关注少数类(通常是正类)的性能来弥补这一点,因为它直接评估模型在识别正类方面的能力。 精确率与召回率的平衡:精确率(Pr

LinkedList的源码

package java.util;public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable{// 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。private transient Entry<E>

SQL2005 性能监视器计数器错误解决方法

【系统环境】 windows 2003 +sql2005 【问题状况】 用户在不正当删除SQL2005后会造成SQL2005 性能监视器计数器错误,如下图 【解决办法】 1、在 “开始” --> “运行”中输入 regedit,开启注册表编辑器,定位到 [HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVer

Linux性能分析工具合集

Linux性能分析工具合集 工具合集主要包含以下各种工具,对于了解Linux系统结构、网络结构、内核层次具有一定的帮助。 Linux Performance Observability ToolsLinux Static Performance ToolsLinux Performance Benchmark ToolsLinux Performance Tuning ToolsLinux