常用的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關鍵字，是以是線程安全的。