性能优化(一):ArrayList还是LinkedList?

引言

集合作为一种存储数据的容器,是我们日常开发中使用最频繁的对象类型之一。JDK为开发者提供了一系列的集合类型,这些集合类型使用不同的数据结构来实现。因此,不同的集合类型,使用场景也不同。

很多同学在面试的时候,经常会被问到集合的相关问题,比较常见的有ArrayList和LinkedList的区别。

相信大部分同学都能回答上:“ArrayList是基于数组实现,LinkedList是基于链表实现。”

而在回答使用场景的时候,我发现大部分同学的答案是:“ArrayList和LinkedList在新增、删除元素时,LinkedList的效率要高于 ArrayList,而在遍历的时候,ArrayList的效率要高于LinkedList。”这个回答是否准确呢?今天这一讲就带你验证。

初识List接口

在学习List集合类之前,我们先来通过这张图,看下List集合类的接口和类的实现关系:

我们可以看到ArrayList、Vector、LinkedList集合类继承了AbstractList抽象类,而AbstractList实现了List接口,同时也继承了AbstractCollection抽象类。ArrayList、Vector、LinkedList又根据自我定位,分别实现了各自的功能。

ArrayList和Vector使用了数组实现,这两者的实现原理差不多,LinkedList使用了双向链表实现。基础铺垫就到这里,接下来,我们就详细地分析下ArrayList和LinkedList的源码实现。

ArrayList是如何实现的?

ArrayList很常用,先来几道测试题,自检下你对ArrayList的了解程度。

问题1:我们在查看ArrayList的实现类源码时,你会发现对象数组elementData使用了transient修饰,我们知道transient关键字修饰该属性,则表示该属性不会被序列化,然而我们并没有看到文档中说明ArrayList不能被序列化,这是为什么?

问题2:我们在使用ArrayList进行新增、删除时,经常被提醒“使用ArrayList做新增删除操作会影响效率”。那是不是ArrayList在大量新增元素的场景下效率就一定会变慢呢?

问题3:如果让你使用for循环以及迭代循环遍历一个ArrayList,你会使用哪种方式呢?原因是什么?

如果你对这几道测试都没有一个全面的了解,那就跟我一起从数据结构、实现原理以及源码角度重新认识下ArrayList吧。

1.ArrayList实现类

ArrayList实现了List接口,继承了AbstractList抽象类,底层是数组实现的,并且实现了自增扩容数组大小。

ArrayList还实现了Cloneable接口和Serializable接口,所以他可以实现克隆和序列化。

ArrayList还实现了RandomAccess接口。你可能对这个接口比较陌生,不知道具体的用处。通过代码我们可以发现,这个接口其实是一个空接口,什么也没有实现,那ArrayList为什么要去实现它呢?

其实RandomAccess接口是一个标志接口,他标志着“只要实现该接口的List类,都能实现快速随机访问”。

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

2.ArrayList属性

ArrayList属性主要由数组长度size、对象数组elementData、初始化容量default_capacity等组成, 其中初始化容量默认大小为10。

  //默认初始化容量private static final int DEFAULT_CAPACITY = 10;//对象数组transient Object[] elementData; //数组长度private int size;

从ArrayList属性来看,它没有被任何的多线程关键字修饰,但elementData被关键字transient修饰了。这就是我在上面提到的第一道测试题:transient关键字修饰该字段则表示该属性不会被序列化,但ArrayList其实是实现了序列化接口,这到底是怎么回事呢?

这还得从“ArrayList是基于数组实现“开始说起,由于ArrayList的数组是基于动态扩增的,所以并不是所有被分配的内存空间都存储了数据。

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

因此使用transient修饰数组,是防止对象数组被其他外部方法序列化。

3.ArrayList构造函数

ArrayList类实现了三个构造函数,第一个是创建ArrayList对象时,传入一个初始化值;第二个是默认创建一个空数组对象;第三个是传入一个集合类型进行初始化。

当ArrayList新增元素时,如果所存储的元素已经超过其已有大小,它会计算元素大小后再进行动态扩容,数组的扩容会导致整个数组进行一次内存复制。因此,我们在初始化ArrayList时,可以通过第一个构造函数合理指定数组初始大小,这样有助于减少数组的扩容次数,从而提高系统性能。

 public ArrayList(int initialCapacity) {//初始化容量不为零时,将根据初始化值创建数组大小if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//初始化容量为零时,使用默认的空数组this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}public ArrayList() {//初始化默认为空数组this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

4.ArrayList新增元素

ArrayList新增元素的方法有两种,一种是直接将元素加到数组的末尾,另外一种是添加元素到任意位置。

 public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}

两个方法的相同之处是在添加元素之前,都会先确认容量大小,如果容量够大,就不用进行扩容;如果容量不够大,就会按照原来数组的1.5倍大小进行扩容,在扩容之后需要将数组复制到新分配的内存地址。

  private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}

当然,两个方法也有不同之处,添加元素到任意位置,会导致在该位置后的所有元素都需要重新排列,而将元素添加到数组的末尾,在没有发生扩容的前提下,是不会有元素复制排序过程的。

这里你就可以找到第二道测试题的答案了。如果我们在初始化时就比较清楚存储数据的大小,就可以在ArrayList初始化时指定数组容量大小,并且在添加元素时,只在数组末尾添加元素,那么ArrayList在大量新增元素的场景下,性能并不会变差,反而比其他List集合的性能要好。

5.ArrayList删除元素

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

 public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}

6.ArrayList遍历元素

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

  public E get(int index) {rangeCheck(index);return elementData(index);}E elementData(int index) {return (E) elementData[index];}

LinkedList是如何实现的?

虽然LinkedList与ArrayList都是List类型的集合,但LinkedList的实现原理却和ArrayList大相径庭,使用场景也不太一样。

LinkedList是基于双向链表数据结构实现的,LinkedList定义了一个Node结构,Node结构中包含了3个部分:元素内容item、前指针prev以及后指针next,代码如下。

 private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

总结一下,LinkedList就是由Node结构对象连接而成的一个双向链表。在JDK1.7之前,LinkedList中只包含了一个Entry结构的header属性,并在初始化的时候默认创建一个空的Entry,用来做header,前后指针指向自己,形成一个循环双向链表。

在JDK1.7之后,LinkedList做了很大的改动,对链表进行了优化。链表的Entry结构换成了Node,内部组成基本没有改变,但LinkedList里面的header属性去掉了,新增了一个Node结构的first属性和一个Node结构的last属性。这样做有以下几点好处:

  • first/last属性能更清晰地表达链表的链头和链尾概念;

  • first/last方式可以在初始化LinkedList的时候节省new一个Entry;

  • first/last方式最重要的性能优化是链头和链尾的插入删除操作更加快捷了。

这里同ArrayList的讲解一样,我将从数据结构、实现原理以及源码分析等几个角度带你深入了解LinkedList。

1.LinkedList实现类

LinkedList类实现了List接口、Deque接口,同时继承了AbstractSequentialList抽象类,LinkedList既实现了List类型又有Queue类型的特点;LinkedList也实现了Cloneable和Serializable接口,同ArrayList一样,可以实现克隆和序列化。

由于LinkedList存储数据的内存地址是不连续的,而是通过指针来定位不连续地址,因此,LinkedList不支持随机快速访问,LinkedList也就不能实现RandomAccess接口。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.LinkedList属性

我们前面讲到了LinkedList的两个重要属性first/last属性,其实还有一个size属性。我们可以看到这三个属性都被transient修饰了,原因很简单,我们在序列化的时候不会只对头尾进行序列化,所以LinkedList也是自行实现readObject和writeObject进行序列化与反序列化。

  transient int size = 0;transient Node<E> first;transient Node<E> last;

3.LinkedList新增元素

LinkedList添加元素的实现很简洁,但添加的方式却有很多种。默认的add (Ee)方法是将添加的元素加到队尾,首先是将last元素置换到临时变量中,生成一个新的Node节点对象,然后将last引用指向新节点对象,之前的last对象的前指针指向新节点对象。

 public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}

LinkedList也有添加元素到任意位置的方法,如果我们是将元素添加到任意两个元素的中间位置,添加元素操作只会改变前后元素的前后指针,指针将会指向添加的新元素,所以相比ArrayList的添加操作来说,LinkedList的性能优势明显。

 public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}

4.LinkedList删除元素

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

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

5.LinkedList遍历元素

LinkedList的获取元素操作实现跟LinkedList的删除元素操作基本类似,通过分前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的,特别是在for循环遍历的情况下,每一次循环都会去遍历半个List。

所以在LinkedList循环遍历时,我们可以使用iterator方式迭代循环,直接拿到我们的元素,而不需要通过循环查找List。

总结

前面我们已经从源码的实现角度深入了解了ArrayList和LinkedList的实现原理以及各自的特点。如果你能充分理解这些内容,很多实际应用中的相关性能问题也就迎刃而解了。

就像如果现在还有人跟你说,“ArrayList和LinkedList在新增、删除元素时,LinkedList的效率要高于ArrayList,而在遍历的时候,ArrayList的效率要高于LinkedList”,你还会表示赞同吗?

现在我们不妨通过几组测试来验证一下。这里因为篇幅限制,所以我就直接给出测试结果了,对应的测试代码你可以访问Github查看和下载。

1.ArrayList和LinkedList新增元素操作测试

  • 从集合头部位置新增元素

  • 从集合中间位置新增元素

  • 从集合尾部位置新增元素

测试结果(花费时间):

  • ArrayList>LinkedList

  • ArrayList<LinkedList

  • ArrayList<LinkedList

通过这组测试,我们可以知道LinkedList添加元素的效率未必要高于ArrayList。

由于ArrayList是数组实现的,而数组是一块连续的内存空间,在添加元素到数组头部的时候,需要对头部以后的数据进行复制重排,所以效率很低;而LinkedList是基于链表实现,在添加元素的时候,首先会通过循环查找到添加元素的位置,如果要添加的位置处于List的前半段,就从前往后找;若其位置处于后半段,就从后往前找。因此LinkedList添加元素到头部是非常高效的。

同上可知,ArrayList在添加元素到数组中间时,同样有部分数据需要复制重排,效率也不是很高;LinkedList将元素添加到中间位置,是添加元素最低效率的,因为靠近中间位置,在添加元素之前的循环查找是遍历元素最多的操作。

而在添加元素到尾部的操作中,我们发现,在没有扩容的情况下,ArrayList的效率要高于LinkedList。这是因为ArrayList在添加元素到尾部的时候,不需要复制重排数据,效率非常高。而LinkedList虽然也不用循环查找元素,但LinkedList中多了new对象以及变换指针指向对象的过程,所以效率要低于ArrayList。

说明一下,这里我是基于ArrayList初始化容量足够,排除动态扩容数组容量的情况下进行的测试,如果有动态扩容的情况,ArrayList的效率也会降低。

2.ArrayList和LinkedList删除元素操作测试

  • 从集合头部位置删除元素

  • 从集合中间位置删除元素

  • 从集合尾部位置删除元素

测试结果(花费时间):

  • ArrayList>LinkedList

  • ArrayList<LinkedList

  • ArrayList<LinkedList

ArrayList和LinkedList删除元素操作测试的结果和添加元素操作测试的结果很接近,这是一样的原理,我在这里就不重复讲解了。

3.ArrayList和LinkedList遍历元素操作测试

  • for(;;)循环

  • 迭代器迭代循环

测试结果(花费时间):

  • ArrayList<LinkedList

  • ArrayList≈LinkedList

我们可以看到,LinkedList的for循环性能是最差的,而ArrayList的for循环性能是最好的。

这是因为LinkedList基于链表实现的,在使用for循环的时候,每一次for循环都会去遍历半个List,所以严重影响了遍历的效率;ArrayList则是基于数组实现的,并且实现了RandomAccess接口标志,意味着ArrayList可以实现快速随机访问,所以for循环效率非常高。

LinkedList的迭代循环遍历和ArrayList的迭代循环遍历性能相当,也不会太差,所以在遍历LinkedList时,我们要切忌使用for循环遍历。

思考题

我们通过一个使用for循环遍历删除操作ArrayList数组的例子,思考下ArrayList数组的删除操作应该注意的一些问题。

public static void main(String[] args){ArrayList<String> list = new ArrayList<String>();list.add("a");list.add("a");list.add("b");list.add("b");list.add("c");list.add("c");remove(list);//删除指定的“b”元素for(int i=0; i<list.size(); i++)("c")()()(s : list) {System.out.println("element : " + s)list.get(i)}}

从上面的代码来看,我定义了一个ArrayList数组,里面添加了一些元素,然后我通过remove删除指定的元素。请问以下两种写法,哪种是正确的?

写法1:

public static void remove(ArrayList<String> list) {Iterator<String> it = list.iterator();while (it.hasNext()) {String str = it.next();if (str.equals("b")) {it.remove();}}}

写法2:

public static void remove(ArrayList<String> list) {for (String s : list){if (s.equals("b")) {list.remove(s);}}}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flutter笔记:使用Flutter私有类涉及的授权协议问题

Flutter笔记 使用Flutter私有类涉及的授权协议问题 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.cs…

使用docker-compose编排lnmp(dockerfile)完成wordpress

文章目录 使用docker-compose编排lnmp&#xff08;dockerfile&#xff09;完成wordpress1、服务器环境2、Docker、Docker-Compose环境安装2.1 安装Docker环境2.2 安装Docker-Compose 3、nginx3.1 新建目录&#xff0c;上传安装包3.2 编辑Dockerfile脚本3.3 准备nginx.conf配置文…

【哈希表】Leetcode 14. 最长公共前缀

题目讲解 14. 最长公共前缀 算法讲解 我们使用当前第一个字符串中的与后面的字符串作比较&#xff0c;如果第一个字符串中的字符没有出现在后面的字符串中&#xff0c;我们就直接返回&#xff1b;反之当容器中的所有字符串都遍历完成&#xff0c;说明所有的字符串都在该位置…

Java枚举(enum)

“今天我们来学习枚举吧&#xff0c;三妹&#xff01;”我说&#xff0c;“同学让你去她家玩了两天&#xff0c;感觉怎么样呀&#xff1f;” “心情放松了不少。”三妹说&#xff0c;“可以开始学 Java 了&#xff0c;二哥。” “OK。” “枚举&#xff08;enum&#xff09;…

Linux服务器安全基础 - 查看入侵痕迹

1. 常见系统日志 /var/log/cron 记录了系统定时任务相关的日志 /var/log/dmesg 记录了系统在开机时内核自检的信息&#xff0c;也可以使用dmesg命令直接查看内核自检信息 /var/log/secure:记录登录系统存取数据的文件;例如:pop3,ssh,telnet,ftp等都会记录在此. /var/log/btmp:记…

【数据结构】链表专题2

前言 本篇博客继续探讨有关链表的专题&#xff0c;这片博客的题&#xff0c;提前打个预防针&#xff0c;有点意思哦&#xff0c;哈哈哈&#xff0c;话不多说&#xff0c;进入正文 &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏&#xff1a;数据结构 若有问题 评论…

ubuntu下安装配置python3.11

方案1 添加仓库&#xff1a; $ sudo add-apt-repository ppa:deadsnakes/ppa $ sudo apt update $ sudo apt install python3.11然后查看有多少个python版本已经安装了&#xff1a; ls -l /usr/bin/python*python2.7,python 3.8 ,python 3.11. 然后&#xff0c;设置系统默认…

【IC设计】CRC(循环冗余校验)

目录 理论解读CRC应用CRC算法参数解读常见CRC参数模型 设计实战校招编程题分类串行输入、并行计算、串行输出**串行计算、串行输出&#xff08;线性移位寄存器&#xff09;LSFR线性移位寄存器&#xff08;并转串&#xff09;(并行计算)模二除 总结——串行、并行计算的本质参考…

【数据结构】--- 深入剖析二叉树(上篇)--- 初识树和二叉树

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; 数据结构之旅 &#x1f3e0; 初识树 &#x1f4d2; 树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点…

旅游系列之:庐山美景

旅游系列之&#xff1a;庐山美景 一、路线二、住宿二、庐山美景 一、路线 庐山北门乘坐大巴上山&#xff0c;住在上山的酒店东线大巴游览三叠泉&#xff0c;不需要乘坐缆车&#xff0c;步行上下三叠泉即可&#xff0c;线路很短 二、住宿 长江宾馆庐山分部 二、庐山美景

SpringBoot 快速开始 Dubbo RPC

文章目录 SpringBoot 快速开始 Dubbo RPC下载 Nacos项目启动项目的创建创建主项目接口定义服务的创建Dubbo 服务提供者的创建服务的消费者创建 添加依赖给 Provider、Consumer 添加依赖 开始写代码定义接口在 Provider 中实现在 Consumer 里面使用创建启动类 注册中心配置启动 …

基于Spring Boot的校园博客系统设计与实现

基于Spring Boot的校园博客系统设计与实现 开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/idea 系统部分展示 系统功能界面图&#xff0c;在系统首页可以查看首页、文…

状态模式

文章目录 1.UML类图2.状态基类3.状态实现类3.状态机管理类使用示例 1.UML类图 2.状态基类 public abstract class State {public string? Name { get; set; }public StateMachine? StateMachine {get; set;}public abstract void Exit();public abstract void Enter(); }3.…

(三)Appdesigner-界面转换及数据导入和保存

提示&#xff1a;文章为系列文章&#xff0c;可以在对应学习专栏里面进行学习。对应资源已上传 目录 前言 一、Appdesigner是什么&#xff1f; 二、界面切换 三、数据导入及保存 &#xff08;一&#xff09;数据导入 &#xff08;二&#xff09;数据保存 总结 前言 Appd…

2024年第六届先进材料、机械和制造国际会议(AMMM 2024)即将召开!

2024年第六届先进材料、机械和制造国际会议&#xff08;AMMM 2024&#xff09;将于2024年9月6-8日在日本东京举行。AMMM 2024将以国际材料&#xff0c;机械和制造为主题&#xff0c;吸引到来自多个领域的研究人员和学者相聚在一起分享知识&#xff0c;讨论想法&#xff0c;并了…

【力扣】203、环形链表 II

142. 环形链表 II 要解决这道题&#xff0c;首先需要对问题进行拆解&#xff1a; 确定链表是否存在环确定环的入口点 如何判断是否存在环呢&#xff1f;这个比较容易想到&#xff0c;使用快慢指针即可判断链表是否存在环。我们定义两个指针&#xff1a; ListNode slow head…

【RabbitMQ】可靠性策略(幂等,消息持久化)

MQ可靠性策略 发送者的可靠性问题生产者的重连生产者确认 MQ的可靠性数据持久化Lazy Queue 消费者的可靠性问题消费者确认机制消息失败处理 业务幂等性简答问题 发送者的可靠性问题 生产者的重连 可能存在由于网络波动&#xff0c;出现的客户端连接MQ失败&#xff0c;我们可以…

10G MAC层设计系列-(4)MAC TX模块

一、前言 MAC TX模块就是要将IP层传输过来的数据封装前导码、MAC地址、帧类型以及进行CRC校验&#xff0c;并与CRC值一块组成以太网帧。 二、模块设计 首先对输入的数据进行缓存&#xff0c;原因是在之后要进行封装MAC帧头&#xff0c;所以需要控制数据流的流动 FIFO_DATA_6…

neo4j 的插入速度为什么越来越慢,可能是使用了过多图谱查询操作

文章目录 背景描述分析解决代码参考neo4j 工具类Neo4jDriver知识图谱构建效果GuihuaNeo4jClass 背景描述 使用 tqdm 显示&#xff0c;处理的速度&#xff1b; 笔者使用 py2neo库&#xff0c;调用 neo4j 的API 完成节点插入&#xff1b; 有80万条数据需要插入到neo4j图数据中&am…

手机恢复出厂设置ip地址会变吗

当我们对手机进行恢复出厂设置时&#xff0c;很多人会担心手机的IP地址是否会发生变化。IP地址对于手机的网络连接至关重要&#xff0c;它决定了手机在网络中的身份和位置。那么&#xff0c;手机恢复出厂设置后&#xff0c;IP地址到底会不会发生变化呢&#xff1f;虎观代理小二…