ArrayList是集合框架中比较常用的数据结构，继承自 AbstractList，实现了List 、RandomAccess、Cloneable、Serializable 接口，所以底层基于数组实现容量大小动态变化，是支持快速访问、复制、序列化的。允许null存在。
ArrayList 底层是基于数组来实现容量大小动态变化的。
private int size;//容器中实际元素个数 transient Object[] elementData;注意：上面的 size 是指 elementData 中实际元素个数，而 elementData.length 为集合容量，表示最多可以容纳多少个元素。
private static final int DEFAULT_CAPACITY = 10;DEFAULT_CAPACITY是指ArrayList默认容量大小为10
/** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};这两个数组的意思是用来确定第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。
无参构造函数
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }给elementData赋值了一个空数组。
有参构造函数 构造一个初始容量大小为 initialCapacity 的 ArrayList
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }使用指定 Collection 来构造 ArrayList 的构造函数
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }将 Collection 转化为数组并赋值给 elementData，把 elementData 中元素的个数赋值给 size。 如果 size 不为零，则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。 如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。
add方法
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }添加时先确定容量，然后size自增一，添加元素到相应位置，元素数量加1。
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }先检查下标是否越界，确定容量，修改modCount，然后使用System.arraycopy方法从将旧数组index位置的元素开始复制到新数组index+1的位置，将elementData的index位置放入element值。
remove方法
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }当我们调用 remove(int index) 时，首先会检查 index 是否合法，然后再判断要删除的元素是否位于数组的最后一个位置。如果 index 不是最后一个，就再次调用 System.arraycopy() 方法拷贝数组。如果 index 是最后一个元素那么就直接将数组的最后一个位置制空， 当我们调用 remove(Object o) 时，会把 o 分为是否为空来分别处理。然后对数组做遍历，找到第一个与 o 对应的下标 index，然后调用 fastRemove 方法，删除下标为 index 的元素。
LinkedList 是 Java 集合中比较常用的数据结构，与 ArrayList 一样，实现了 List 接口，只不过 ArrayList 是基于数组实现的，而 LinkedList 是基于链表实现的。所以 LinkedList 插入和删除方面要优于 ArrayList，而随机访问上则 ArrayList 性能更好。 除了 LIst 接口之外，LinkedList 还实现了 Deque，Cloneable，Serializable 三个接口。这说明该数据结构支持队列，克隆和序列化操作的。与 ArrayList 一样，允许 null 元素的存在，且是不支持多线程的。
LinkedList有上面三个成员变量，size 为 LinkedList 的大小，first 和 last 分别为链表的头结点和尾节点。Node 为节点对象。
LinkedList() 仅仅构造一个空的列表。后一个构造方法构造一个包含指定 Collection 中所有元素的列表，该构造方法首先会调用空的构造方法，然后通过 addAll() 的方式把 Collection 中的所有元素添加进去。
add操作
public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }将新节点e置为first，如果原链表为空，last为newNode，如果不为空，f的前节点为newNode。大小加一，计数操作次数加一。
public void addLast(E e) { linkLast(e); } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }同理队尾添加方法。
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }首先检查下标是否越界，然后判断如果 index == size 则添加到末尾，否则将该元素插入的 index 的位置。其中 node(index) 是获取 index 位置的节点，linkBefore 负责把元素 e 插入到 succ 之前。
remove操作
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }先检查下标是否越界，然后调用 unlink 释放节点， 移除指定元素。
1）数据结构的不同，ArrayList是基于数组实现的，LinkedList是基于双链表实现的。LinkedLIst还实现了Deque接口，Deque接口是Queue接口的子接口， 它代表一个双向队列，因此LinkedList可以作为双向队列 ，栈（可以参见Deque提供的接口方法）和List集合使用，功能强大。 2）Array可以直接返回数组种index位置的元素，因此在随机访问集合元素上有较好的性能，但是插入删除需要移动数组插入位置之后的所有元素。 3）相比于ArrayList，LinkedList随机访问集合元素时性能较差，因为需要在双向列表中找到要index的位置，再返回，但插入删除更快，LinkedList中插入或删除的时间复杂度仅为O(1)。 4）都实现了List接口
Vector是矢量队列，它继承了AbstractList，实现了List、 RandomAccess, Cloneable, Serializable接口。因此可以实现队列的相应功能，可以随机访问、克隆、序列化。
Vector内部通过一个Object数组来存储数据，使用elementCount变量来表示实际存储的元素个数。
创建一个空的Vector，并且指定了Vector的初始容量和扩容时的增长系数。
public Vector(int initialCapacity) { this(initialCapacity, 0); }创建一个空的Vector，并且指定了Vector的初始容量。
public Vector() { this(10); }创建一个空的Vector，并且指定了Vector的初始容量为10。
public Vector(Collection<? extends E> c) { elementData = c.toArray(); elementCount = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, elementCount, Object[].class); }根据其他集合来创建一个非空的Vector。
add操作
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }首先看容量是否够，不够进行扩容操作，然后将元素e放置在数组的size位置。储存元素个数加一。
private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }增加元素后，ArrayList中要存储的元素个数为minCapacity，若此时minCapacity > elementData原始的容量，则要扩容。
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }首先获取elementData的原始容量，如果在构造方法中设置了capacityIncrement > 0，那么新数组长度就是原数组长度 + capacityIncrement。否则，新数组长度就是原数组长度 * 2。若进行扩容后，capacity仍然比实际需要的小，则新容量更改为实际需要的大小。如果新数组的长度比虚拟机能够提供给数组的最大存储空间大，则将新数组长度更改为最大正数：Integer.MAX_VALUE。然后按照新的容量newCapacity创建一个新数组，再将原数组中的内容copy到新数组中。
public void add(int index, E element) { insertElementAt(element, index); } public synchronized void insertElementAt(E obj, int index) { modCount++; if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = obj; elementCount++; }remove操作
public boolean remove(Object o) { return removeElement(o); }调用removeElement方法来删除元素。
public synchronized boolean removeElement(Object obj) { modCount++; int i = indexOf(obj); if (i >= 0) { removeElementAt(i); return true; } return false; }首先查找元素obj在数组中的下标，若下标 >= 0，调用removeElementAt（int）方法删除元素。
public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return oldValue; }首先检查下标合法性，获取旧的元素值，计算需要移动的元素个数，移动元素删除。
1）底层实现：ArrayList：数组 ，Vector：数组， LinkedList：双向链表 采用数组作为数据存储结构的ArrayList、Vector查询速度快（可以根据下标直接取，比迭代查找更快），增删慢。LinkedList增删快，查询慢。 2）线程安全：Vector：线程安全，ArrayList：非线程安全，LinkedList:非线程安全，如果是开发中没有线程同步的需求，推荐优先使用ArrayList。因此其内部没有synchronized，执行效率会比Vector快很多。 3）扩容方面：由于ArrayList和Vector基于数组实现，当数组长度不够时，其内部会创建一个更大的数组，然后将原数组中的数据拷贝至新数组中。如果在创建Vector时不指定capacityIncrement（自动扩展长度）的值，如需扩展，则每次至少扩展至原长度的2倍。
