ArrayList入門實踐

構造函數

ArrayList 有三個構造函數，默認不帶參數的構造函數就是初始化一個空數組。

//一個空數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//實際存儲元素的數組
transient Object[] elementData; 

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

帶一個 int 類型的容量參數的構造函數，可以指定 ArrayList 的容量大小。

//空數組
private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //容量大于 0 就構建一個 Object 的數組
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //容量等于 0 就是一個空數組
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //容量小于 0 拋出異常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    }
}

帶一個集合的構造函數, 將集合轉換成 Object[] 類型后拷貝到 elementData 中。

public ArrayList(Collection< ? extends E > c) {
    //集合轉為數組
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        //集合是不是 ArrayList 類型
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            //將集合元素拷貝成 Object[] 到 elementData
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        //空元素
        elementData = EMPTY_ELEMENTDATA;
    }
}

常用函數

add()

先從 ArrayList 最常用的方法 add() 開始講起，add() 方法就是將元素添加到 elementData 的末尾。平均時間復雜度為 O(1)。

//ArrayList.add()
public boolean add(E e) {
    //檢查數組是否存放的下
    ensureCapacityInternal(size + 1); 
    //添加到末尾
    elementData[size++] = e;
    return true;
}

//ArrayList.ensureCapacityInternal()
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//ArrayList.calculateCapacity()
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //檢查時不是默認時的空數組，是默認時的空數組，初始化的容量就是 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//ArrayList.ensureExplicitCapacity()
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

//ArrayList.grow()
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);
    //copy 成一個新數組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

1. 擴容的大小為原長度+1/2的原長度
2. 如果擴容長度比傳入的最小容量小，則使用最小容量,如果擴容長度超過設定的最大容量,則實際用最大容量
3. 初始化默認長度為10,當添加到11個長度時,容量為15

add(int index, E element)

將元素插入到指定的位置，主要的操作是將指定位置之后的元素往后移動一個位置，空出 index 位置。平均時間復雜度為 O(n)。

//ArrayList.add(int index, E element)
public void add(int index, E element) {
    //index的越界檢查
    rangeCheckForAdd(index);
    //擴容
    ensureCapacityInternal(size + 1); 
    //將 index 之后的所有元素 copy 到往后挪動一位
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);

    //將 index 位置放入新元素
    elementData[index] = element;
    //數量 + 1
    size++;
}

get()

get() 應該是第二個常用的函數，可以返回隨機位置的元素。需要注意的是越界時，超過容量返回的是 IndexOutOfBoundsException 異常，index 太小返回的是 ArrayIndexOutOfBoundsException 異常。平均時間復雜度為 O(1)。

//ArrayList.get()
public E get(int index) {
    //index 越界檢查
    rangeCheck(index);
    //返回指定位置的元素
    return elementData(index);
}

//ArrayList.rangeCheck()
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//ArrayList.elementData()
E elementData(int index) {
    return (E) elementData[index];
}

remove()

刪除指定位置的元素，并返回刪除的元素。平均時間復雜度為 O(n)。

//ArrayList.remove()
public E remove(int index) {
    //越界檢查
    rangeCheck(index);

    modCount++;
    //取出元素
    E oldValue = elementData(index);
    //拷貝數組，將 index 之后的元素往前移動一個位置
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    //最后一個元素置 null
    elementData[--size] = null; 

    return oldValue;
}

remove(Object o)

刪除指定的元素，需要循環(huán)數組刪除第一個指定的元素。平均時間復雜度為 O(n)。

//ArrayList.remove(Object o)
public boolean remove(Object o) {
    if (o == null) {
        //循環(huán)整個數組，找出第一個需要刪除的元素
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        //循環(huán)整個數組，找出第一個需要刪除的元素
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//ArrayList.fastRemove
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    elementData[--size] = null;

總結

1. ArrayList 內部用一個數組存儲元素，容量不夠時會擴容原來的一半。
2. ArrayList 實現了 RandomAccess，支持隨機訪問。
3. ArrayList 實現了 Cloneable，支持被拷貝克隆。
4. ArrayList 刪除指定元素和指定位置上的元素的效率不高，需要遍歷數組。