ArrayList

基于数组实现，通过下标访问元素时速度很快，根据下标的遍历性能优于迭代器遍历。 在中间插入、或者尾部插入遇到扩容、非尾部删除时，由于需要进行数组的复制重整，效率较低。

初始容量

在不指定数组大小的情况下，初始容量为0，在添加第一个元素时，扩展成默认容量10。

添加元素

检查容量

检查当前元素个数+1是否超过数组长度，超过进行扩容。

扩容方法： 定义数组长度最大值MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8， 取原数组长度+原数组长度>>2 ，即原长度的1.5倍 ，如果该值超过了MAX_ARRAY_SIZE,看原长度+1是否超过MAX_ARRAY_SIZE，如果没超过则扩容到MAX_ARRAY_SIZE，否则扩容到Integer.MAX_VALUE。

因为某些虚拟机的数组可能存有header words,实际长度可能达不到Integer.MAX_VALUE,这样处理减小溢出几率。

中间插入

System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;

通过复制覆盖的方式将index位以及之后的元素向后移动一位，再在index位上插入数据。 所以ArrayList中间插入时，越靠近头部插入代价越大。

删除元素

通过复制覆盖的方式将index位之后的元素向前移动一位。

ArrayList总结

1. 初始容量是0，第一次添加元素的时候设置数组长度为默认值10
2. 添加元素时先检查容量，容量不够进行扩容。
3. 扩容1.5倍，但不超过Integer.MAX-8,超过后再扩容为Integer.MAX
4. 性能瓶颈主要在添加元素时的扩容和删除非尾部元素时的数组移位。

Vector

基于数组实现，每个方法都加了同步锁synchronized。 扩容每次扩大2倍。

Stack

Stack继承与Vector，添加了栈方法。

LinkedList

基于双向链表实现，不需要扩容操作。插入元素效率高，访问元素慢。

LinkedList实现了Queue、Deque,可用于实现栈和队列。

PriorityQueue

优先队列，内部采用数组实现的堆，不允许null元素

PriorityQueue.offer

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        //扩容
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        //在末尾添加元素 并维护堆
        siftUp(i, e);
    return true;
}
//根据是元素实现了比较器还是有外部比较器选择维护堆的方法
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        //循环 与父节点比较
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

Priority.poll

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    //取堆顶数据
    E result = (E) queue[0];
    //尾部数据放到堆顶
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        //向下维护堆
        siftDown(0, x);
    return result;
}
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    //只需要处理非叶节点
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        //选出子节点，然后与父节点比较 是否需要交换
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

Priority.remove

private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        //把末尾数据移到删除的位置 向下维护堆
        siftDown(i, moved);
        // 如果节点下沉了，说明原尾部数据可以作为删除数据的子节点的子节点，则不需要向上维护堆，否则，就需要向上维护堆
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

CopyOnWriteArrayList

为了解决多线程情况下，遍历的数组可能已被修改，会抛出ConcurrentModificationException异常的问题。

修改数组时，先复制一份，修改完后，将原数组的地址引用指向新数组。

以add方法为例：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //复制
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        //指向新数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}