Java集合ArrayList和LinkedList区别

Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口。

Java集合大致可以分为Set、List、Queue和Map四种体系，其中Set代表无序、不可重复的集合；List代表有序、重复的集合；而Map则代表具有映射关系的集合；Queue体系集合，代表一种队列集合实现。

jdk1.4以前没有Queue集合，一般用LinkedList 实现队列。

集合框架

基础知识 

数组：

链表： 

数组的优点

1. 随机访问性强
2. 查找速度快

数组的缺点

1. 插入和删除效率低，必须移动数组
2. 可能浪费内存
3. 内存空间要求高，必须有足够的连续内存空间。
4. 数组大小固定，不能动态拓展

链表的优点

1. 插入删除速度快，只需通过指针指向对象地址
2. 内存利用率高，不会浪费内存
3. 大小没有固定，拓展很灵活

链表的缺点

1. 不能随机查找，必须从第一个开始遍历，查找效率低

ArrayList和LinkedList区别

ArrayList和LinkedList的大致区别： 

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 （LinkedList是双向链表，有next也有previous）
2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 
3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 

一．时间复杂度

ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法。 

例子：我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是ArrayList和LinkedList时的查询速度，比较结果ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。 

这是否表明ArrayList总是比LinkedList性能要好呢？这并不一定，在某些情况下LinkedList的表现要优于ArrayList，有些算法在LinkedList中实现时效率更高。比方说，利用Collections.reverse方法对列表进行反转时，其性能就要好些。

例子：要对其进行大量的插入和删除操作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素，ArrayList耗时比LinkList长。当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。

二．空间复杂度 

private static class Entry { Object element; Entry next; Entry previous; } 

LinkedList中有一个私有的内部类Entry，每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素（双向链表）。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。 

ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10。当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。

三．总结 

ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下： 

1. 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
2. 在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3. LinkedList不支持高效的随机元素访问。
4. ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了，这种顺序访问是不是很像队列操作方式，LinkedList适合实现队列。

总结完数组与链表的优缺点后，是否有一种方法把2种数据结构结合使用，HashMap就很好实现这种结合，先计算出hash数组，在hash冲突后使用链表。

在数据结构中数组、链表、B树、哈希数组等这些基础感念，在这些基础上演变出各种形式，需要融会贯通。

参考：

HashMap原理及内部存储结构