为方便开发人员，JDK提供了一套主要数据结构的实现，比如List、Map等。今儿说说List接口。
List接口的一些列实现中，最常用最重要的就是这三个：ArrayList、Vector、LinkedList。
JDK中这三个类的定义：
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializablepublic class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializablepublic class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
从这三个类定义就可以看出一些信息：
下面详细说说这三个List实现。
这三个里面，免备案空间，ArrayList和Vector使用了数组的实现，相当于封装了对数组的操作。这也正是他们能够支持快速随机访问的原因，多说一句，JDK中所有基于数组实现的数据结构都能够支持快速随机访问。
ArrayList和Vector的实现上几乎都使用了相同的算法，他们的主要区别就是ArrayList没有对任何一个方法做同步，所以不是线程安全的；而Vector中大部分方法都做了线程同步，是线程安全的。
LinkedList使用的是双向循环链表的数据结构。由于是基于链表的，所以是没法实现随机访问的，只能顺序访问，这也正式它没有实现RandomAccess接口的原因。
正式由于ArrayList、Vector和LinkedList所采用的数据结构不同，注定他们适用的是完全不同的场景。
通过阅读这几个类的源码，我们可以看到他们实现的不同。ArrayList和Vector基本一样，我们就拿ArrayList和LinkedList做对比。
在末尾增加一个元素
ArrayList中的add方法实现如下：
add(E e) {elementData[size++] = e;;5}
这个方法做两件事情，首先确保数组空间足够大，然后在数组末尾增加元素并且通过后++使得完成size+1。
从这个代码可以看出，如果数组空间足够大，那么只是数组的add操作就是O(1)的性能，非常高效。
在看看ensureCapacityInternal这个方法的实现：
ensureCapacityInternal(int minCapacity) { 2modCount++;(minCapacity – elementData.length > 0) 5 grow(minCapacity); 6 }grow(int minCapacity) {oldCapacity = elementData.length;11int newCapacity = oldCapacity + (oldCapacity >> 1);12if (newCapacity – minCapacity < 0)13newCapacity = minCapacity;14if (newCapacity – MAX_ARRAY_SIZE > 0)15newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);18}
可以看出，如果数组空间不够，那么这个方法就会做数组扩容和数组复制操作，看第11行，JDK利用移位运算符进行扩容计算，>>1右移一位表示除2，所以newCapacity就是扩容为原来的1.5倍。
PS：这里的代码都是JDK1.7中的实现，JDK1.7对1.6的很多代码做了优化，比如上面这段扩容代码，在JDK1.6中第11行是直接除2，显然，移位运算要更高效。
在看看LinkedList中的add方法：
add(E e) { 2 linkLast(e);; 4 } linkLast(E e) { 7final Node<E> l = last; 8final Node<E> newNode = new Node<>(l, e, null); 9last = newNode;10if (l == null)11first = newNode;l.next = newNode;14size++;15modCount++;16}
1Node(Node<E> prev, E element, Node<E> next) {2this.item = element;3this.next = next;4this.prev = prev;5}
从这段add代码可以看出，LinkedList由于使用了链表，所以不需要进行扩容，直接把元素加到链表最后，把新元素的前驱指向之前的last元素，并把last元素指向新元素就ok。这也是一个O(1)的性能。
测试一下：
main(String[] args) {begin = System.currentTimeMillis();List<Object> list = new LinkedList<Object>(); 7Object obj = new Object(); 8for(int i=0; i<50000; i++){ 9 list.add(obj);10 }end = System.currentTimeMillis();13long time = end – begin;14System.out.println(time+””);15 16}
分别对ArrayList和LinkedList做末尾add操作，循环50000次，ArrayList耗时6ms，而LinkedList耗时8ms，虚拟主机，这是由于LinkedList在add时候需要更多的对象创建和赋值操作。
在任意位置插入元素
ArrayList中的实现如下：
努力爱一个人。付出，不一定会有收获；
