ArrayList和LinkedList有什么区别？是面试官很喜欢问的问题。 可能大部分朋友和我一样可以回复“ArrayList是基于数组实现的，LinkedList是基于双向链表实现的。” “关于这一点，我在以前的文章中也提到过。 但说实话，这样苍白的回答并不能让面试官满意，他想知道更多。 如果小伙伴们继续做如下回复:“ArrayList在添加和删除新元素时效率不如LinkedList，因为涉及数组复制，但在遍历时效率比LinkedList高。” “面试官会满意吗？我只能说，如果面试官是善意的，可能会让我们回答下一个问题；不然他会让我们回家等通知，可能就没消息了。 为什么会这样？为什么？答案错了吗？脾气暴躁的小伙伴，请喝点奶茶冷静一下。 你冷静下来后，请跟我来。让我们携手研究ArrayList和LinkedList的数据结构、实现原理和源代码，谜底或许会揭晓。 01.ArrayList是如何实现的？ArrayList实现了List接口，继承了AbstractList通用类，底层基于array，实现了动态扩展。 公共类ArrayList & ltE & gt扩展AbstractList & ltE & gt实现列表& ltE & gt，RandomAccess，Cloneable，Java . io . serializable { private static final int DEFAULT _ CAPACITY = 10；瞬态对象[]element data；私有int大小；}ArrayList还实现了RandomAccess接口，这是一个有标记的接口:公共接口RandomAccess {}内部为空，标记“实现这个接口的类支持快速(通常是固定时间)随机访问” 快速随机存取是什么意思？也就是说，内存地址可以通过下标(index)直接访问，不需要遍历。 public E get(int index){ objects . check index(index，size)；返回element data(index)；} E element data(int index){ return(E)element data[index]；}ArrayList还实现了Cloneable接口，表明ArrayList支持复制。 ArrayList确实重写了Object类的clone()方法。 public Object clone(){ try { ArrayList & lt；？& gtv =(ArrayList & lt；？& gt)super . clone()；v . element data = arrays . copy of(element data，size)；v . mod count = 0；回归v；} catch(CloneNotSupportedException e){//这不应该发生，因为我们是Cloneable throw new internal error(e)；}}ArrayList还实现了Serializable接口，这也是一个有标记的接口:公共接口Serializable {}内部也是空的，标记“实现这个接口的类支持序列化” 序列化是什么意思？Java的序列化是指将一个对象转换成一个字节序列，这个字节序列包含了对象的字段和方法。 序列化后的对象可以写入数据库、文件或网络传输。 明眼人的朋友可能会注意到，ArrayList中的关键字段elementData是用transient关键字修饰的，用来防止被它修饰的字段被序列化。 这不是前后矛盾吗？既然一个类实现了可序列化的接口，那它肯定是想序列化的吧？那为什么保存关键数据的elementData不想序列化呢？这得从“ArrayList是基于数组实现的”说起 众所周知，数组是定长的，也就是说数组一旦公布，其长度(容量)是固定的，不能像有些东西那样自由伸缩。 这个很麻烦。一旦数组满了，就不能再添加新元素了。 ArrayList不想像数组一样活着，它想灵活，所以实现了动态扩展。 一旦添加元素，发现容量已满(s == elementData.length)，按照原数组的1.5倍(旧容量>:& gt1)产能扩张 容量扩展后，原始数组被复制到新分配的内存地址Arrays.copyof(元素数据，新容量)。 private void add(E，Object[] elementData，int s){ if(s = = element data . length)element data = grow()；element data[s]= e；大小= s+1；}私有对象[]grow(){ return grow(size+1)；}私有对象[]grow(int min capacity){ int old capacity = element data . length；if(old capacity & gt；0 || elementData！= default capacity _ EMPTY _ ELEMENTDATA){ int new capacity = arrays support . new length(old capacity，minCapacity - oldCapacity，/* minimum growth */old capacity & gt；& gt1 /*优选成长*/)；return element data = arrays . copy of(element data，new capacity)；} else { return element data = new Object[math . max(DEFAULT _ CAPACITY，min CAPACITY)]；}}动态扩容是什么意思？大家想一想。 好吧，让我告诉你答案。我等不及了。 这意味着数组的实际大小可能永远不会填满，并且总会有多余的内存空间。 例如，默认数组大小为10。当添加第11个元素时，数组的长度扩展了1.5倍，也就是15，也就是说还有4个内存空间闲置，对吗？序列化时，如果整个数组都序列化，会多序列化4个内存空间吗？ 当存储的元素数量非常非常大的时候，闲置空间会非常非常大，序列化会耗费大量时间。 所以ArrayList做了一个愉快而聪明的决定，内部提供了两个私有方法writeObject和readObject来完成序列化和反序列化。 private void writeObject(Java . io . object output stream s)抛出java.io.IOException { //写出元素计数，任何隐藏的东西int expectedModCount = modCounts . defaultwriteobject()；//写出size作为与clone() s.writeInt(size)行为兼容的容量；//按照正确的顺序写出所有元素。for(int I = 0；我& lt尺寸；i++){ s . writeobject(element data[I])；} if (modCount！= expectedModCount){ throw new ConcurrentModificationException()；}}从writeObject方法的源代码可以看出，它使用ArrayList的实际大小而不是数组的长度(elementData.length)来序列化元素作为上限。 这里应该有掌声！不是对我，而是对Java源代码的作者，他们真的很神奇。可以用两个词来形容他们——敬业和优秀。 02.LinkedList是如何实现的？LinkedList是从AbstractSequentialList继承的双向链表，因此它也可以作为堆栈、队列或队列来操作。 public class LinkedList & ltE & gt扩展AbstractSequentialList & ltE & gt实现列表& ltE & gt，Deque & ltE & gt，Cloneable，Java . io . serializable { transient int size = 0；瞬时节点& ltE & gt第一；瞬时节点& ltE & gt最后；}LinkedList内部定义了一个Node节点，由三部分组成:元素内容项、前引用prev和后引用next。 代码如下:私有静态类节点< E & gt{ E项；LinkedList。节点& ltE & gt接下来；LinkedList。节点& ltE & gtprev节点(LinkedList。节点& ltE & gtprev，E元素，LinkedList。节点& ltE & gtnext){ this . item = element；this.next = nextthis.prev = prev}}LinkedList还实现了Cloneable接口，表示LinkedList支持复制。 LinkedList还实现Serializable接口，这表明LinkedList支持序列化。 目光敏锐的朋友可能再次注意到，LinkedList中的关键字段size、first和last是用瞬态关键字修饰的。这不是又矛盾了吗？到底要不要连载？答案是LinkedList想用自己的方式序列化，看看自己的writeObject()方法:private void writeObject(Java . io . object输出流)抛出java.io.ioexception {//writeout任何隐藏的序列化magic . default writeObject()；//写出size s . Write int(size)；//按照正确的顺序写出所有元素。for (LinkedList。节点& ltE & gtx =第一；x！= nullx = x . next)s . writeobject(x . item)；}找到了吗？LinkedList在序列化过程中只保留元素的内容项，不保留元素的前后引用。 这样节省了很多内存空间吧？有些朋友可能会很困惑。他们只保留元素的内容，不保留前后的引用。反序列化的时候应该怎么做？private void Read object(Java . io . objectinputstream s)抛出java.io.IOException，ClassNotFoundException {//Read in any hidden serialization magic s . default Read object()；//读入size int size = s . readint()；//以正确的顺序读入所有元素。for(int I = 0；我& lt尺寸；i++)link last((E)s . read object())；} void link last(E E){ final linked list。节点& ltE & gtl =最后；最终链接列表。节点& ltE & gtnewNode =新LinkedList。节点& lt& gt(l，e，null)；last = newNodeif(l = = null)first = new node；else l.next = newNodesize++；modcount++；}注意for循环中的linkLast()方法，它可以重新链接链表，从而恢复链表序列化前的顺序。 太棒了，不是吗？与ArrayList相比，LinkedList不实现RandomAccess接口，因为LinkedList存储数据的内存地址是不连续的，所以不支持随机访问。 03.ArrayList和LinkedList添加新元素谁更快？我们已经从多个维度了解了ArrayList和LinkedList的实现原理和各自的特点。 接下来说ArrayList和LinkedList加新元素谁更快？1)ArrayListArrayList添加新元素有两种方式，一种是直接将元素添加到数组末尾，另一种是将元素插入到指定位置。 将源代码添加到数组末尾:public boolean add(e e){ modcount++；add(e，elementData，size)；返回true}private void add(E e，Object[] elementData，int s){ if(s = = element data . length)element data = grow()；element data[s]= e；大小= s+1；}很简单。先判断是否需要扩容，然后直接通过索引将元素添加到末尾。 插入到指定位置的源代码:public void add (int index，ee element){ rangecheckforadd(index)；modcount++；final int s；object[]element data；if((s = size)= =(element data = this . element data)。length)element data = grow()；System.arraycopy(elementData，index，elementData，index + 1，s-index)；element data[index]= element；大小= s+1；}首先检查插入的位置是否在合适的范围内，然后判断是否需要扩展，然后将这个位置之后的元素复制到新添加元素的位置，最后通过索引将元素添加到指定的位置。 这种情况伤害很大，表现会很差。 2)LinkedListLinkedList添加新元素也有两种情况，一种是直接将元素添加到队列末尾，另一种是将元素插入指定位置。 将源代码添加到队列末尾:public boolean add(e e){ link last(e)；返回true} void link last(E E){ final linked list。节点& ltE & gtl =最后；最终链接列表。节点& ltE & gtnewNode =新LinkedList。节点& lt& gt(l，e，null)；last = newNodeif(l = = null)first = new node；else l.next = newNodesize++；modcount++；}先在临时变量L中存储队列末尾的最后一个节点(不是说不推荐用I作为变量名吗？Java的作者明知故犯)，然后生成一个新的Node node并赋给last。如果L为空，说明是第一次增加，所以首先是新节点；否则，将新节点分配给上一个节点的下一个。 插入指定位置的源代码:public void add (int index，ee element){ checkpositionindex(index)；if(index = = size)link last(element)；else linkBefore(element，node(index))；}LinkedList。节点& ltE & gtnode(int index){//assert isElementIndex(index)；if(index & lt；(大小& gt& gt1)) { LinkedList。节点& ltE & gtx =第一；for(int I = 0；我& lt指数；i++)x = x . next；返回x；} else { LinkedList。节点& ltE & gtx =最后；for(int I = size-1；我& gt指数；I-)x = x . prev；返回x；}}void linkBefore(E，E，LinkedList。节点& ltE & gtsucc) { //断言succ！= null最终链接列表。节点& ltE & gtpred = succ.prev最终链接列表。节点& ltE & gtnewNode =新LinkedList。节点& lt& gt(pred，e，succ)；succ.prev = newNodeif(pred = = null)first = new node；else pred.next = newNodesize++；modcount++；}先检查插入的位置是否在合适的范围内，再判断插入的位置是否是队列的末尾。如果是，则将其增加到队列的末尾；否则，执行linkBefore()方法 在执行linkBefore()方法之前，将调用node()方法来查找指定位置的元素，这需要遍历LinkedList。 如果插入位置在前半段，从队头开始往后看；否则，从线的末端向前看。 也就是说，如果插入的位置越靠近LinkedList的中间，遍历的时间就越长。 在指定位置找到元素(succ)后，将启动linkBefore()方法。首先将succ的前一个节点(prev)存储在临时变量pred中，然后生成一个newNode (newNode)，将succ的前一个节点改为newNode。如果pred为null，则插入队列头，因此第一个是新节点；否则，将pred的下一个节点改为newNode。 源代码分析完后，小伙伴们是不是在想:“就像ArrayList一样，在添加新元素的时候，效率不一定比LinkedList低！”当两者的起始长度相同时:如果元素是从集合的头部新加入的，ArrayList要比LinkedList花费更多的时间，因为需要复制头部之后的元素。 public class ArrayList test { public static void addFromHeaderTest(int num){ ArrayList & lt；字符串& gtlist = new ArrayList & lt字符串& gt(num)；int I = 0；long time start = system . current time millis()；while(我& ltNum) {list.add(0，i+"沉默王二")；i++；} long time end = system . current time millis()；System.out.println("ArrayList从集合头部添加新元素所花费的ArrayList "+(time end-time start))；} }/* * * * @作者微信搜索“寂静之王II”，回复关键字PDF */public class链表测试{ public static void addfromheader test(int num){链表< String & gtlist = new LinkedList<。字符串& gt();int I = 0；long time start = system . current time millis()；while(我& ltNum) {list.addFirst(i+《寂静之王II》)；i++；} long time end = system . current time millis()；System.out.println("LinkedList从集合头部添加新元素所用的LinkedList时间"+(time end-time start))；}}num为10000，代码的实测时间如下:ArrayList从集合头开始添加新元素需要595的时间，LinkedList从集合头开始添加新元素需要15的时间，ArrayList比链表花费的时间多得多。 如果从集合中间添加新元素，ArrayList可能比LinkedList花费的时间少，因为需要遍历LinkedList。 public class ArrayList test { public static void addfromidtest(int num){ ArrayList & lt；字符串& gtlist = new ArrayList & lt字符串& gt(num)；int I = 0；long time start = system . current time millis()；while(我& ltnum){ int temp = list . size()；List.add(temp/2+“沉默二”)；i++；} long time end = system . current time millis()；System.out.println("ArrayList从集合中间添加新元素所花费的ArrayList "+(time end-time start))；} } public class linked list test { public static void addfromidtest(int num){ linked list & lt；字符串& gtlist = new LinkedList<。字符串& gt();int I = 0；long time start = system . current time millis()；while(我& ltnum){ int temp = list . size()；List.add(temp/2，i+“沉默王二”)；i++；} long time end = system . current time millis()；System.out.println("LinkedList从集合中间添加新元素所用的LinkedList时间"+(time end-time start))；}}num为10000，代码实测时间如下:ArrayList从集合中间添加新元素所花费的时间为1。LinkedList从集合中间添加新元素所花费的时间是101。数组列表比链表花费的时间少得多。 如果从集合的末尾添加新元素，ArrayList应该比LinkedList花费更少的时间。因为数组是一个连续的内存空间，所以不需要复制数组。链表需要创建新的对象，前后的引用都要重新排列。 public class ArrayList test { public static void addFromTailTest(int num){ ArrayList & lt；字符串& gtlist = new ArrayList & lt字符串& gt(num)；int I = 0；long time start = system . current time millis()；while(我& ltNum) {list.add(i+《寂静之王II》)；i++；} long time end = system . current time millis()；System.out.println("ArrayList从集合末尾添加新元素所花费的ArrayList "+(time end-time start))；} }公共类linked list test { public static void addFromTailTest(int num){ linked list & lt；字符串& gtlist = new LinkedList<。字符串& gt();int I = 0；long time start = system . current time millis()；while(我& ltNum) {list.add(i+《寂静之王II》)；i++；} long time end = system . current time millis()；System.out.println("LinkedList从集合末尾添加新元素所用的LinkedList时间"+(time end-time start))；}}num为10000，代码实测时间如下:ArrayList从集合末尾添加新元素需要时间69LinkedList从集合末尾添加新元素需要时间193ArrayList比LinkedList需要的时间少。 这个结论是不是和预期不太相符？ArrayList在两种情况下比LinkedList好很多(中间加新元素，尾部加新元素)，但只有在头部加新元素时比LinkedList差。因为数组重复， 当然，如果涉及数组扩展，ArrayList的性能就没那么可观了，因为扩展的时候数组还得复制。 04.ArrayList和LinkedList删除元素谁更快？1) ArrayList删除一个元素时，有两种方法。一种是直接删除元素(remove(Object))，需要先遍历数组找到元素对应的索引；一种是通过索引删除元素(remove(int)) public boolean remove(Object o){ final Object[]es = element data；final int size = this.sizeint I = 0；找到了:{ if(o = = null){ for(；我& lt尺寸；i++) if (es[i] == null)找到分隔符；} else { for(；我& lt尺寸；i++) if (o.equals(es[i])) break找到；}返回false} fastRemove(es，I)；返回true} public E remove(int index){ objects . check index(index，size)；最终对象[]es = element data；@ suppress warnings(" unchecked ")E old value =(E)es[index]；fastRemove(es，index)；返回旧值；}但本质上都是一样的，因为最后都调用了fastRemove(Object，int)方法。 private void fast remove(Object[]es，int I){ modcount++；最终int newSizeif ((newSize = size - 1)>i) System.arraycopy(es，i + 1，es，I，newSize-I)；es[size = newSize]= null；}从源代码中可以看到，需要删除的并不是最后一个元素，而是都需要数组重组。 被删除元素的位置越高，成本越高。 2)LinkedListLinkedList删除元素时，常见的方式有四种:remove(int)，在指定位置删除元素public e remove(int index){ checkelemenndex(index)；返回unlink(node(index))；}先检查索引，然后调用Node(int)方法(遍历前后半部，同添加新元素)找到节点Node，再调用unlink(Node)去掉节点的前后引用，升级前一个节点的后引用和后一个节点的前引用:eunlink(Node < E & gt；x) { //断言x！= null最终E元素= x . item；最终节点& ltE & gtnext = x.next最终节点& ltE & gtprev = x.previf(prev = = null){ first = next；} else { prev.next = nextx.prev = null} if(next = = null){ last = prev；} else { next.prev = prevx.next = null} x.item = null尺寸-；modcount++；返回元素；}remove(Object)，直接删除元素public boolean remove(Object o){ if(o = = null){ for(linked list . node < E & gt；x =第一；x！= nullx = x . next){ if(x . item = = null){ unlink(x)；返回true} } } else { for (LinkedList。节点& ltE & gtx =第一；x！= nullx = x . next){ if(o . equals(x . item)){ unlink(x)；返回true} } }返回false}也是前面的后半遍历。找到要删除的元素后，调用unlink(Node) RemoveFirst()，删除第一个节点，public E remove first(){ finallinkedlist . node < E & gt；f =第一；if (f == null)抛出new NoSuchElementException()；返回unlink first(f)；} private E unlink first(linked list。节点& ltE & gtf){//assert f = = first & amp；& ampf！= null最终E元素= f . item；最终链接列表。节点& ltE & gtnext = f.nextf.item = nullf.next = null//help GC first = next；if(next = = null)last = null；else next.prev = null尺寸-；modcount++；返回元素；}不遍历删除第一个节点，只需将第二个节点升级到第一个节点即可。 RemoveLast()，删除最后一个节点。删除最后一个节点类似于删除第一个节点，只要倒数第二个节点升级到最后一个节点。 可以看出，LinkedList在删除前后位置的元素时效率非常高，但如果删除中间位置的元素，效率就比较低。 这里没有更多的代码测试。感兴趣的朋友可以自己尝试一下，结果和新加入的元素一致:ArrayList在删除集合头部的元素时，花费的时间比LinkedList多得多；从集合中间删除元素时，ArrayList比LinkedList花费的时间少得多；从集合末尾删除元素时，ArrayList比LinkedList花费的时间要少一些。 我的本地统计结果如下，朋友们可以参考一下:ArrayList从集合头删除元素所用的时间380LinkedList从集合头删除元素4ArrayList从集合中间删除元素381LinkedList从集合中间删除元素5922ArrayList从集合尾删除元素8l . inked list从集合尾删除元素需要时间，1205，ArrayList和LinkedList。遍历元素谁更快？1)ArrayList遍历ArrayList查找元素时，通常有两种形式:get(int)，根据索引查找元素public e get(int index){ objects . check index(index，size)；返回element data(index)；}因为ArrayList是用数组实现的，所以根据索引查找元素非常快，一步一个脚印。 Of (object)，根据元素找到index public int index of(Object o){返回range (o，0，size)的索引；}int indexOfRange(Object o，int start，int end){ Object[]es = element data；if(o = = null){ for(int I = start；我& lt结束；i++){ if(es[I]= = null){ return I；} } } else { for(int I = start；我& lt结束；i++){ if(o . equals(es[I]){ return I；} } }返回-1；}如果要查找基于元素的索引，需要遍历整个数组，从头到尾查找。 2)LinkedList遍历LinkedList查找一个元素，通常有两种形式:get(int)，在指定位置查找元素public e get(int index){ checkelementedex(index)；返回节点(索引)。项；}既然需要调用node(int)方法，就意味着需要遍历前半部分和后半部分。 Of (object)，找到元素的位置public int index of(Object o){ int index = 0；if (o == null) { for (LinkedList。节点& ltE & gtx =第一；x！= nullx = x.next) { if (x.item == null)返回索引；index++；} } else { for (LinkedList。节点& ltE & gtx =第一；x！= nullx = x.next) { if (o.equals(x.item))返回索引；index++；} } return-1；}需要遍历整个链表，类似于ArrayList的indexOf() 当我们遍历一个集合时，通常有两种方式，一种是使用for循环，另一种是使用迭代器。 如果使用for循环，可想而知在get时LinkedList的性能会很差。由于每个外部for循环，必须执行一次node(int)方法来遍历前半部分和后半部分。 LinkedList。节点& ltE & gtnode(int index){//assert isElementIndex(index)；if(index & lt；(大小& gt& gt1)) { LinkedList。节点& ltE & gtx =第一；for(int I = 0；我& lt指数；i++)x = x . next；返回x；} else { LinkedList。节点& ltE & gtx =最后；for(int I = size-1；我& gt指数；I-)x = x . prev；返回x；}}如果使用迭代器呢？LinkedList & lt字符串& gtlist = new LinkedList<。字符串& gt();for(迭代器& lt字符串& gtit = list . iterator()；it . has next()；){ it . next()；}迭代器只会调用node(int)方法一次。执行list.iterator()时，先调用AbstractSequentialList类的iterator()方法，再调用AbstractList类的listIterator()方法，再调用LinkedList类的listIterator(int)方法，如下图所示。 最后返回LinkedList类的内部私有类ListItr对象:public listiterator < E & gtlist iterator(int index){ checkPositionIndex(index)；返回新LinkedList。ListItr(索引)；}私有类ListItr实现ListIterator & ltE & gt{私人链接列表。节点& ltE & gtlastReturned私人链接列表。节点& ltE & gt接下来；private int nextIndexprivate int expectedModCount = modCount；ListItr(int index){//assert isPositionIndex(index)；next = (index == size)？null:节点(索引)；nextIndex = index} public boolean has next(){ return next index & lt；尺寸；} public E next(){ checkforcomedification()；如果(！hasNext())抛出新的NoSuchElementException()；lastReturned = nextnext = next.nextnext index++；return lastReturned.item}}执行ListItr的构造方法时调用一次node(int)方法，返回第一个节点。 之后迭代器执行hasNext()判断是否有下一个，执行Next()方法的下一个节点。 因此可以得出结论，在遍历LinkedList时，千万不要使用for循环，而要使用迭代器。 也就是说，for循环时，ArrayList比LinkedList花费的时间少得多；；当迭代器遍历时，两者的性能是相似的。 06.花了两天时间总结，终于肝完了！相信看完这篇文章，如果面试官问你ArrayList和LinkedList有什么区别，你一定会很自信的和他聊上半个小时。 另外，我把看过的学习视频按顺序分类了，一共500G。目录如下，还有2020年最新的面试题目。现在我将免费送给你。 链接:https://pan.baidu.com/s/1j2uB7-TF3t5BAzVXBgV7dA密码:cg1q我是沉默的王二，一个沉默但有趣的程序员。谢谢大家的喜欢、收藏和评论。下一部分再见！