JAVA 集合方面，第一個(gè)，必須得從 ArrayList 開始，畢竟 ArrayList 可以稱得上是集合方面最常用的類了，估計(jì)沒有之一。

ArrayList 實(shí)現(xiàn)了 List 接口，是基于數(shù)組實(shí)現(xiàn)的。小伙伴們都知道，數(shù)組的大小是固定的，創(chuàng)建的時(shí)候指定了大小，就不能再調(diào)整了，如果數(shù)組滿了，就不能再添加任何元素了。ArrayList 是數(shù)組很好的替代方案，它提供了比數(shù)組更豐富的預(yù)定義方法（增刪改查），并且大小是可以根據(jù)元素的多少進(jìn)行自動(dòng)調(diào)整的，非常靈活。

準(zhǔn)備在 ArrayList 的第四個(gè)位置（下標(biāo)為 3）上添加一個(gè)元素 55。

此時(shí) ArrayList 中第五個(gè)位置以后的元素將會(huì)向后移動(dòng)。

準(zhǔn)備把 23 從 ArrayList 中移除。

此時(shí)下標(biāo)為 7、8、9 的元素往前挪。

01、如何創(chuàng)建一個(gè) ArrayList

ArrayList<String> alist = new ArrayList<String>();

可以通過上面的語句來創(chuàng)建一個(gè)字符串類型的 ArrayList（通過尖括號來限定 ArrayList 中元素的類型，如果嘗試添加其他類型的元素，將會(huì)產(chǎn)生編譯錯(cuò)誤），更簡化的寫法如下：

List<String> alist = new ArrayList<>();

由于 ArrayList 實(shí)現(xiàn)了 List 接口，所以 alist 變量的類型可以是 List 類型；new 關(guān)鍵字聲明后的尖括號中可以不再指定元素的類型，因?yàn)榫幾g器可以通過前面尖括號中的類型進(jìn)行智能推斷。

如果非常確定 ArrayList 中元素的個(gè)數(shù)，在創(chuàng)建的時(shí)候還可以指定初始大小。

List<String> alist = new ArrayList<>(20);

這樣做的好處是，可以有效地避免在添加新的元素時(shí)進(jìn)行不必要的擴(kuò)容。但通常情況下，我們很難確定 ArrayList 中元素的個(gè)數(shù)，因此一般不指定初始大小。

02、向 ArrayList 中添加一個(gè)元素

可以通過 add() 方法向 ArrayList 中添加一個(gè)元素，如果不指定下標(biāo)的話，就默認(rèn)添加在末尾。

alist.add("王二");

感興趣的小伙伴可以研究一下 add() 方法的源碼，它在添加元素的時(shí)候會(huì)執(zhí)行 grow() 方法進(jìn)行擴(kuò)容，這個(gè)是面試官特別喜歡考察的一個(gè)重點(diǎn)。

下面是 add(E e) 方法的源碼：

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

調(diào)用了私有的 add(E e, Object[] elementData, int s) 方法：

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

然后調(diào)用了非常關(guān)鍵的 grow(int minCapacity) 方法：

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

如果創(chuàng)建 ArrayList 的時(shí)候沒有指定初始大小，那么 ArrayList 的初始大小就是 DEFAULT_CAPACITY：

private static final int DEFAULT_CAPACITY = 10;

可以容納 10 個(gè)元素。

還可以通過 add(int index, E element) 方法把元素添加到指定的位置：

alist.add(0, "王三");

add(int index, E element) 方法的源碼如下：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
            elementData, index + 1,
            s - index);
    elementData[index] = element;
    size = s + 1;
}

該方法會(huì)調(diào)用到一個(gè)非常重要的本地方法 System.arraycopy()，它會(huì)對數(shù)組進(jìn)行復(fù)制（要插入位置上的元素往后復(fù)制，參照文章一開頭提到的兩張圖片）。

03、更新 ArrayList 中的元素

可以使用 set() 方法來更改 ArrayList 中的元素，需要提供下標(biāo)和新元素。

alist.set(0, "王四");

原來 0 位置上的元素為“王三”，現(xiàn)在將其更新為“王四”。

來看一下 set() 方法的源碼：

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

該方法會(huì)先對指定的下標(biāo)進(jìn)行檢查，看是否越界，然后替換新值并返回舊值。

04、刪除 ArrayList 中的元素

remove(int index) 方法用于刪除指定下標(biāo)位置上的元素，remove(Object o) 方法用于刪除指定值的元素。

alist.remove(1);
alist.remove("王四");

先來看 remove(int index) 方法的源碼：

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

該方法返回要?jiǎng)h除的元素，真正的刪除操作在 fastRemove(es, index) 方法中。

再來看 remove(Object o) 方法的源碼：

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

該方法通過 break label 的方式找到要?jiǎng)h除元素（null 的時(shí)候使用 == 操作符判斷，非 null 的時(shí)候使用 equals() 方法，意味著如果有相同元素時(shí)，刪除第一個(gè)）的下標(biāo)，然后調(diào)用 fastRemove() 方法。

既然都調(diào)用了 fastRemove() 方法，那就繼續(xù)來跟蹤一下源碼：

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

當(dāng)刪除的是末尾的元素時(shí)，不需要復(fù)制數(shù)組，直接把末尾的元素賦值為 null 即可；否則的話，就需要調(diào)用 System.arraycopy() 對數(shù)組進(jìn)行復(fù)制。參照文章一開頭提到的第三張、第四張圖片。

05、查找 ArrayList 中的元素

如果要正序查找一個(gè)元素，可以使用 indexOf() 方法；如果要倒序查找一個(gè)元素，可以使用 lastIndexOf() 方法。

alist.indexOf("王二");
alist.lastIndexOf("王二");

來看一下 indexOf() 方法的源碼：

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

如果元素為 null 的時(shí)候使用“==”操作符，否則使用 equals() 方法——該方法不是 null 安全的。

lastIndexOf() 方法和 indexOf() 方法類似，不過遍歷的時(shí)候從最后開始。

contains() 方法可以判斷 ArrayList 中是否包含某個(gè)元素，其內(nèi)部調(diào)用了 indexOf() 方法：

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

如果 ArrayList 中的元素是經(jīng)過排序的，就可以使用二分查找法，效率更快。

Collections 類的 sort() 方法可以對 ArrayList 進(jìn)行排序，該方法會(huì)按照字母順序?qū)?String 類型的列表進(jìn)行排序。如果是自定義類型的列表，還可以指定 Comparator 進(jìn)行排序。

List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");

Collections.sort(copy);
System.out.println(copy);

輸出結(jié)果如下所示：

[a, b, c, d]
1

排序后就可以使用二分查找法了：

int index = Collections.binarySearch(copy, "b");

06、最后

關(guān)于 ArrayList，就先介紹這么多吧，通過源碼的角度，我想小伙伴們一定對 ArrayList 有了更深刻的印象。

簡單總結(jié)一下 ArrayList 的時(shí)間復(fù)雜度，方便后面學(xué)習(xí) LinkedList 時(shí)作為一個(gè)對比。

1）通過下標(biāo)（也就是 get(int index)）訪問一個(gè)元素的時(shí)間復(fù)雜度為 O(1)，因?yàn)槭侵边_(dá)的，無論數(shù)據(jù)增大多少倍，耗時(shí)都不變。

2）添加一個(gè)元素（也就是 add()）的時(shí)間復(fù)雜度為 O(1)，因?yàn)橹苯犹砑拥侥┪病?/p>

3）刪除一個(gè)元素的時(shí)間復(fù)雜度為 O(n)，因?yàn)橐闅v列表，數(shù)據(jù)量增大幾倍，耗時(shí)也增大幾倍。

4）查找一個(gè)未排序的列表時(shí)間復(fù)雜度為 O(n)，因?yàn)橐闅v列表；查找排序過的列表時(shí)間復(fù)雜度為 O(log n)，因?yàn)榭梢允褂枚植檎曳ǎ?dāng)數(shù)據(jù)增大 n 倍時(shí)，耗時(shí)增大 logn 倍（這里的 log 是以 2 為底的，每找一次排除一半的可能）