1. 列表划分为线程安全和线程非安全两类
线程安全:Vector,CopyOnWriteArrayList,Collections.synchronizedList()
线程非安全:ArrayList,LinkedList
2. 底层存储
数组:ArrayList, Vecotr, CopyOnWriteArrayList
双向链表:LinkedList
通过三个添加元素的过程图,来看数据结构
ArrayList,Vector: 底层存储为数组
LinkedList: 底层存储为双向链表
CopyArrayList:底层存储为数组
3. 使用场景和说明
ArrayList
-
底层为数组,适合随机访问
-
删除不会引起数组容量变小
-
动态插入可能涉及到数组长度重新分配
-
为避免频繁的数组扩容,可设置一个合适的初始容量
-
不适用于频繁的在数组中间进行插入删除的场景
LinkedList
-
底层为双向链表,适合频繁删除新增的场景
-
随机访问不友好,需要遍历
Vector
-
线程安全
-
所有的方法都加锁,导致性能较差
CopyOnWriteArrayList
-
线程安全
-
读方法不加锁;修改方法加锁,一次只能一个写线程访问
-
修改时,会拷贝一份内容出来,对拷贝的结果进行操作,最后覆盖之前的内容;每次修改都会先上锁,然后进行数组拷贝,所以性能较ArrayList低;读取无锁,所以读的性能比Vector高(没有竞争);默认初始容量为0
-
遍历和读取都是基于访问时刻列表中的数组进行的;在执行过程中,链表发生修改不会影响遍历和读取的结果(即此时访问的依然是原数组内容)
4. 特性
1. List是有序的
2. ArrayList默认容量为10;
3. LinkedList,CopyOnWriteArrayList默认容量为0
4. new ArrayList<>()内部的数组实际上引用的是一个空数组
5. 需要线程安全的场景,使用CopyOnWriteArrayList(并发读性能好)或Collections.synchronizedList(并发写性能好)来替代Vector
6. ArrayList扩容规则
-
增加原来空间大小的一半
-
如果依然塞不下,则扩充到正好填充满的情况
7. 排序
-
Collections.sort(list, new Comparator(){xxx})
-
若List中的元素,实现了Comparable接口后,可以直接调用Collections.sort(list);