List

1.概述

List 是一个有序序列，除了继承了 Collection 接口的方法之外，还有下面的功能拓展：

位置访问(positional access)，基于索引来操作元素，包含get、set、add、addAll 和 remove。
搜索，在 List 中搜索指定的元素，放回元素的索引，indexOf、lastIndexOf。
迭代，利用 List 顺序的特点，对 Iterator 的语义进行了拓展，比如 ListIterator。
范围视图(range-view)，用于执行范围操作，sublist

2.功能拓展

位置访问

基本的位置访问方法是get、set、add、remove。（set 和 remove 会返回元素以前的值）。

典型的例子是 Conllections 中的 shuffle 函数实现：

搜索

迭代

List 的 listIterator 方法返回了一个针对于 List 的迭代器 ListIterator，可以进行双向迭代。ListIterator 的定义如下：

ListIterator 的 cursor 并不指向元素，而是指向元素之间或 List 两端，所以，对于一个长度为 n 的 List，cursor 会有 n + 1 个位置。

对于 ListIterator 的方法，hasNext、hasPrevious 分别返回是否存在下一个、上一个元素。next、previous 分别返回下一个、上一个元素，并移动迭代位置。nextIndex、previousInde 分别返回下一个、上一个元素的索引。

remove 方法，将上次调用 next 、previous 函数返回的 element 给修改为新的元素。每次调用 next 或 previous 只能进行一次此调用。在此之中不能调用 add 方法，否则会抛出异常。

set 方法，将上次调用 next 、previous 函数返回的 element 给修改为新的元素。在此之中不能调用 remove、add 方法，否则会抛出异常。

add 方法，添加一个新元素到 next 与 previous 返回元素之间（如果有的话），cursor 位于新元素之后。

AbstractList 接口中有一个成员变量为 modCount，它记录了 List 被修改的次数，用于子类某些实现，要求对于迭代器使用过程中，根据此值是否改变来确认迭代器是否快速失效，而不是去发现是否存在其它线程修改原 List。

范围视图

List 的 subList 返回 [fromIndex, toIndex) 的范围视图（fromIndex 与 toIndex 相等时返回空列表）。

需要注意到的是：

subList 的非结构化改变会影响原 list，反之亦然。
原 list 有除 subList 以外的任何方式在结构上进行了修改，那么 subList 的行为会变得未定义。

所以，一般将 subList 作为一个 transient object 来使用，而不是长期持有。

3.实现

Java 提供了两种通用的实现：ArrayList 和 LinkedList。在绝大多数情况下，都应该选择 ArrayList，只有在频繁的在List中插入和删除元素时，才考虑使用 LinkedList。

其它实现这里先不做叙述。

ArrayList

ArrayList 是一个基于能动态改变容量的数组实现的 List，类似于 C 中动态申请内存。

实现原理

首先，我们查看 ArrayList 的成员变量，主要的如下：

其中，Array 中的元素其实是被存储到 elementData 数组中，并对元素做了类型擦涂，为 Object，所以 ArrayList 中可以存储不同类型的元素。size 的值为 elementData 中的元素数量（并非大小）。

elementData 会有 3 种值：

EMPTY_ELEMENTDATA：表示，当明确 ArrayList 列表的大小为 0 时。此时所有的 ArrayList 实例共享 EMPTY_ELEMENTDATA。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：表示，未明确指出 ArrayList 列表大小，采用的默认容器。注意，ArrayList 使用 Lazy Initialization 的方式申请内存，初始化时 elementData 为空，只有当插入第一个元素时，才会创建默认大小的底层数组。
new Object[length]：指明了列表长度时。

ArrayList 需要确保列表大小，以保证有足够的空间来存储元素。这里就使用了扩容的机制，当需要扩容时，会开启新大小的空间并将原列表复制进去。有关扩容的方法如下：

其中，ensureCapacity 是提供给程序员使用的，ensureCapacityInternal 是当我调用 ArrayList中的其它方法时，如 add，程序调用的函数。这两个会去调用 ensureExplicitCapacity 方法进行扩容。扩容执行函数 grow，策略为变为 1.5 倍。