1 概述

List 接口规定它的实现类需要有以下特性

是一个有序集合
可以包含多个相同的元素
访问指定位置的元素
Java 集合框架实现List接口的有三个常用类ArrayList, LinkedList 和 Vector

2 ArrayList

ArrayList的底层实际上是在维护一个数组，由于数组的内存是连续的，所以可以很方便地通过索引index来访问指定位置的元素。
数组在初始化的时候长度固定了，所以如何设置数组的长度成了一个问题。ArrayList提供了一个构造器来设置初始值。如果不传入这个值，会把elementData初始化为ArrayList里维护的一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

   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);
        }
    }

添加的元素超过当前数组的长度是不可避免的，那么当前数组容量不够的时候，就需要一个更长的数组。第一个问题就是新数组的长度怎么定呢?
- 定小了，很容易达到下一次饱和，就需要不停开辟新的数组，拷贝数组。
- 定得太大了，申请了一大片内存很可能根本用不到，浪费！
ArrayList提供的扩容策略是
- 首先保证当前操作需要的最小容量 minCapacity
- 然后假定我需要扩容的容量是 newCapacity = oldCapacity + (oldCapacity << 1) 也就是现有容量的1.5倍
- 取两个值更大的那个 newCapacity = max(minCapacity, newCapacity)
- 再与数组理论上允许的最大值 MAX_ARRAY_SIZE(等于Integer.MAX_VALUE - 8) 比较，如果minCapacity比MAX_ARRAY_SIZE还大，直接把容量扩充到Integer.MAX_VALUE

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

总之，由于数组的特性，ArrayList 在访问元素的时候可以通过内存地址偏移量快速访问。在执行需要改变数组结构的操作时，性能就比较差。

3 LinkedList

LinkedList的底层维护的是一个双向链表，检索指定位置的元素时必须从头开始访问或从尾部开始遍历（会先判断离头近还是离尾巴近, get(index)方法实际调用了下面这个方法

    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

双向链表在添加和插入元素的时候特别方便，只要维护前后节点就好了。所以LinkedList的添加和插入性能好。

4 Vector

Verctor 就是一个线程安全的ArrayList, 每个接口都使用了synchronized关键字修饰。

5 ListIterator

ListIterator是一个为List定制的接口，继承自Iterator。ListIterator 额外定义了hasPrevious()和previous()方法，所以可以从后往前迭代。

6 总结

ArrayList, LinkedList 和 Vector 都实现了List接口
Vector通过synchronized关键字修饰方法，是线程安全的。ArrayList和LinkedList不是线程安全的。
ArrayList在通过索引访问get(index)和修改set(index, e)时性能比LinkedList要好，在执行需要改变数组结构的操作比如插入，删除和容量不足时的添加操作时性能比LinkedList要差。