ArrayList

ArrayList 基于数组实现，默认大小为 10，实现了 RandomAccess 接口，表示支持快速随机访问。数组容量不够时会进行扩容，拷贝数组，因此创建 ArrayList 时选择合理的数组大小可以减少扩容的次数。

添加元素

添加元素时如果发现容量不够，会进行扩容，默认会扩容为原来的 1.5 倍大小，扩容过程中会把旧数组拷贝到新数组，因此扩容操作会比较损耗性能。

删除元素

删除 index 位置上的元素后，需要把 index 之后的元素拷贝到 index 位置，这个操作的时间复杂度是 O (n)，因此也是比较损耗性能的。

序列化

ArrayList 序列化时不会序列化整个数组，而是只序列化有元素的那部分内容。序列化和反序列化时会反射调用对象的 writeObject 和 readObject 方法。

Fail-Fast

序列化或迭代的过程中，如果 modCount 改变了，会抛出 ConcurrentModificationException 快速失败。

LinkedList

基于双向链表实现，使用 Node 存储节点信息，也可以使用下标访问元素，但是依然需要遍历链表。虽然 LinkedList 内部会根据下标和 size 来决定从头部还是尾部开始遍历，时间复杂度依然为 O (n)。

LinkedList 本质上还是一个 List，它需要基于索引来访问，使用双向链表实现，是空间换时间的思想。根据索引判断目标节点处于链表的前半段还是后半段，决定是从头部开始遍历还是从尾部开始遍历，可以节省一半的时间。

与 ArrayList 的比较

ArrayList 基于数组实现，LinkedList 基于双向链表实现。从增删改查的角度来看，ArrayList 改查的速度比较快，都可以在 O (1) 时间内完成，单纯看增删的话，会觉得 LinkedList 快，但是增删元素的时候需要先找到元素，所以 LinkedList 除了在尾部追加元素时只需 O (1) 的时间，指定位置的增删也需要 O (n) 的时间。
大部分情况下，都建议使用 ArrayList 而不是 LinkedList，因为改查的时间复杂度上 ArrayList 表现更好，其他方面又和 LinkedList 差不多，而且 ArrayList 占用的内存更少。

与 ArrayDeque 的比较

ArrayDeque 是一个可扩容的数组，不可以存 null 值，但是 LinkedList 可以存 null 值。ArrayDeque 利用了循环数组的思想，头尾的增删更高效，内存使用也比 LinkedList 更少。另外，Stack 已经被官方标记为不建议使用，想用 Stack 语义的话可以用 ArrayDeque 实现。

ArrayDeque 循环下标计算技巧

addFirst：(head-1)&(length-1)

addLast：(tail+1)&(length-1)

Vector

Vector 的实现和 ArrayList 基本相同，但是使用了 synchronized 进行同步，因此整体上性能会比 ArrayList 差。

如何扩容？

创建 Vector 时可以传入 capacityIncrement 参数，在扩容时会使容量增加 capacityIncrement，但是如果 capacityIncrement=0，则会扩容为原来的 2 倍大小。调用 Vector 的无参构造函数时，capacityIncrement 默认为 0，所以 Vector 默认情况下会扩容为原来的 2 倍大小。

并发替代方案

如果需要一个同步的 List，可以使用 Collections.synchronizedList () 得到一个同步的 ArrayList，也可以使用 CopyOnWriteArrayList。

SynchronizedList 和 Vector 的区别

SynchronizedList 兼容性更强，可以处理所有的 List 子类。SynchronizedList 的扩容机制跟随原有 List，Vector 则默认扩容为原来的 2 倍大小。Vector 的 Iterator 会自行同步，而 SynchronizedList 遍历时必须手动同步。