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关键字在内存的区别
