ArrayList實(shí)現(xiàn)了List接口，是順序容器，即元素存放的數(shù)據(jù)與放進(jìn)去的順序相同，允許放入null元素，底層通過數(shù)組實(shí)現(xiàn)。除該類未實(shí)現(xiàn)同步外，其余跟Vector大致相同。每個(gè)ArrayList都有一個(gè)容量（capacity），表示底層數(shù)組的實(shí)際大小，容器內(nèi)存儲(chǔ)元素的個(gè)數(shù)不能多于當(dāng)前容量。當(dāng)向容器中添加元素時(shí)，如果容量不足，容器會(huì)自動(dòng)增大底層數(shù)組的大小。前面已經(jīng)提過，Java泛型只是編譯器提供的語法，所以這里的數(shù)組是一個(gè)Object數(shù)組，以便能夠容納任何類型的對(duì)象。

size(), isEmpty(), get(), set()方法均能在常數(shù)時(shí)間內(nèi)完成，add()方法的時(shí)間開銷跟插入位置有關(guān)，addAll()方法的時(shí)間開銷跟添加元素的個(gè)數(shù)成正比。其余方法大都是線性時(shí)間。

為追求效率，ArrayList沒有實(shí)現(xiàn)同步（synchronized），如果需要多個(gè)線程并發(fā)訪問，用戶可以手動(dòng)同步，也可使用Vector替代。

? ? ? ? ? ? ? ? ? ? ? ? ? ?

set()

set()

既然底層是一個(gè)數(shù)組ArrayList的set()方法也就變得非常簡單，直接對(duì)數(shù)組的指定位置賦值即可。

public E set(int index, E element) {
? ?rangeCheck(index);//下標(biāo)越界檢查
? ?E oldValue = elementData(index);
? ?elementData[index] = element;//賦值到指定位置，復(fù)制的僅僅是引用
? ?return oldValue;
}

get()方法同樣很簡單，唯一要注意的是由于底層數(shù)組是Object[]，得到元素后需要進(jìn)行類型轉(zhuǎn)換。

public E set(int index, E element) {
? ?rangeCheck(index);//下標(biāo)越界檢查
? ?E oldValue = elementData(index);
? ?elementData[index] = element;//賦值到指定位置，復(fù)制的僅僅是引用
? ?return oldValue;
}

跟C++ 的vector不同，ArrayList沒有push_back()方法，對(duì)應(yīng)的方法是add(E e)，ArrayList也沒有insert()方法，對(duì)應(yīng)的方法是add(int index, E e)。這兩個(gè)方法都是向容器中添加新元素，這可能會(huì)導(dǎo)致capacity不足，因此在添加元素之前，都需要進(jìn)行剩余空間檢查，如果需要?jiǎng)t自動(dòng)擴(kuò)容。擴(kuò)容操作最終是通過grow()方法完成的。

private void grow(int minCapacity) {
? ?int oldCapacity = elementData.length;
? ?int newCapacity = oldCapacity + (oldCapacity >> 1);//原來的1.5倍
? ?if (newCapacity - minCapacity < 0)
? ? ? ?newCapacity = minCapacity;
? ?if (newCapacity - MAX_ARRAY_SIZE > 0)
? ? ? ?newCapacity = hugeCapacity(minCapacity);
? ?elementData = Arrays.copyOf(elementData, newCapacity);//擴(kuò)展空間并復(fù)制
}

由于Java GC自動(dòng)管理了內(nèi)存，這里也就不需要考慮源數(shù)組釋放的問題。

空間的問題解決后，插入過程就顯得非常簡單。

add(int index, E e)需要先對(duì)元素進(jìn)行移動(dòng)，然后完成插入操作，也就意味著該方法有著線性的時(shí)間復(fù)雜度。

addAll()

addAll()方法能夠一次添加多個(gè)元素，根據(jù)位置不同也有兩個(gè)版本，一個(gè)是在末尾添加的addAll(Collection<? extends E> c)方法，一個(gè)是從指定位置開始插入的addAll(int index, Collection<? extends E> c)方法。跟add()方法類似，在插入之前也需要進(jìn)行空間檢查，如果需要?jiǎng)t自動(dòng)擴(kuò)容；如果從指定位置插入，也會(huì)存在移動(dòng)元素的情況。addAll()的時(shí)間復(fù)雜度不僅跟插入元素的多少有關(guān)，也跟插入的位置相關(guān)。

remove()

remove()方法也有兩個(gè)版本，一個(gè)是remove(int index)刪除指定位置的元素，另一個(gè)是remove(Object o)刪除第一個(gè)滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程，需要將刪除點(diǎn)之后的元素向前移動(dòng)一個(gè)位置。需要注意的是為了讓GC起作用，必須顯式的為最后一個(gè)位置賦null值。

public E remove(int index) {
? ?rangeCheck(index);
? ?modCount++;
? ?E oldValue = elementData(index);
? ?int numMoved = size - index - 1;
? ?if (numMoved > 0)
? ? ? ?System.arraycopy(elementData, index+1, elementData, index, numMoved);
? ?elementData[--size] = null; //清除該位置的引用，讓GC起作用
? ?return oldValue;
}

關(guān)于Java GC這里需要特別說明一下，有了垃圾收集器并不意味著一定不會(huì)有內(nèi)存泄漏。對(duì)象能否被GC的依據(jù)是是否還有引用指向它，上面代碼中如果不手動(dòng)賦null值，除非對(duì)應(yīng)的位置被其他元素覆蓋，否則原來的對(duì)象就一直不會(huì)被回收。

? ? ? ? ? ? ? ? ? ? ? ? ?

總結(jié)：

1. Arraylist底層是數(shù)組，為了效率線程是不安全的。
   

2. 查詢效率高，增刪效率低。

3. 可以存儲(chǔ)重復(fù)的元素、自動(dòng)數(shù)組擴(kuò)容

感受最近的心情：哎，正好我這15發(fā)工資了，我媽媽來問我發(fā)了多少就叭叭叭的問了很多，男孩子要上進(jìn)呀，努力賺錢吧，在說我媽一直以為我還是在光電園的公司里，我都換了好幾家公司了，總是問我工資多少工資多少，這么低夠養(yǎng)活自己吧，還是要努力呀！怎么還沒轉(zhuǎn)正呢？問問你關(guān)系好的同事工資呀或者討好關(guān)心呀！這么欺騙也不是呀，還是得自己爭氣努力呀，小劉！加油！?加油！好好敲代碼，賺錢吧！

? ? ? ? ? ? ? ? ? ?? ? ??