List是一个有序的队列，每一个元素都有它的索引。第一个元素的索引值是0。List的实现类有LinkedList, ArrayList, Vector, Stack。
List抽象数据类型:
ADT
List
Data
线性表的元素集合为{a1,a2,a3,a4....an},数据类型都是DataType.线性表的元素可以重复，并且可以插入null。
Operations（仅定义逻辑方法，与JDK方法不保持一致）
InitList(); 初始化操作，创建一个空线性表。
ListEmpty(); 判断线性表是否为空，返回布尔值。
AddElement(DataType d,I i); 在线性表的位置i插入元素d。
GetElement(I i); 获取线性表在位置i的元素。
LocateElement(DataType d); 获取元素d在线性表的位置。
RemoveElement(DataType d);/RemoveElement(I i); 移除元素d(在位置i的元素)。
ClearList(); 清空线性表。
ListLength(); 线性表的大小。List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
方法剖析
- add (E e) 向列表内添加指定元素
- add(int index.E e) 向集合指定位置添加元素
- addAll(Collection<？ extends E> c) addAll(int index, Collection<？ extends E> c) 向集合内(指定位置 index)添加另一集合的全部元素
- get(int index)获取指定位置的元素
- clear() 清空集合，可用于多次使用单个集合对象，节省资源
- contains(Object o) 判断是否还有某个对象
- containsAll(Collection<？> c) 判断是否含有集合c的所有元素
- parallelStream() java8新特性，使用fork/join框架自动并行处理
- remove(Object o) 移除集合中的一个元素
- removeAll(Collection<？> c) 移除集合含有的集合c中的所有元素
- removeIf(Predicate<？ super E> filter) 底层迭代调用Predicate的test方法。Predicate函数式接口主要用提供test()方法，该方法返回一个布尔变量
- spliterator() 并行迭代器
- stream() 返回集合的流资源，用于函数式运算
- toArray() 转换成数组
- toArray(T[] a) 将集合转换成对应对象类型的数组
- sort(Comparator<？ super E> c) 使用函数式编程对列表进行排序,排序通过
Arrays.sort()实现 - subList(int fromIndex, int toIndex) 获取子列表
- retainAll(Collection<？> c) 移除除c元素的所有其他元素
- replaceAll(UnaryOperator
List接口为Collection子接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack
ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作(自动扩容机制）。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。
size、isEmpty、get、set、iterator 和 listIterator 操作的算法复杂度。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。
ArrayList擅长于随机访问。同时ArrayList是非同步的。
如果多线程访问ArrayList，可以创建一个线程安全的ArrayList:
List list = Collections.synchronizedList(new ArrayList(...));
ArrayList抽象数据类型：
ADT ArrayList
Data 数据集合为{a1,a2,a3....,an},元素的存储顺寻和放进去的顺序保持一致，底层数据放在一个Object[]数组中,
具有一个容量CAPACITY，当添加元素时，会先检查容量，如果容量不足，执行自动扩容操作。
Operatons（仅定义逻辑方法，与JDK方法不保持一致）
InitList(); 初始化操作，创建一个空线性表。
InitList(n); 初始化操作，创建一个容量为n的数组。
InitList(Collection c);初始化操作，使用Collection的元素创建一个新的数组表，两者的DataType必须一致。
ListEmpty(); 判断线性表是否为空，返回布尔值。
AddElement(DataType d,I i); 在线性表的位置i插入元素d。
GetElement(I i); 获取线性表在位置i的元素。
LocateElement(DataType d); 获取元素d在线性表的位置。
RemoveElement(DataType d);/RemoveElement(I i); 移除元素d(在位置i的元素)。
SetElement(DataType d,I i); 将位置i的元素设置为d;
ClearList(); 清空线性表。
ListLength(); 线性表的大小。方法剖析
add (E e) 向集合内添加指定元素，ArrayList具有自动扩容机制，当添加元素时，会自动扩展ArrayList内部存储数据的elementData数组大小,
最大存储容量为int的存储范围(<= 2147483647),并将新元素放于数组的尾部(有序存储)
add(int index, E element) 底层实现使用了System.arraycopy,添加新元素到数组列表，默认添加到数组的最后
addAll(Collection<？ extends E> c) addAll(int index, Collection<？extends E> c) 向集合内添加另一集合的全部元素，同样使用自动扩容机制.由于底层实现使用了System.arraycopy,基于浅复制（复制的是对象的引用，改变任何一个对象都会影响另一个），所以是线程不安全的.
get(int index)获取指定位置的元素
clear() 循环设置底层存储数组elementData[]为null，最后设置ArryList数组size为0.会设置++modCount，用于保证迭代器线程安全.
contains(Object o) 判断是否含有某个对象，底层实现为调用indexOf(Object var1),如果对应的索引值大于等于0，则含有该对象
containsAll(Collection<？> c) 判断是否含有集合c的所有元素，底层实现为循环调用contains(Object o).由ArrayList的父类AbstractList的父类AbstractCollection实现，ArrayList直接调用父类方法.
parallelStream() 使用Fork/Join框架并行执行任务,涉及到线程池和工作窃取算法
remove(int index) 底层使用System.arraycopy，将index之后的子数组全部前移一位
remove(Object o) 遍历底层数组，找到对应的元素后调用remove(int index)移除元素
removeAll(Collection<？> c)移除集合含有的集合c中的所有元素，底层实现为使用contains(Object o)遍历，移除两个集合的交集。算法复杂度为O(m*n),当数据量较大时，会影响性能。优化可参考：Java中ArrayList的removeAll方法详解
removeIf(Predicate<？super E> filter) 底层迭代调用Predicate的test方法。Predicate函数式接口主要用提供test()方法，该方法返回一个布尔变量。Collection接口已经实现，直接调用。
spliterator() 并行迭代器
stream() 返回集合的流资源，用于函数式运算
toArray() 转换成数组
toArray(Collection<？extends E> c) 将集合转换成Object对象类型的数组
subList(int fromIndex, int toIndex) 获取子列表,由父类AbstractSequentialList实现
同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。
由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
LinkedList抽象数据类型
ADT LinkedList
Data 线性链表的数据对象集合为{a1,a2,...an},每个元素的类型均为DataType。
除了第一个元素外，每一个元素有且仅有一个直接前驱元素，除最后一个元素外，每个元素有且仅有一个直接后继元素。
Operations
initList()初始化操作
listEmpty()判断线性表是否为空
clearList()清空线性表
contains(DataType d)是否包含某个元素
getElement(I i)将第i个位置的值返回给e
locateElement(DataType e)在线性表中查找与e相同的值的位置
insert(DataTypy e)插入元素到线性表，默认插入到列表的最后位置
listInsert(Ii,DataType e) 插入操作,在线性表的第i个位置插入新元素
delete(DataType e) 删除操作
iteratorList()遍历链表方法剖析
add (E e) 向集合内添加指定元素，默认将新元素添加到链表的末端
add(int index, E element) 将元素插入到链表对应的位置，改变其前驱和后驱元素，将新元素加入
addAll(Collection<？extends E> c) addAll(int index, Collection<？extends E> c) 向集合内添加另一集合的全部元素，同样使用自动扩容机制.由于底层实现使用了System.arraycopy,基于浅复制（复制的是对象的引用，改变任何一个对象都会影响另一个），所以是线程不安全的.
addFirst(E e) 将元素添加到链表的起始位置
addLast(E e) 将元素添加到链表的末尾位置
get(int index)获取指定位置的元素，底层实现为遍历链表，时间复杂度为O(n)，远大于ArrayList的O(1)
linkFirst(E e) 将新元素添加到链表的首端
linkLast(E e) 将新元素添加到链表的末端
linkBefore(E e, Node
Vector
与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。但是Vector由于使用了synchronized标识所有的方法，所以性能上没有ArrayList高。
Stack
抽象元素类型
ADT Stack
Data 栈的数据集合为{a1,a2,a3....an},每个元素的类型均为DataType。
栈具有后进先出的特性last-in-first-out (LIFO),后进的元素先出栈。
Operations
InitStack(); 初始化一个空栈
ClearStack(); 清空栈
StackEmpty(); 判断当前栈是否为空
push(); 将元素压入栈
pop(); 将栈顶元素出栈Stack继承自Vector，实现一个后进先出的堆栈，底层是一个数组。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
[1]: 搞懂 Java ArrayList 源码
[2]: java集合框架综述