常用的List集合

ArrayList的一些特点及原理

特点是排列有序，可重复，底层使用数组存储，读取速度快，增删慢，getter()和setter()方法快,线程不安全，当容量不够时，ArrayList会扩容当前容量的一半。

看如下源码：

//默认容量
private static final int DEFAULT_CAPACITY = 10;
//一个空的数组，当初始化的容量为0时，让数组变量elementData指向此数组对象。
private static final Object[] EMPTY_ELEMENTDATA = {};
//一个空的数组，这个空的数组和另外一个空数组作用是不同的，使用无参构造函数时，让数组变量elementData指向此数组，
//在数组列表采取add()操作时，会判断(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA)，如果为ture,会将elementData修改为默认容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList实际存放数据的数组变量
transient Object[] 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);
    }
}
//无参的构造函数，使用默认的空数组，
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
           

从源码可以看出，ArrayList本质上就是数组，当采用无参的构造函数初始化的时候，最初容量是0，等到采用add()操作时，会将容量设为默认的容量10

add()操作的源码：

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++;

        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
private void grow(int minCapacity) {
        //以前的容量
        int oldCapacity = elementData.length;
        //新的容量，新容量为原容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        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;
    }
           

从上面的源码可以看出，通常情况下，数组列表的容量扩容是增加当前容量的一半，即扩容后的容量为原容量的1.5倍，而且并不是可以无限扩容的，为了防止内存溢出，源码做了最大容量的限制。相关的新增删除的操作没有加锁或者synchronized关键字，因此线程不安全。

LinkedList的一些特点及原理

排列有序，可重复，底层使用双向循环链表数据结构存储，查询速度慢，增删快，add()和remove()方法快，线程不安全。LinkedList内部定义了内部类Node作为双向链表的数据节点。因此双向链表的操作的特点就是LinkedList操作的特点，并且相关的新增删除的操作没有加锁或者synchronized关键字，因此线程不安全。

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

Vector的一些特点及原理

排序有序，可重复，底层使用数组存储，读取速度快，增删慢，线程安全，sychronized关键字加在方法上，效率低，默认容量是10，当容量不够时，Vector默认扩展一倍容量。

查看部分源码：

protected Object[] elementData;
    //指定的扩容量
    protected int capacityIncrement;

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    //当采用无参的构造函数时，默认设置容量为10
    public Vector() {
        this(10);
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //从这一行代码看出，当没有指定扩容量的时候，默认的扩容原容量的一倍，及扩容后的容量是扩容前的两倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

  
           

从源码可以看出Vector的内部其实和ArrayList一样也是使用数组存储，因此这两个类很多相似点，不同的是：

1.ArrayList 在内部定义数组的时候使用了transient关键字，而Vector没有使用该关键字，因此在对象这两个类定义的对象在在序列化的时候是不同的

2.ArrayList默认的扩容是当前容量的一半，即扩容后是原容量的1.5倍，而Vector默认的扩容是当前容量的一倍，即扩容后是原容量的2倍。

3.ArrayList的相关操作是线程不安全的，而Vector在相关的操作方法前加了Synchronized关键字，因此是线程安全的。