01、List 简介
“List 的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。
以下是 List 集合简易架构图
由图中的继承关系，可以知道，ArrayList、LinkedList、Vector、Stack 都是List 的四个实现类。
- AbstractCollection 是一个抽象类，它唯一实现 Collection 接口的类。AbstractCollection 主要实现了 toArray()、toArray(T[] a)、remove() 等方法。
- AbstractList 也是一个抽象类，它继承于 AbstractCollection。AbstractList 实现 List 接口中除 size()、get(int location) 之外的函数，比如特定迭代器 ListIterator。
- AbstractSequentialList 是一个抽象类，它继承于 AbstractList。AbstractSequentialList 实现了“链表中，根据 index 索引值操作链表的全部函数”。
- ArrayList 是一个动态数组，它由数组实现。随机访问效率高，随机插入、随机删除效率低。
- LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 随机访问效率低，但随机插入、随机删除效率高。
- Vector 也是一个动态数组，和 ArrayList 一样，也是由数组实现。但是ArrayList 是非线程安全的，而 Vector 是线程安全的。
- Stack 是栈，它继承于 Vector。它的特性是：先进后出(FILO, First In Last Out)。
下面对各个实现类进行方法剖析！
02、ArrayList
“ArrayList 实现了 List 接口，也是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入 null 元素，底层通过数组实现。除该类未实现同步外，其余跟 Vector 大致相同。
在 Java1.5 之后，集合还提供了泛型，泛型只是编译器提供的语法糖，方便编程，对程序不会有实质的影响。因为所有的类都默认继承至 Object，所以这里的数组是一个 Object 数组，以便能够容纳任何类型的对象。
2.1、get 方法
get() 方法同样很简单，先判断传入的下标是否越界，再获取指定元素。
public E get(int index) { rangeCheck(index); return elementData(index); } /** * 检查传入的index是否越界 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
2.2、set 方法
set() 方法也非常简单，直接对数组的指定位置赋值即可。
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
2.3、add 方法
ArrayList 添加元素有两个方法，一个是 add(E e)，另一个是 add(int index, E e)。这两个方法都是向容器中添加新元素，可能会出现容量（capacity）不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过 grow() 方法完成的。
grow方法实现
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的1.5倍 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
添加元素还有另外一个 addAll() 方法，addAll() 方法能够一次添加多个元素，根据位置不同也有两个方法，一个是在末尾添加的 addAll(Collection<? extends E> c)方法，一个是从指定位置开始插入的 addAll(int index, Collection<? extends E> c)方法。
不同点：addAll() 的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关，时间复杂度是线性增长！
