List
What's List
相关信息
Java 中链表数据结构的接口，继承 Collection 容器接口，List 又称为集合。
容器是什么
容器是容纳 Java 对象的对象。容器中只存放对象，基本类型需要将其包装成对象类型后才能放到容器里。
Java 容器主要包括 Collection 和 Map 两个根接口。
链表内存模型
链表是一系列的对象，每个对象元素存储下一个元素的内存地址值，添加元素时只需在上一个元素中记录新元素的内存地址值即可（插入效率高），查询元素时则需要以链式结构逐一向下查询（查询效率低）。
因此在创建时申请的计算机内存地址是不连续的。
链表特性
- 元素默认按输入顺序有序排列。
- 元素可重复。
- 初始大小不指定时的默认是 10（JDK1.6），在 JDK1.8 后是 0.
- 添加元素效率高，访问元素效率低。
API
List 接口定义的 API，其具体实现类（ArrayList、Vector、LinkedList）都实现了以下方法：
| api | 作用 |
|---|---|
| size() | 获取长度 |
| isEmpty() | 判断是否长度为0 |
| get() | 获取元素 |
| set() | 放入元素 |
| add() | 放入元素，时间开销跟插入位置有关 |
| addAll() | 放入全部元素，开销跟添加元素的个数成正比 |
| clear() | 清除所有元素 |
| contains() | 判断元素是否存在 |
| remove() | 删除一个元素 |
| toArray() | 转为数组 |
ArrayList
ArrayList 具体实现了 List 接口。
底层数据结构使用数组 Object[] 实现，申请一段连续的内存地址。当数组大小不满足时需要进行扩容，将已经有数组的数据复制到新的存储空间中，可以看作是一个自动扩容的数组。
ArrayList 为追求效率，没有实现同步，多个线程并发访问，需要手动同步。
快速失败
ArrayList 采用了快速失败的机制，通过记录 modCount 参数来实现。面对并发的修改时，迭代器很快就会完全失败，而不是发生任意不确定行为。
特性：
- 查询快，增删慢（中间位置插入或者删除元素时，需要对数组进行复制、移动，代价较高）。
- 按输入顺序有序排列。
- 允许放入
NULL元素，ArrayList 底层是数组，添加 null 并未对数据结构造成影响。
自动扩容
在每次添加元素时，检查添加元素后的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。
数组扩容通过一个公开的方法 ensureCapacity(int minCapacity) 来实现。在实际添加大量元素前，也可以手动使用 ensureCapacity 来增加 ArrayList 实例的容量，以减少递增式再分配的数量。
数组扩容时，需要将老数组中的元素重新拷贝到新数组中，每次容量的增长大约是原容量的 1.5 倍。扩容代价很高，应尽量避免。在构造 ArrayList 实例时，如可预知保存的元素的数量时，就指定其容量，避免数组扩容。
LinkedList
LinkedList 基于具体实现了 List 接口。
基于双向链表实现，申请的计算机内存是不连续的，每个元素中存储上一个元素和下一个元素的内存地址值，因此从任何一个地方插入元素效率都很高，查询元素时也可以从头部或尾部开始查询。
提供了一些对集合头部和尾部的操作，可以快速地在链表中间插入和删除元素，还可以用作栈、队列和双向队列。
特性：
- 增删块，查询慢。
- 按输入顺序有序排列。
- 允许放入
NULL元素，LinkedList 底层为双向链表，node.value = null 没有问题。
| api | 作用 |
|---|---|
| addFirst() | 向队列头部添加元素 |
| addLash() | 向队列尾部添加元素 |
| peek() | 检索第一个元素 |
| poll() | 检索并删除第一个元素 |
| pop() | 删除并返回第一个元素 |
Vector
线程安全的 ArrayList，底层数据结构是数组，查询快，增删慢。