ArrayList 与 LinkedList的性能区别

Java集合类

Set:无序、不可重复;List有序、重复的集合;Queue代表队列集合实现;Map代表具有映射关系的集合。

Java集合与数组的区别

Java 集合与数组的区别:

• 数组的长度是不可变的,不能动态添加数据;集合可以保存不确定数量的数组，同时也可以保存具有映射关系的数据。
• 同一个数组的元素即基本类型的值,也可以是对象;集合只能存储同一类型的对象。

Java集合介绍

Set的元素是不可重复，不能存在相同的对象，可以存放不能的对象，具有相同的值。
List中可以存储相同的对象，按照顺序存储。
Queue用于模拟队列，不能随机访问。
Map的key是一个set集合,不能重复(keySet());Map的value是一个list集合,可以重复,使用list存储(values)。

ArrayList

List是一个接口,它继承于Collection接口,代表有序的队列。
AbstractList是一个抽象类,它继承于AbstractCollection。
AbstractSequentialList是一个抽象类,实现了链表中,根据index索引值操作链表的全部方法。
ArrayList、LinkedList、Vector和Stack是List的四个实现类。
Vector是基于数组实现的,是矢量队列,和ArrayList一样,也是一个动态数组,有数组实现。ArrayList是非线程安全的,Vector是线程安全的。
Stack是基于数组实现的,具有Vector先进后出特性。
ArrayList是基于数组实现的List类,内部封装一个动态的、允许在分配的数组，数组可以动态增长。
ArrayList是线程不安全,可以通过Collections.synchronizedList(List l)返回一个线程安全的ArrayList集合。
ArrayList实现了RandomAccess接口,因此具有随机访问功能,通过数组的下标进行快速访问;实现Cloneable接口,能被克隆。
ArrayList默认的大小为10，可以动态扩展，每次扩展为1.5倍，Vector是扩展为两倍。
ArrayList的add和remove方法使用到System.arrayCopy()方法。ArrayList允许存在null。

LinkedList

LinkedList是双链表结构，实现了List和Queue接口，允许元素为null。
LinkedList是非线程安全的。可以通过Collections.synchronizedList(new LinkedList(...))创建线程安全的List。
LinkedList实现了Closeable接口,能被克隆。

header是双向链头的表头，表头的节点对象是个Node类实例(在JDK7之前是Entry)

ArrayList 与 LinkedList的性能区别

结构差别

List	存储结构	特点	循环时间复杂度	get(i)时间复杂度	总时间复杂度	实现
ArrayList	数组结构	可以根据下标直接取值	O(n)	O(1)	O(n)	基于数组实现,可动态扩容数组的容量
LinkedList	链表结构	如果需要寻找某一个下标的数值必须从头遍历	O(n)	O(n)	O(n^2)	基于双向链表的实现,可以做堆栈、队列使用

ArrayList在随机访问set和get比LinkedList的效率更高,因为LinkedList要通过遍历查询遍历移动指针,而ArrayList只需通过index在数组取出即可。
在末尾添加元素，ArrayList比LinkedList更高效。在首位添加元素，LinkedList比ArrayList高效(ArrayList使用System.arrayCopy()移动元素)。

LinkedList不支持高效的随机元素访问。

类别	ArrayList	Vector	LinkedList
优点	适合查找	适合查找	不适合查找
继承类	AbstractList	AbstractList	AbstractSequentialList
实现接口	List,RandomAccess,Cloneable,Serializable	List,RandomAccess,Cloneable,Serializable	List,Deque,Cloneable,Serializable
线程安全	否	是	否
数组增量	50%	100%
数据结构	数组	数组	双向链表
适用场景	适用于需要频繁查找元素的场景	适用于需要频繁查找元素的场景	适用于需要频繁插入删除元素的场景

LinkedList双向列表的实现也比较简单，通过计数索引值实现，从链表长度的1/2开始查找，下标大了就从表头开始找，小了就从表尾开始找。

ArrayList创建底层数组时,JDK7为饿汉式，JDK8是懒汉式。

ArrayList用for循环遍历比iterator迭代器遍历快，LinkedList用iterator迭代器遍历比for循环遍历快，
因为ArrayList继承自RandomAccess。

性能测试

在遍历ArrayList或者LinkedList，需要使用Iterator或者foreach。

# iterator例子
public void iteratorList(List<Integer> lists){
    Iterator<Integer> it = lists.iterator();
    while (it.hasNext()){
        Integer integer = it.next();
        // TODO 处理数据
    }
}

# foreach 例子
public void foreachList(List<Integer> lists){
    for (Integer i : lists) {
        // TODO 处理数据
    }
}

list在遍历删除元素时，需要使用iterator进行遍历删除。对CopyOnWriteArrayList中元素进行遍历删除，需要使用for循环。

参考文献

ArrayList与LinkedList遍历性能比较
Java集合框架（一）
Java集合框架之ArrayList、LinkedList的区别（四）
源码浅析ArrayList、LinkedList和Vector的区别
美团试题：ArrayList和linkedlist有什么区别，如何遍历，使用for循环遍历linkedlist为什么效率低，linkedlist能使用索引访问么，使用迭代器呢
腾讯面试笔记：volatile关键字与synchronized关键字在内存的区别