arraylist和linkedlist有何异同array list 和linked list的区别

ArrayList和LinkedList有什么区别，是面试官非常喜欢问的一个问题。可能大部分小伙伴和我一样，能回答出“ArrayList是基于数组实现的，LinkedList是基于双向链表实现的。”

关于这一点，我之前的文章里也提到过了。但说实话，这样苍白的回答并不能令面试官感到满意，他还想知道的更多。

那假如小伙伴们继续做出下面这样的回答：

“ArrayList在新增和删除元素时，因为涉及到数组复制，所以效率比LinkedList低，而在遍历的时候，ArrayList的效率要高于LinkedList。”

面试官会感到满意吗？我只能说，如果面试官比较仁慈的话，他可能会让我们回答下一个问题；否则的话，他会让我们回家等通知，这一等，可能意味着杳无音讯了。

为什么会这样呢？为什么为什么？回答的不对吗？

暴躁的小伙伴请喝口奶茶冷静一下。冷静下来后，请随我来，让我们一起肩并肩、手拉手地深入地研究一下ArrayList和LinkedList的数据结构、实现原理以及源码，可能神秘的面纱就揭开了。

01、ArrayList是如何实现的？

ArrayList实现了List接口，继承了AbstractList抽象类，底层是基于数组实现的，并且实现了动态扩容。

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{privatestaticfinalintDEFAULT_CAPACITY=10;transientObject[]elementData;privateintsize;}

ArrayList还实现了RandomAccess接口，这是一个标记接口：

publicinterfaceRandomAccess{}

内部是空的，标记“实现了这个接口的类支持快速（通常是固定时间）随机访问”。快速随机访问是什么意思呢？就是说不需要遍历，就可以通过下标（索引）直接访问到内存地址。

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}

ArrayList还实现了Cloneable接口，这表明ArrayList是支持拷贝的。ArrayList内部的确也重写了Object类的clone()方法。

publicObjectclone(){try{ArrayList<?>v=(ArrayList<?>)super.clone();v.elementData=Arrays.copyOf(elementData,size);v.modCount=0;returnv;}catch(CloneNotSupportedExceptione){//thisshouldn'thappen,sinceweareCloneablethrownewInternalError(e);}}

ArrayList还实现了Serializable接口，同样是一个标记接口：

publicinterfaceSerializable{}

内部也是空的，标记“实现了这个接口的类支持序列化”。序列化是什么意思呢？Java的序列化是指，将对象转换成以字节序列的形式来表示，这些字节序中包含了对象的字段和方法。序列化后的对象可以被写到数据库、写到文件，也可用于网络传输。

眼睛雪亮的小伙伴可能会注意到，ArrayList中的关键字段elementData使用了transient关键字修饰，这个关键字的作用是，让它修饰的字段不被序列化。

这不前后矛盾吗？一个类既然实现了Serilizable接口，肯定是想要被序列化的，对吧？那为什么保存关键数据的elementData又不想被序列化呢?

这还得从“ArrayList是基于数组实现的”开始说起。大家都知道，数组是定长的，就是说，数组一旦声明了，长度（容量）就是固定的，不能像某些东西一样伸缩自如。这就很麻烦，数组一旦装满了，就不能添加新的元素进来了。

ArrayList不想像数组这样活着，它想能屈能伸，所以它实现了动态扩容。一旦在添加元素的时候，发现容量用满了s==elementData.length，就按照原来数组的1.5倍（oldCapacity>>1）进行扩容。扩容之后，再将原有的数组复制到新分配的内存地址上Arrays.copyOf(elementData,newCapacity)。

privatevoidadd(Ee,Object[]elementData,ints){if(s==elementData.length)elementData=grow();elementData[s]=e;size=s+1;}privateObject[]grow(){returngrow(size+1);}privateObject[]grow(intminCapacity){intoldCapacity=elementData.length;if(oldCapacity>0||elementData!=DEFAULTCAPACITY_EMPTY_ELEMENTDATA){intnewCapacity=ArraysSupport.newLength(oldCapacity,minCapacity-oldCapacity,/*minimumgrowth*/oldCapacity>>1/*preferredgrowth*/);returnelementData=Arrays.copyOf(elementData,newCapacity);}else{returnelementData=newObject[Math.max(DEFAULT_CAPACITY,minCapacity)];}}

动态扩容意味着什么？大家伙想一下。嗯，还是我来告诉大家答案吧，有点迫不及待。

意味着数组的实际大小可能永远无法被填满的，总有多余出来空置的内存空间。

比如说，默认的数组大小是10，当添加第11个元素的时候，数组的长度扩容了1.5倍，也就是15，意味着还有4个内存空间是闲置的，对吧？

序列化的时候，如果把整个数组都序列化的话，是不是就多序列化了4个内存空间。当存储的元素数量非常非常多的时候，闲置的空间就非常非常大，序列化耗费的时间就会非常非常多。

于是，ArrayList做了一个愉快而又聪明的决定，内部提供了两个私有方法writeObject和readObject来完成序列化和反序列化。

privatevoidwriteObject(java.io.ObjectOutputStreams)throwsjava.io.IOException{//Writeoutelementcount,andanyhiddenstuffintexpectedModCount=modCount;s.defaultWriteObject();//Writeoutsizeascapacityforbehavioralcompatibilitywithclone()s.writeInt(size);//Writeoutallelementsintheproperorder.for(inti=0;i<size;i++){s.writeObject(elementData[i]);}if(modCount!=expectedModCount){thrownewConcurrentModificationException();}}

从writeObject方法的源码中可以看得出，它使用了ArrayList的实际大小size而不是数组的长度（elementData.length）来作为元素的上限进行序列化。

此处应该有掌声啊！不是为我，为Java源码的作者们，他们真的是太厉害了，可以用两个词来形容他们——殚精竭虑、精益求精。

02、LinkedList是如何实现的？

LinkedList是一个继承自AbstractSequentialList的双向链表，因此它也可以被当作堆栈、队列或双端队列进行操作。

publicclassLinkedList<E>extendsAbstractSequentialList<E>implementsList<E>,Deque<E>,Cloneable,java.io.Serializable{transientintsize=0;transientNode<E>first;transientNode<E>last;}

LinkedList内部定义了一个Node节点，它包含3个部分：元素内容item，前引用prev和后引用next。代码如下所示：

privatestaticclassNode<E>{Eitem;LinkedList.Node<E>next;LinkedList.Node<E>prev;Node(LinkedList.Node<E>prev,Eelement,LinkedList.Node<E>next){this.item=element;this.next=next;this.prev=prev;}}

LinkedList还实现了Cloneable接口，这表明LinkedList是支持拷贝的。

LinkedList还实现了Serializable接口，这表明LinkedList是支持序列化的。眼睛雪亮的小伙伴可能又注意到了，LinkedList中的关键字段size、first、last都使用了transient关键字修饰，这不又矛盾了吗？到底是想序列化还是不想序列化？

答案是LinkedList想按照自己的方式序列化，来看它自己实现的writeObject()方法：

privatevoidwriteObject(java.io.ObjectOutputStreams)throwsjava.io.IOException{//Writeoutanyhiddenserializationmagics.defaultWriteObject();//Writeoutsizes.writeInt(size);//Writeoutallelementsintheproperorder.for(LinkedList.Node<E>x=first;x!=null;x=x.next)s.writeObject(x.item);}

发现没？LinkedList在序列化的时候只保留了元素的内容item，并没有保留元素的前后引用。这样就节省了不少内存空间，对吧？

那有些小伙伴可能就疑惑了，只保留元素内容，不保留前后引用，那反序列化的时候怎么办？

publicinterfaceRandomAccess{}0

注意for循环中的linkLast()方法，它可以把链表重新链接起来，这样就恢复了链表序列化之前的顺序。很妙，对吧？

和ArrayList相比，LinkedList没有实现RandomAccess接口，这是因为LinkedList存储数据的内存地址是不连续的，所以不支持随机访问。

03、ArrayList和LinkedList新增元素时究竟谁快？

前面我们已经从多个维度了解了ArrayList和LinkedList的实现原理和各自的特点。那接下来，我们就来聊聊ArrayList和LinkedList在新增元素时究竟谁快？

1）ArrayList

ArrayList新增元素有两种情况，一种是直接将元素添加到数组末尾，一种是将元素插入到指定位置。

添加到数组末尾的源码：

publicinterfaceRandomAccess{}1

很简单，先判断是否需要扩容，然后直接通过索引将元素添加到末尾。

插入到指定位置的源码：

publicinterfaceRandomAccess{}2

先检查插入的位置是否在合理的范围之内，然后判断是否需要扩容，再把该位置以后的元素复制到新添加元素的位置之后，最后通过索引将元素添加到指定的位置。这种情况是非常伤的，性能会比较差。

2）LinkedList

LinkedList新增元素也有两种情况，一种是直接将元素添加到队尾，一种是将元素插入到指定位置。

添加到队尾的源码：

publicinterfaceRandomAccess{}3

先将队尾的节点last存放到临时变量l中（不是说不建议使用I作为变量名吗？Java的作者们明知故犯啊），然后生成新的Node节点，并赋给last，如果l为null，说明是第一次添加，所以first为新的节点；否则将新的节点赋给之前last的next。

插入到指定位置的源码：

publicinterfaceRandomAccess{}4

先检查插入的位置是否在合理的范围之内，然后判断插入的位置是否是队尾，如果是，添加到队尾；否则执行linkBefore()方法。

在执行linkBefore()方法之前，会调用node()方法查找指定位置上的元素，这一步是需要遍历LinkedList的。如果插入的位置靠前前半段，就从队头开始往后找；否则从队尾往前找。也就是说，如果插入的位置越靠近LinkedList的中间位置，遍历所花费的时间就越多。

找到指定位置上的元素（succ）之后，就开始执行linkBefore()方法了，先将succ的前一个节点（prev）存放到临时变量pred中，然后生成新的Node节点（newNode），并将succ的前一个节点变更为newNode，如果pred为null，说明插入的是队头，所以first为新节点；否则将pred的后一个节点变更为newNode。

经过源码分析以后，小伙伴们是不是在想：“好像ArrayList在新增元素的时候效率并不一定比LinkedList低啊！”

当两者的起始长度是一样的情况下：

• 如果是从集合的头部新增元素，ArrayList花费的时间应该比LinkedList多，因为需要对头部以后的元素进行复制。

publicinterfaceRandomAccess{}5

num为10000，代码实测后的时间如下所示：

publicinterfaceRandomAccess{}6

ArrayList花费的时间比LinkedList要多很多。

• 如果是从集合的中间位置新增元素，ArrayList花费的时间搞不好要比LinkedList少，因为LinkedList需要遍历。

publicinterfaceRandomAccess{}7

num为10000，代码实测后的时间如下所示：

publicinterfaceRandomAccess{}8

ArrayList花费的时间比LinkedList要少很多很多。

• 如果是从集合的尾部新增元素，ArrayList花费的时间应该比LinkedList少，因为数组是一段连续的内存空间，也不需要复制数组；而链表需要创建新的对象，前后引用也要重新排列。

publicinterfaceRandomAccess{}9

num为10000，代码实测后的时间如下所示：

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}0

ArrayList花费的时间比LinkedList要少一些。

这样的结论和预期的是不是不太相符？ArrayList在添加元素的时候如果不涉及到扩容，性能在两种情况下（中间位置新增元素、尾部新增元素）比LinkedList好很多，只有头部新增元素的时候比LinkedList差，因为数组复制的原因。

当然了，如果涉及到数组扩容的话，ArrayList的性能就没那么可观了，因为扩容的时候也要复制数组。

04、ArrayList和LinkedList删除元素时究竟谁快？

1）ArrayList

ArrayList删除元素的时候，有两种方式，一种是直接删除元素（remove(Object)），需要直先遍历数组，找到元素对应的索引；一种是按照索引删除元素（remove(int)）。

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}1

但从本质上讲，都是一样的，因为它们最后调用的都是fastRemove(Object,int)方法。

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}2

从源码可以看得出，只要删除的不是最后一个元素，都需要数组重组。删除的元素位置越靠前，代价就越大。

2）LinkedList

LinkedList删除元素的时候，有四种常用的方式：

• remove(int)，删除指定位置上的元素

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}3

先检查索引，再调用node(int)方法（前后半段遍历，和新增元素操作一样）找到节点Node，然后调用unlink(Node)解除节点的前后引用，同时更新前节点的后引用和后节点的前引用：

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}4

• remove(Object)，直接删除元素

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}5

也是先前后半段遍历，找到要删除的元素后调用unlink(Node)。

• removeFirst()，删除第一个节点

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}6

删除第一个节点就不需要遍历了，只需要把第二个节点更新为第一个节点即可。

• removeLast()，删除最后一个节点

删除最后一个节点和删除第一个节点类似，只需要把倒数第二个节点更新为最后一个节点即可。

可以看得出，LinkedList在删除比较靠前和比较靠后的元素时，非常高效，但如果删除的是中间位置的元素，效率就比较低了。

这里就不再做代码测试了，感兴趣的小伙伴可以自己试试，结果和新增元素保持一致：

• 从集合头部删除元素时，ArrayList花费的时间比LinkedList多很多；
• 从集合中间位置删除元素时，ArrayList花费的时间比LinkedList少很多；
• 从集合尾部删除元素时，ArrayList花费的时间比LinkedList少一点。

我本地的统计结果如下所示，小伙伴们可以作为参考：

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}7

05、ArrayList和LinkedList遍历元素时究竟谁快？

1）ArrayList

遍历ArrayList找到某个元素的话，通常有两种形式：

• get(int)，根据索引找元素

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}8

由于ArrayList是由数组实现的，所以根据索引找元素非常的快，一步到位。

• indexOf(Object)，根据元素找索引

publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}EelementData(intindex){return(E)elementData[index];}9

根据元素找索引的话，就需要遍历整个数组了，从头到尾依次找。

2）LinkedList

遍历LinkedList找到某个元素的话，通常也有两种形式：

• get(int)，找指定位置上的元素

publicObjectclone(){try{ArrayList<?>v=(ArrayList<?>)super.clone();v.elementData=Arrays.copyOf(elementData,size);v.modCount=0;returnv;}catch(CloneNotSupportedExceptione){//thisshouldn'thappen,sinceweareCloneablethrownewInternalError(e);}}0

既然需要调用node(int)方法，就意味着需要前后半段遍历了。

• indexOf(Object)，找元素所在的位置

publicObjectclone(){try{ArrayList<?>v=(ArrayList<?>)super.clone();v.elementData=Arrays.copyOf(elementData,size);v.modCount=0;returnv;}catch(CloneNotSupportedExceptione){//thisshouldn'thappen,sinceweareCloneablethrownewInternalError(e);}}1

需要遍历整个链表，和ArrayList的indexOf()类似。

那在我们对集合遍历的时候，通常有两种做法，一种是使用for循环，一种是使用迭代器（Iterator）。

如果使用的是for循环，可想而知LinkedList在get的时候性能会非常差，因为每一次外层的for循环，都要执行一次node(int)方法进行前后半段的遍历。

publicObjectclone(){try{ArrayList<?>v=(ArrayList<?>)super.clone();v.elementData=Arrays.copyOf(elementData,size);v.modCount=0;returnv;}catch(CloneNotSupportedExceptione){//thisshouldn'thappen,sinceweareCloneablethrownewInternalError(e);}}2

那如果使用的是迭代器呢？

publicObjectclone(){try{ArrayList<?>v=(ArrayList<?>)super.clone();v.elementData=Arrays.copyOf(elementData,size);v.modCount=0;returnv;}catch(CloneNotSupportedExceptione){//thisshouldn'thappen,sinceweareCloneablethrownewInternalError(e);}}3

迭代器只会调用一次node(int)方法，在执行list.iterator()的时候：先调用AbstractSequentialList类的iterator()方法，再调用AbstractList类的listIterator()方法，再调用LinkedList类的listIterator(int)方法，如下图所示。

最后返回的是LinkedList类的内部私有类ListItr对象：

publicObjectclone(){try{ArrayList<?>v=(ArrayList<?>)super.clone();v.elementData=Arrays.copyOf(elementData,size);v.modCount=0;returnv;}catch(CloneNotSupportedExceptione){//thisshouldn'thappen,sinceweareCloneablethrownewInternalError(e);}}4

执行ListItr的构造方法时调用了一次node(int)方法，返回第一个节点。在此之后，迭代器就执行hasNext()判断有没有下一个，执行next()方法下一个节点。

由此，可以得出这样的结论：遍历LinkedList的时候，千万不要使用for循环，要使用迭代器。

也就是说，for循环遍历的时候，ArrayList花费的时间远小于LinkedList；迭代器遍历的时候，两者性能差不多。