前言面试的时候经常被问到几个问题：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循环遍历。
