前言面试的时候，经常被问几个问题：
ArrayList和LinkedList的区别，我想大多数朋友都能回答：
ArrayList基于数组实现，而LinkedList基于链表实现
随机访问列表时，ArrayList比链接列表更有效率等
使用ArrayList和链接列表的场景是什么？ 被问到时，大部分朋友的回答可能如下。
对于ArrayList和链接的列表，在添加和删除元素时，链接的列表比ArrayList更高效，在遍历时，ArrayList比链接的列表更高效
那个回答正确吗？ 今天研究吧！
首先，让我们简单介绍一下ArrayList和LinkedList的原理实现！
源代码分析ArrayList 实现类
publicclassarraylisteextendsabstractlisteimplementsliste，RandomAccess，Cloneable，java.io.Serializable ArrayList在列表中
ArrayList还实现了Cloneable接口和Serializable接口，因此可以实现克隆和序列化。
ArrayList还实现了random访问接口。 该接口是一个标志接口，表明“实现此接口的List类可以实现快速随机访问”。
基本属性
ArrayList属性主要由数组长度size、对象数组elementData、初始化容量default_capacity等组成，初始化容量的默认大小为10。
//默认初始化容量privatestaticfinalintdefault _ capacity=10； //对象数组transient object [ ] element数据； //数组长度privateintsize； 从ArrayList属性来看，elementData由transient关键字限定，而由transient关键字限定的字段表示属性不序列化。
但是，ArrayList其实是为什么实现序列化接口的呢？
ArrayList数组基于动态放大，因此并不是所有分配的内存空间都包含数据。
使用外部序列化方法序列化数组将序列化整个数组。 ArrayList通过在内部使用两个专用方法writeObject和readObject进行序列化和反序列化，在序列化和反序列化数组的时期节省了空间和时间，以防止这些不包含数据的内存空间序列化
因此，使用transient修饰数组是防止对象数组被其他外部方法序列化。
ArrayList的自定义序列化方法如下：
初始化
初始化方法有三种。 无参数直接初始化，指定大小进行初始化，指定初始数据进行初始化。 源代码如下。
ArrayList添加新元素时，如果超出了已存储元素的大小，则计算元素的大小，然后动态扩展。 数组的扩展将对整个数组进行内存复制。
因此，通过在第一个构造函数中正确指定数组的初始大小，可以在初始化ArrayList时减少数组的扩展次数并提高系统性能。
注意事项：
初始化无ArrayList参数构造函数时，缺省大小为空数组，不是常见的10。 10是第一次添加时扩展的数组值。
新增元素
在ArrayList中添加元素的方法包括直接在数组末尾添加元素，以及在任意位置添加元素。
公共布尔型(ee )电子封装国际) size1； //IncrementsmodCount！ 元素数据[ size ]=e； 返回真； }公共语音添加(索引，Eelement )语言检查器索引； 企业空间国际(size 1； //IncrementsmodCount！ system.arraycopy (元素数据，索引，元素数据，索引1，大小索引)； element data [索引]=element； size； }这两种方法的共同点是在添加元素之前确认允许量
量大小，如果容量够大，就不用进行扩容；如果容量不够大，就会按照原来数组的1.5倍大小进行扩容，在扩容之后需要将数组复制到新分配的内存地址。下面是具体的源码：
这两个方法也有不同之处，添加元素到任意位置，会导致在该位置后的所有元素都需要重新排列，而将元素添加到数组的末尾，在没有发生扩容的前提下，是不会有元素复制排序过程的。
所以ArrayList在大量新增元素的场景下效率不一定就很慢的
如果我们在初始化时就比较清楚存储数据的大小，就可以在ArrayList初始化时指定数组容量大小，并且在添加元素时，只在数组末尾添加元素，那么ArrayList在大量新增元素的场景下，性能并不会变差，反而比其他List集合的性能要好。
删除元素
ArrayList 删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，原理和思路都差不多。
ArrayList在每一次有效的删除元素操作之后，都要进行数组的重组，并且删除的元素位置越靠前，数组重组的开销就越大。
我们选取根据值删除方式来进行源码说明：
遍历元素
由于ArrayList是基于数组实现的，所以在获取元素的时候是非常快捷的。
public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; } LinkedListLinkedList是基于双向链表数据结构实现的。
这个双向链表结构，链表中的每个节点都可以向前或者向后追溯，有几个概念如下：
链表每个节点我们叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置；
first 是双向链表的头节点，它的前一个节点是 null。
last 是双向链表的尾节点，它的后一个节点是 null；
当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
因为是个双向链表，只要机器内存足够强大，是没有大小限制的。
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结构对象连接而成的一个双向链表。
实现类
LinkedList类实现了List接口、Deque接口，同时继承了AbstractSequentialList抽象类，LinkedList既实现了List类型又有Queue类型的特点；LinkedList也实现了Cloneable和Serializable接口，同ArrayList一样，可以实现克隆和序列化。
由于LinkedList存储数据的内存地址是不连续的，而是通过指针来定位不连续地址，因此，LinkedList不支持随机快速访问，LinkedList也就不能实现RandomAccess接口。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable基本属性
transient int size = 0;transient Node first;transient Node last;我们可以看到这三个属性都被transient修饰了，原因很简单，我们在序列化的时候不会只对头尾进行序列化，所以LinkedList也是自行实现readObject和writeObject进行序列化与反序列化。
下面是LinkedList自定义序列化的方法。
节点查询
链表查询某一个节点是比较慢的，需要挨个循环查找才行，我们看看 LinkedList 的源码是如何寻找节点的：
LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。
如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能。
新增元素
LinkedList添加元素的实现很简洁，但添加的方式却有很多种。
默认的add (Ee)方法是将添加的元素加到队尾，首先是将last元素置换到临时变量中，生成一个新的Node节点对象，然后将last引用指向新节点对象，之前的last对象的前指针指向新节点对象。
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/
测试结果：
操作花费时间从集合头部位置添加元素（ArrayList）550从集合头部位置添加元素（LinkedList）34从集合中间位置位置添加元素（ArrayList）32从集合中间位置位置添加元素（LinkedList）58746从集合尾部位置添加元素（ArrayList）29从集合尾部位置添加元素（LinkedList）31
通过这组测试，我们可以知道LinkedList添加元素的效率未必要高于ArrayList。
从集合头部位置添加元素
由于ArrayList是数组实现的，在添加元素到数组头部的时候，需要对头部以后的数据进行复制重排，所以效率很低；
LinkedList是基于链表实现，在添加元素的时候，首先会通过循环查找到添加元素的位置，如果要添加的位置处于List的前半段，就从前往后找；若其位置处于后半段，就从后往前找，因此LinkedList添加元素到头部是非常高效的。
从集合中间位置位置添加元素
ArrayList在添加元素到数组中间时，同样有部分数据需要复制重排，效率也不是很高；
LinkedList将元素添加到中间位置，是添加元素最低效率的，因为靠近中间位置，在添加元素之前的循环查找是遍历元素最多的操作。
从集合尾部位置添加元素
而在添加元素到尾部的操作中，在没有扩容的情况下，ArrayList的效率要高于LinkedList。
这是因为ArrayList在添加元素到尾部的时候，不需要复制重排数据，效率非常高。
LinkedList虽然也不用循环查找元素，但LinkedList中多了new对象以及变换指针指向对象的过程，所以效率要低于ArrayList。
注意：这是排除动态扩容数组容量的情况下进行的测试，如果有动态扩容的情况，ArrayList的效率也会降低。
删除元素操作性能测试
ArrayList和LinkedList删除元素操作测试的结果和添加元素操作测试的结果很接近！
结论：如果需要在List的头部进行大量的插入、删除操作，那么直接选择LinkedList。否则，ArrayList即可。
遍历元素操作性能测试
测试用例源代码：
ArrayList：https://paste.ubuntu.com/p/ZNWc9H2pYm/
LinkedList：https://paste.ubuntu.com/p/xSk4nHDHvN/
测试结果：
操作花费时间for循环（ArrayList）3for循环（LinkedList）17557迭代器循环（ArrayList）4迭代器循环（LinkedList）4
我们可以看到，LinkedList的for循环性能是最差的，而ArrayList的for循环性能是最好的。
这是因为LinkedList基于链表实现的，在使用for循环的时候，每一次for循环都会去遍历半个List，所以严重影响了遍历的效率；ArrayList则是基于数组实现的，并且实现了RandomAccess接口标志，意味着ArrayList可以实现快速随机访问，所以for循环效率非常高。
LinkedList的迭代循环遍历和ArrayList的迭代循环遍历性能相当，也不会太差，所以在遍历LinkedList时，我们要切忌使用for循环遍历。
●【练手项目】基于SpringBoot的ERP系统，自带进销存+财务+生产功能
●分享一套基于SpringBoot和Vue的企业级中后台开源项目，代码很规范！
●能挣钱的，开源 SpringBoot 商城系统，功能超全，超漂亮！
PS：因为公众号平台更改了推送规则，如果不想错过内容，记得读完点一下“在看”，加个“星标”，这样每次新文章推送才会第一时间出现在你的订阅列表里。点“在看”支持我们吧！