类声明

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

其中

public abstract class AbstractSequentialList<E> extends AbstractList<E>

可以看到，它们的共同点是

都继承 AbstractList 类
都实现了 List 接口
都实现了 Cloneable 接口
都实现了 Serializable 接口

区别

ArrayList 实现了 RandomAccess 接口，因为它底层是使用数组（会自动 resize）来维护的，而数组是可随机访问的。 LinkedList 实现了 Deque 接口，该接口是一个支持两端元素插入和移除的线性集合。它是英文 double ended queue 的简写。

共同点

它们都不是线程安全的，因为它们的方法并没有任何同步语义
它们都是 List 这个数据结构的实现（有序列表）

区别

实现上不同。ArrayList 使用的是动态数组来维护该列表，而 LinkedList 使用的是双向链表来实现
根据实现的不同，就决定了它们各自的特点：ArrayList 读取性能快(O(1))，而 LinkedList 修改（插入或删除）性能快(O(1))
内存占用不同因为链表是使用前后指针来进行维护的，所以要占用一些额外的内存占用，而数组实现的方式则不需要。

注意点

因为 ArrayList 使用的是动态数组来维护，所以为了避免频繁地进行数组的内存分配与复制，最好要事先估算它的大小，然后提供足够的容量大小因子(这个参数只有在 ArrayList 才会有)来初始化它。

扩容的触发条件:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

即 minCapacity - elementData.length > 0 时，就需要扩容了。扩容源码:

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

首先，将大小扩大为原内部维护的数组大小的 oldCapacity + (oldCapacity>>1)，即 1.5 倍（右移一位，相当于除以2，即 oldCapacity + oldCapacity/2）如果扩大后的大小，还是小于 minCapacity ，则 newCapacity = minCapacity，否则是扩大后1.5倍的大小为基准将再 newCapacity 与 MAX_ARRAY_SIZE 比较，判断是不是超大数组，如果是超大数组，则以 Integer.MAX_VALUE 为最终的扩大大小。

注意，initCapacity 是在一开始的时候，就会 new Object[initCapacity] 大小的Object数组引用的了。

删除元素

如果想在循环里删除元素，一定要用 Iterator 来进行 remove ，而不要使用 List.remove() ！！

同步的 List

List list = Collections.synchronizedList(new ArrayList());

通过源码注释可知，这种 List ，在进行迭代的时候，需要手动同步(其他的通过 Collections.synchronizedXXXX() 返回的对象也一样):

     * <pre>
     *  List list = Collections.synchronizedList(new ArrayList());
     *      ...
     *  synchronized (list) {
     *      Iterator i = list.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * </pre>

Vector

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到它和 ArrayList 实现的接口和继承的类都是一样的。最最主要的区别就是，这个类是线程安全的，因为它的所有涉及线程安全的方法，都添加了 synchronized 关键字来进行同步了。

它和 ArrayList 的扩容大小不同:

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

capacityIncrement 可以通过构造函数来提供，默认为0，即如果不提供 capacityIncrement 参数，则以2倍的大小来进行扩容。

Vector 还是 Collections.synchronizedList ?

这个问题，首先要考虑你之前是否已经有了 List 的数据。因为如果之前已经有了数据的，但想转换为同步的数据，这时它们的区别是:

Vector ：虽然它有个构造函数，提供以另一个 Collection 类型为参数来进行初始化，不过，这会 *导致复制数据*，即完全是以 Vector 为基准了

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

Collections.synchronizedList ：这种方式，只是一种包装，即它不会进行数据复制，底层还是引用了相同的数据结构，只是在方法上提供了同步的语义（synchronized）

        final List<E> list;

        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }

参考资料

When to use LinkedList over ArrayList?

JDK 之 ArrayList 和 LinkedList 源码阅读笔记

Contents

类声明

共同点

区别

注意点

删除元素

同步的 List

Vector

Vector 还是 Collections.synchronizedList ?

参考资料