当前位置: 首页 > 科技观察

ArrayList和LinkedList使用不当,性能差距会这么大!

时间:2023-03-13 05:27:28 科技观察

前言面试的时候经常被问到几个问题:ArrayList和LinkedList的区别,相信大部分朋友都能回答:ArrayList是基于数组实现的,LinkedList是基于链表实现的。随机访问一个List时,ArrayList比LinkedList等效率更高。当被问及ArrayList和LinkedList的使用场景是什么时,大部分朋友的回答可能是:ArrayList和LinkedList增删元素时,LinkedList的效率更高比ArrayList高,遍历时ArrayList的效率比LinkedList高,这个答案准确吗?今天就来研究一下吧!先简单介绍一下ArrayList和LinkedList的原理实现!源码分析ArrayList实现类publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.SerializableArrayList实现了List接口,继承了AbstractList抽象类。ArrayList还实现了Cloneable接口和Serializable接口,所以他可以实现克隆和序列化。ArrayList还实现了RandomAccess接口,这是一个flag接口,标志“只要实现了该接口的List类就可以实现快速随机访问”。基本属性ArrayList属性主要由数组长度大小、对象数组elementData、初始化容量default_capacity组成,其中初始化容量默认大小为10。//默认初始化容量privatestaticfinalintDEFAULT_CAPACITY=10;//对象数组transientObject[]elementData;//数组长度privateintsize;从ArrayList属性来看,elementData是通过关键字transient修饰的,transient关键字修饰字段表示该属性不会被序列化。但是ArrayList实际上实现了序列化接口。为什么?因为ArrayList的数组是基于动态扩展的,并不是所有分配的内存空间都存放数据。如果使用外部序列化方式对数组进行序列化,则会对整个数组进行序列化。为了避免序列化这些没有数据存储的内存空间,ArrayList提供了两个私有方法writeObject和readObject来自己完成序列化和反序列化,这在序列化和反序列化数组时节省了空间和时间。所以使用transient修改数组是为了防止对象数组被其他外部方法序列化。ArrayList自定义序列化方法如下:初始化有三种初始化方法:不带参数直接初始化、指定大小初始化、指定初始数据初始化。源码如下:向ArrayList添加元素时,如果存储的元素超过其现有大小,则会计算该元素的大小,然后动态扩容。数组的扩容会导致整个数组的内存拷贝。因此,我们在初始化ArrayList时,可以通过第一个构造函数合理指定数组的初始大小,有助于减少数组的扩充次数,从而提高系统性能。注意:ArrayList无参构造函数在初始化时,默认大小为空数组,而不是我们常说的10。10为第一次加法时展开后的数组值。添加元素给ArrayList添加元素有两种方式,一种是直接向数组末尾添加元素,另一种是向任意位置添加元素。publicbooleanadd(Ee){ensureCapacityInternal(size+1);//IncrementsmodCount!!elementData[size++]=e;returntrue;}publicvoidadd(intindex,Eelement){rangeCheckForAdd(index);ensureCapacityInternal(size+1);//增量模数!!System.arraycopy(elementData,index,elementData,index+1,size-index);elementData[index]=element;size++;}这两种方法的相同点是在添加元素之前会先确认容量大小,如果如果容量足够大,则无需扩容;如果容量不够大,则按照原数组大小的1.5倍扩容,扩容后需要将数组复制到新分配的内存地址。下面是具体的源码:这两种方法也是有区别的。将元素添加到任何位置都会导致该位置之后的所有元素重新排列。向数组末尾添加元素不需要扩展。接下来,将没有元素重复排序过程。所以ArrayList的效率不一定在大量新增元素的场景下就慢。如果我们在初始化的时候就知道存储数据的大小,我们就可以在ArrayList初始化的时候指定数组的大小,而在添加元素的时候,只在数组的末尾添加元素,那么ArrayList的性能就会在添加大量元素的场景下并没有变差,但是ArrayList的性能要优于其他List集合。删除元素ArrayList删除元素的方式有很多种,比如根据数组索引删除、根据值删除或者批量删除等,原理和思路都差不多。ArrayList在每次有效的元素删除操作后都需要重组数组,删除的元素越早,数组重组的代价越大。我们选择按值删除来说明源码:遍历元素由于ArrayList是基于数组实现的,所以获取元素的速度非常快。publicEget(intindex){rangeCheck(index);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}LinkedListLinkedList是基于双向链表的数据结构实现的。在这个双向链表结构中,链表中的每个节点都可以向前或向后追踪。有如下几个概念:链表中的每个节点称为Node。Node有一个prev属性,代表上一个节点的位置,还有一个next属性,代表下一个节点的位置;first是双向链表的头节点,它的前一个节点为null。last是双向链表的尾节点,它的最后一个节点为null;当链表中没有数据时,first和last为同一个节点,前后点均为null;因为是双向链表,只要机器内存够大,没有Size限制。Node结构包含三部分:元素内容item、前指针prev和后指针next,代码如下。privatestaticclassNode{Eitem;//节点值??Nodenext;//下一个节点指向Nodeprev;//前一个节点指向//初始化参数顺序为:前一个节点,自身Node值,下一个节点Node(Nodeprev,Eelement,Nodenext){this.item=element;this.next=next;this.prev=prev;}}LinkedList由Node结构对象连接形成一个双向链表。实现类LinkedList实现了List接口和Deque接口,继承了AbstractSequentialList抽象类。LinkedList同时实现了List类型和Queue类型的特点;LinkedList还实现了Cloneable和Serializable接口。和ArrayList一样,可以实现克隆和排序变化。由于LinkedList存储数据的内存地址是不连续的,但不连续的地址是通过指针定位的,因此LinkedList不支持随机快速访问,LinkedList无法实现RandomAccess接口。publicclassLinkedListtextendsAbstractSequentialListimplementsList,Deque,Cloneable,java.io.Serializable基本属性transientintsize=0;transientNodefirst;transientNodelast;我们可以看到这三个属性都是被transient修饰的,原因很简单,我们在序列化Serialization的时候不会只对齐头尾,所以LinkedList也实现了readObject和writeObject来进行序列化和反序列化。下面是LinkedList自定义序列化的方法。节点查询链表查询某个节点比较慢,需要循环查找。我们来看看LinkedList的源码是如何寻找节点的:LinkedList并没有采用从头到尾循环的方式,而是采用了简单的二分法。首先检查索引是在链表的前半部分还是后半部分。如果是前半部分,就从头开始看,反之亦然。这样循环次数至少减少了一半,提高了搜索性能。添加元素向LinkedList添加元素的实现非常简单,但是添加元素的方法有很多种。默认的add(Ee)方法是将添加的元素添加到队列尾部。首先将最后一个元素替换成一个临时变量生成一个新的Node节点对象,然后将最后一个引用指向新的节点对象。previouslastobjectprevious指针指向新节点对象。LinkedList还有一个方法可以将元素添加到任意位置。如果我们在任意两个元素的中间添加一个元素,添加元素的操作只会改变前后元素的前后指针,指针会指向新添加的元素,所以相对于ArrayList来说加法操作,LinkedList的性能优势很明显。删除元素在LinkedList中删除元素的操作,首先要通过循环找到要删除的元素。如果要删除的位置在List的前半部分,我们就从前往后查找;如果位置在下半场,我们会从后场寻找。这样删除相对靠前或者靠后的元素效率很高,但是如果List元素比较多,删除的元素在List的中间,效率会比较低。遍历元素LinkedList获取元素的操作与LinkedList删除元素的操作基本类似。通过前半部分和后半部分循环查找对应的元素,但是这种方式查询元素的效率非常低,尤其是在for循环遍历的情况下,每次循环都会遍历一半的List。所以当LinkedList循环的时候,我们可以使用iterator来迭代循环,直接获取我们的元素,而不用通过循环查找List。分析测试新元素操作性能测试测试用例源码:ArrayList:https://paste.ubuntu.com/p/gktBvjgMGk/LinkedList:https://paste.ubuntu.com/p/3jQrY2XMPr/测试结果:通过这个分组测试,我们可以知道LinkedList添加元素的效率不一定比ArrayList高。从集合头部开始添加元素由于ArrayList是由数组实现的,所以在向数组头部添加元素时,需要复制头部之后的数据并重新排列,效率很低;LinkedList基于链表,在添加元素时,先通过循环找到添加元素的位置。如果要添加的位置在List的前半部分,则从前向后查找;如果它的位置在下半场,则从后往前搜索。因此,LinkedList将元素添加到头部是非常高效的。从集合中间位置开始添加元素ArrayList在数组中间添加元素时,还需要复制一些数据重新排列,效率不是很高;LinkedList向中间位置添加元素,这是添加元素效率最低的,因为靠近中间位置,添加元素前的循环查找是遍历元素最多的操作。从集合的尾部开始添加元素,在向尾部添加元素的操作中,在没有扩容的情况下,ArrayList的效率要高于LinkedList。这是因为ArrayList在末尾添加元素时不需要复制和重新排列数据,效率很高。LinkedList虽然不需要循环查找元素,但是LinkedList有更多的新对象和对象指针变化的过程,所以效率比ArrayList要低。注意:这是在不动态扩展阵列容量的情况下进行的测试。如果有动态扩容,ArrayList的效率也会降低。删除元素操作性能测试ArrayList和LinkedList删除元素操作测试结果和添加元素操作测试结果非常接近!结论:如果需要在List的头部进行大量的插入删除操作,那么直接选择LinkedList。否则,ArrayList就可以了。遍历元素操作性能测试测试用例源码:ArrayList:https://paste.ubuntu.com/p/ZNWc9H2pYm/LinkedList:https://paste.ubuntu.com/p/xSk4nHDHvN/测试结果:我们可以看到,LinkedList的for循环性能最差,而ArrayList的for循环性能最好。这是因为LinkedList是基于链表实现的。使用for循环时,每次for循环都会遍历一半的List,严重影响遍历效率;ArrayList是基于数组实现的,实现了RandomAccess接口标志。这意味着ArrayList可以实现快速的随机访问,所以for循环非常高效。LinkedList的迭代循环遍历和ArrayList的迭代循环遍历性能不相上下,也不会太差,所以在遍历LinkedList的时候一定要避免使用for循环遍历。