更多 Java 集合类方面的文章，请参见文集《Java 集合类》

共同点：

• 都实现了 List 接口

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 class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• 都可以插入 null

基本区别：

• 实现方式：

  • ArrayList 和 Vector 基于数组实现，可以随机访问，实现了 RandomAccess 接口
  • LinkedList 基于链表实现，不可随机访问，实现了 Deque 接口

• 初始容量：

  • ArrayList 初始容量为 10
  • Vector 初始容量为 10
  • LinkedList 基于链表实现，初始容量为 0

• 扩容方式：

  • ArrayList 数组容量不够时，扩容 50% int newCapacity = oldCapacity + (oldCapacity >> 1);
  • Vector 数组容量不够时，扩容 100%
  • LinkedList 基于链表实现，无需考虑扩容

• 是否线程安全：

  • ArrayList 线程不安全
  • Vector 线程安全
  • LinkedList 线程不安全

ArrayList 的实现原理

构造

• public ArrayList() 可以构造一个默认初始容量为 10 的空列表；
  • private static final int DEFAULT_CAPACITY = 10;
• public ArrayList(int initialCapacity) 构造一个指定初始容量的空列表；
• public ArrayList(Collection<? extends E> c) 构造一个包含指定 collection 的元素的列表，这些元素按照该 collection 的迭代器返回它们的顺序排列的。

调整数组容量

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。
数组扩容有两个方法：

• 开发者可以通过一个 public 的方法 ensureCapacity(int minCapacity) 来增加 ArrayList 的容量：

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

• 而在存储元素等操作过程中，如果遇到容量不足，会调用 private 方法 private void ensureCapacityInternal(int minCapacity)
  实现：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

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

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

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

数组的扩容操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。

• 当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。
• 或者根据实际需求，通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。

LinkedList 的实现原理

使用链表

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

双端链表

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

引用：
ArrayList 的实现原理
LinkedList 的实现原理