列表

List, ArrayList, LinkedList, CopyOnWriteArrayList, Vector

简述

1. 列表划分为线程安全和线程非安全两类

线程安全： Vector, CopyOnWriteArrayList, Collections.synchronizedList()

线程非安全：ArrayList, LinkedList

2. 底层存储

数组： ArrayList Vecotr CopyOnWriteArrayList

双向链表：LinkedList

通过三个添加元素的过程图，来看数据结构

ArrayList,Vector ： 底层存储为数组

LinkedList : 底层存储为双向链表

CopyArrayList：底层存储为数组

3. 使用场景和说明

ArrayList

• 底层为数组，适合随机访问
• 删除不会引起数组容量变小
• 动态插入可能涉及到数组长度重新分配
• 为避免频繁的数组扩容，可设置一个合适的初始容量
• 不适用于频繁的在数组中间进行插入删除的场景

LinkedList

• 底层为双向链表，适合频繁删除新增的场景
• 随机访问不友好，需要遍历

Vector

• 线程安全
• 所有的方法都加锁，导致性能较差

CopyOnWriteArrayList

• 线程安全
• 读方法不加锁；修改方法加锁，一次只能一个写线程访问
• 修改时，会拷贝一份内容出来，对拷贝的结果进行操作，最后覆盖之前的内容
• 遍历和读取都是基于访问时刻列表中的数组进行的；在执行过程中，链表发生修改不会影响遍历和读取的结果（即此时访问的依然是原数组内容）

4. 特性

• List 是有序的
• ArrayList 默认容量为10；LinkedList, CopyOnWriteArrayList默认容量为0
• new ArrayList<>() 内部的数组实际上引用的是一个空数组
• ArrayList 扩容规则
  • 增加原来空间大小的一半
  • 如果依然塞不下，则扩充到正好填充满的情况
• 排序
  • Collections.sort(list, new Comparator(){xxx})
  • 若List中的元素，实现了Comparater接口后，可以直接调用 Collections.sort(list);
• 需要线程安全的场景，使用 CopyOnWriteArrayList 或 Collections.synchronizedList 来替代 Vector