本文包含常見的ArrayList的基本知識。在一些主題下也自然地引出了Colletion類的一些相關知識。

一.ArrayList的底層數(shù)據(jù)結構

ArrayList底層是使用一個Object[]數(shù)組來存儲數(shù)據(jù)的，所以它本質上是一個線性存儲結構。這就造成了它可以在O(1)時間內(nèi)隨機訪問任意一個元素。但插入元素或刪除元素時就要移動大量的元素，時間復雜度是O(n)

二.ArrayList初始化和容量增長規(guī)則

默認初始化
ArrayList初始化時如果不指定容量大小，則默認大小為10。但元素數(shù)組elementData并不是在構造方法中完成容量為10的初始化的，而是在第一次添加元素時，才生成大小為10的數(shù)組。

每次添加元素，首先要檢測當前數(shù)組的容量是否滿足當前size+1,（size指當前持有元素的個數(shù)），如果不滿足則擴展數(shù)組大小為oldCapacity + (oldCapacity >> 1)，即為原大小的1.5倍。

帶容量參數(shù)
如果傳入容量參數(shù)進行初始化，則會直接生成相應大小的數(shù)組。

從Collection初始化
可以給ArrayList傳入一個Collection來初始化，初始化后的ArrayList和原Collection無關，是一種深拷貝。這個方法在復制ArrayList時有用。

相關代碼：

//保存元素的數(shù)組
transient Object[] elementData; // non-private to simplify nested class access

//默認構造方法
//elementData指向一個static final常量，該常量為一個長度為0的Object[]數(shù)組
//在第一次添加元素時，會生成長度為10的數(shù)組
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//傳入容量參數(shù)的構造方法
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);
    }
}

//深拷貝Collection進行初始化
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

三.elementData為什么使用transient修飾

首先，ArrayList是實現(xiàn)了java.io.Serializable接口，即ArrayList是支持序列化的。

其次，transient關鍵字的意思是序列化時要跳過的元素，即不進行序列化。

看起來是有矛盾的，但java中除了默認序列化外，還可以在類中提供writeObject()方法進行自定義序列化，和readObject()方法進行自定義反序列化。ArrayList就是這么做的。

而由于elementData數(shù)組中往往有沒有用到的空間，為了不讓這些無意義的元素也序列化，就自定義了序列化方法，只序列化0到size-1的元素，從而節(jié)省序列化后的占用空間。

源碼如下：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}


private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

四.forEach循環(huán)是怎么實現(xiàn)的

請看我之前的一篇文章

五.ArrayList轉化為數(shù)組

ArrayList中有兩個方法可以轉換為數(shù)組，一個是toArray()：轉換為Object[]數(shù)組。由于Object[]類型不能強制轉換為Integer[]等子類型，所以這個方法不使用。toArray()還有一個帶參數(shù)的版本（傳入一個數(shù)組），可以將elementData轉換為傳入的數(shù)組類型并返回，如果傳入的數(shù)組大小夠裝下所有的ArrayList元素，則直接使用傳入的數(shù)組，否則新建數(shù)組。
使用舉例：

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i = 0; i < 10; i++)
        list.add(i);
    //傳入大小和ArrayList元素個數(shù)一樣的數(shù)組就不用再新建數(shù)組了
    Integer[] arr = list.toArray(new Integer[list.size()]);
    System.out.println(Arrays.toString(arr));
}

六.將其它Collection的元素添加到ArrayList

使用addAll(Collection<? extends E> e)方法，可以看到參數(shù)需要是一個Collection，并且泛型類必須是當前ArrayList持有的類型或其子類。

這個方法其實是Collection接口的一個方法，這也就是說所有Collection的實現(xiàn)類之間都可以通過addAll這個方法來相互合并。

使用舉例

ArrayList<Integer> list = new ArrayList<Integer>();
HashSet<Integer> set = new HashSet<Integer>();  //Set接口也實現(xiàn)了Collection接口
for(int i = 10; i < 15; i++) set.add(i);
list.addAll(set);
System.out.println(list);

//同理，也可以將ArrayList添加到Set中
set.add(list);
System.out.println(set);

七.打印ArrayList

在其父類的父類AbstractCollection中實現(xiàn)了一個toString()方法。所以可以調(diào)用list.toString()來獲取ArrayList的字符串形式。使用System.out.println(list)打印時，toString()可以省略。

下面順便記錄一下Collection的體系結構：

1. Collection是集合類的頂層接口。它繼承自Iterable，保證了所有Collection的實現(xiàn)類都可以通過迭代器或forEach循環(huán)訪問元素；它定義了add()、remove()、size()、iterator()等基本的功能方法;
2. 按照面向對象設計的常用的一個技巧，通常會使用一個抽象類來實現(xiàn)子類共同的功能。Collection體系中也是這么做的。AbstractCollection抽象類實現(xiàn)了Collection接口，就是在這里實現(xiàn)了toString()、addAll()等方法。
3. 在AbstractCollection之下又實現(xiàn)了AbstractList、AbstractSet、AbstractQueue三個接口，也是定義List、Set、Queue各自通用的功能。

最后，歡迎大家關注我的基礎知識專題、Java并發(fā)專題，查看更多相關文章。