ArrayList是基于数组实现LinkedList是基于链表实现。ArrayList和LinkedList在新增、删除元素时LinkedList的效率要高于 ArrayList而在遍历的时候ArrayList的效率要高于LinkedList。ArrayList是如何实现的1.ArrayList实现类ArrayList实现了List接口继承了AbstractList抽象类底层是数组实现的并且实现了自增扩容数组大小。ArrayList还实现了Cloneable接口和Serializable接口所以他可以实现克隆和序列化。ArrayList还实现了RandomAccess接口。你可能对这个接口比较陌生不知道具体的用处。通过代码我们可以发现这个接口其实是一个空接口什么也没有实现那ArrayList为什么要去实现它呢其实RandomAccess接口是一个标志接口他标志着“只要实现该接口的List类都能实现快速随机访问”。public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable2.ArrayList属性ArrayList属性主要由数组长度size、对象数组elementData、初始化容量default_capacity等组成 其中初始化容量默认大小为10。//默认初始化容量 private static final int DEFAULT_CAPACITY 10; //对象数组 transient Object[] elementData; //数组长度 private int size;从ArrayList属性来看它没有被任何的多线程关键字修饰但elementData被关键字transient修饰了。transient关键字修饰该字段则表示该属性不会被序列化但ArrayList其实是实现了序列化接口这到底是怎么回事呢这还得从“ArrayList是基于数组实现“开始说起由于ArrayList的数组是基于动态扩增的所以并不是所有被分配的内存空间都存储了数据。如果采用外部序列化法实现数组的序列化会序列化整个数组。ArrayList为了避免这些没有存储数据的内存空间被序列化内部提供了两个私有方法writeObject以及readObject来自我完成序列化与反序列化从而在序列化与反序列化数组时节省了空间和时间。因此使用transient修饰数组是防止对象数组被其他外部方法序列化。3.ArrayList构造函数我们在初始化ArrayList时可以通过第一个构造函数合理指定数组初始大小这样有助于减少数组的扩容次数从而提高系统性能。4.ArrayList新增元素ArrayList新增元素的方法有两种一种是直接将元素加到数组的末尾另外一种是添加元素到任意位置。两个方法的相同之处是在添加元素之前都会先确认容量大小如果容量够大就不用进行扩容如果容量不够大就会按照原来数组的1.5倍大小进行扩容在扩容之后需要将数组复制到新分配的内存地址。我们在使用ArrayList进行新增、删除时经常被提醒“使用ArrayList做新增删除操作会影响效率”。那是不是ArrayList在大量新增元素的场景下效率就一定会变慢呢如果我们在初始化时就比较清楚存储数据的大小就可以在ArrayList初始化时指定数组容量大小并且在添加元素时只在数组末尾添加元素那么ArrayList在大量新增元素的场景下性能并不会变差反而比其他List集合的性能要好。5.ArrayList删除元素ArrayList的删除方法和添加任意位置元素的方法是有些相同的。ArrayList在每一次有效的删除元素操作之后都要进行数组的重组并且删除的元素位置越靠前数组重组的开销就越大。6.ArrayList遍历元素由于ArrayList是基于数组实现的所以在获取元素的时候是非常快捷的。LinkedList是如何实现的LinkedList是基于双向链表数据结构实现的LinkedList定义了一个Node结构Node结构中包含了3个部分元素内容item、前指针prev以及后指针next。在JDK1.7之后LinkedList做了很大的改动对链表进行了优化。链表的Entry结构换成了Node内部组成基本没有改变但LinkedList里面的header属性去掉了新增了一个Node结构的first属性和一个Node结构的last属性。这样做有以下几点好处first/last属性能更清晰地表达链表的链头和链尾概念first/last方式可以在初始化LinkedList的时候节省new一个Entryfirst/last方式最重要的性能优化是链头和链尾的插入删除操作更加快捷了。1.LinkedList实现类LinkedList类实现了List接口、Deque接口同时继承了AbstractSequentialList抽象类LinkedList既实现了List类型又有Queue类型的特点LinkedList也实现了Cloneable和Serializable接口同ArrayList一样可以实现克隆和序列化。由于LinkedList存储数据的内存地址是不连续的而是通过指针来定位不连续地址因此LinkedList不支持随机快速访问LinkedList也就不能实现RandomAccess接口。public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable2.LinkedList属性我们前面讲到了LinkedList的两个重要属性first/last属性其实还有一个size属性。我们可以看到这三个属性都被transient修饰了原因很简单我们在序列化的时候不会只对头尾进行序列化所以LinkedList也是自行实现readObject和writeObject进行序列化与反序列化。3.LinkedList新增元素LinkedList添加元素的实现很简洁但添加的方式却有很多种。默认的add (Ee)方法是将添加的元素加到队尾首先是将last元素置换到临时变量中生成一个新的Node节点对象然后将last引用指向新节点对象之前的last对象的前指针指向新节点对象。LinkedList也有添加元素到任意位置的方法如果我们是将元素添加到任意两个元素的中间位置添加元素操作只会改变前后元素的前后指针指针将会指向添加的新元素所以相比ArrayList的添加操作来说LinkedList的性能优势明显。4.LinkedList删除元素在LinkedList删除元素的操作中我们首先要通过循环找到要删除的元素如果要删除的位置处于List的前半段就从前往后找若其位置处于后半段就从后往前找。这样做的话无论要删除较为靠前或较为靠后的元素都是非常高效的但如果List拥有大量元素移除的元素又在List的中间段那效率相对来说会很低。5.LinkedList遍历元素LinkedList的获取元素操作实现跟LinkedList的删除元素操作基本类似通过分前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的特别是在for循环遍历的情况下每一次循环都会去遍历半个List。