ArrayList是List接口可調(diào)整數(shù)組大小的實(shí)現(xiàn)。實(shí)現(xiàn)所有可選列表操作，并允許放入包括空值在內(nèi)的所有元素。每個(gè)ArrayList都有一個(gè)容量（capacity,區(qū)別于size），表示底層數(shù)組的實(shí)際大小，容器內(nèi)存儲元素的個(gè)數(shù)不能多于當(dāng)前容量。
其中需要注意的是RandomAccess接口，這是一個(gè)標(biāo)記接口，沒有定義任何具體的內(nèi)容，該接口的意義是隨機(jī)存取數(shù)據(jù)。在該接口的注釋中有這樣一段話：
/**?for?(int?i=0,?n=list.size();?i?這說明在數(shù)據(jù)量很大的情況下，采用迭代器遍歷實(shí)現(xiàn)了該接口的集合，速度比較慢。
實(shí)現(xiàn)了RandomAccess接口的集合有：ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList,?Stack,?Vector等。
ArrayList一些重要的字段如下：
????private?static?final?int?DEFAULT_CAPACITY?=?10;
????private?static?final?Object[]?EMPTY_ELEMENTDATA?=?{};
????private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};
????transient?Object[]?elementData;?//?non-private?to?simplify?nested?class?access????private?int?size;//底層數(shù)組中實(shí)際元素個(gè)數(shù)，區(qū)別于capacity可以看到，默認(rèn)第一次插入元素時(shí)創(chuàng)建數(shù)組的大小為10。當(dāng)向容器中添加元素時(shí)，如果容量不足，容器會自動增加50%的容量。增加容量的函數(shù)grow()源碼如下：
private?void?grow(int?minCapacity)?{
????????//?overflow-conscious?code????????int?oldCapacity?=?elementData.length;
????????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);//右移一位代表增加50%????????if?(newCapacity?-?minCapacity??0)
????????????newCapacity?=?hugeCapacity(minCapacity);
????????//?minCapacity?is?usually?close?to?size,?so?this?is?a?win:????????elementData?=?Arrays.copyOf(elementData,?newCapacity);
????}
?private?static?int?hugeCapacity(int?minCapacity)?{
????????if?(minCapacity??MAX_ARRAY_SIZE)??
????????????Integer.MAX_VALUE?:
????????????MAX_ARRAY_SIZE;
????}值得注意的是，由于集合框架用到了編譯器提供的語法糖——泛型，而Java泛型的內(nèi)在實(shí)現(xiàn)是通過類型擦除和類型強(qiáng)制轉(zhuǎn)換來進(jìn)行的，其實(shí)存儲的數(shù)據(jù)類型都是Raw Type，因此集合框架的底層數(shù)組都是Object數(shù)組，可以容納任何對象。
數(shù)組復(fù)制
ArrayList的實(shí)現(xiàn)中大量地調(diào)用了Arrays.copyof()和System.arraycopy()方法。在此介紹一下這兩個(gè)方法。
System.arraycopy()方法是一個(gè)native方法，調(diào)用了系統(tǒng)的C/C++代碼，在openJDK中可以看到其源碼。該方法最終調(diào)用了C語言的memmove()函數(shù)，因此它可以保證同一個(gè)數(shù)組內(nèi)元素的正確復(fù)制和移動，比一般的復(fù)制方法的實(shí)現(xiàn)效率要高很多，很適合用來批量處理數(shù)組。Java強(qiáng)烈推薦在復(fù)制大量數(shù)組元素時(shí)使用該方法，以取得更高的效率。
Arrays.copyOf()方法有很多重載版本，但實(shí)現(xiàn)思路都是一樣的，其泛型版本源碼如下：
public?static??T[]?copyOf(T[]?original,?int?newLength)?{?return?(T[])?copyOf(original,?newLength,?original.getClass());?}
其調(diào)用了copyof()方法：
public?static??T[]?copyOf(U[]?original,?int?newLength,?Class?newType)?{??
????T[]?copy?=?((Object)newType?==?(Object)Object[].class)??
??????????(T[])?new?Object[newLength]??
????????:?(T[])?Array.newInstance(newType.getComponentType(),?newLength);??
????System.arraycopy(original,?0,?copy,?0,??
?????????????????????Math.min(original.length,?newLength));??
????return?copy;??}
該方法實(shí)際上是在其內(nèi)部創(chuàng)建了一個(gè)類型為newType、長度為newLength的新數(shù)組，調(diào)用System.arraycopy()方法，將原來數(shù)組中的元素復(fù)制到新的數(shù)組中。
非線程安全
ArrayList的實(shí)現(xiàn)是不同步的，如果多個(gè)線程同時(shí)訪問ArrayList實(shí)例，并且至少有一個(gè)線程修改list的結(jié)構(gòu)，那么它就必須在外部進(jìn)行同步。如果沒有這些對象， 這個(gè)list應(yīng)該用Collections.synchronizedList()方法進(jìn)行包裝。 最好在list的創(chuàng)建時(shí)就完成包裝，防止意外地非同步地訪問list:
List?list?=?Collections.synchronizedList(new?ArrayList(...));
除了未實(shí)現(xiàn)同步之外，ArrayList大致相當(dāng)于Vector。
size(),?isEmpty(),?get(),set()方法均能在常數(shù)時(shí)間內(nèi)完成，add()方法的時(shí)間開銷跟插入位置有關(guān)(adding n elements requires O(n) time)，addAll()方法的時(shí)間開銷跟添加元素的個(gè)數(shù)成正比。其余方法大都是線性時(shí)間。
常用API
ArrayList常用的size(),?isEmpty(),?get(),set()方法實(shí)現(xiàn)都比較簡單，讀者可自行翻閱源碼，它們均能在常數(shù)時(shí)間內(nèi)完成，性能很高，這也是數(shù)組實(shí)現(xiàn)的優(yōu)勢所在。add()方法的時(shí)間開銷跟插入位置有關(guān)(adding n elements requires O(n) time)，addAll()方法的時(shí)間開銷跟添加元素的個(gè)數(shù)成正比。其余方法大都是線性時(shí)間。
add()方法
public?boolean?add(E?e)?{
????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!????????elementData[size++]?=?e;
????????return?true;}public?void?add(int?index,?E?element)?{
????????rangeCheckForAdd(index);
????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!????????System.arraycopy(elementData,?index,?elementData,?index?+?1,
?????????????????????????size?-?index);
????????elementData[index]?=?element;
????????size++;}前者是在ArrayList尾部插入一個(gè)元素，后者是在指定位置插入元素。值得注意的是，將元素的索引賦給elementData[size]時(shí)可能會出現(xiàn)數(shù)組越界，這里的關(guān)鍵就在于ensureCapacity(size+1)的調(diào)用，這個(gè)方法的作用是確保數(shù)組的容量，它的源碼如下：
ensureCapacity()和ensureExplicitCapacity()方法：
public?void?ensureCapacity(int?minCapacity)?{
????????int?minExpand?=?(elementData?!=?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
????????????//?any?size?if?not?default?element?table??????????????0
????????????//?larger?than?default?for?default?empty?table.?It's?already????????????//?supposed?to?be?at?default?size.????????????:?DEFAULT_CAPACITY;
????????if?(minCapacity?>?minExpand)?{
????????????ensureExplicitCapacity(minCapacity);
????????}}private?void?ensureExplicitCapacity(int?minCapacity)?{
????????modCount++;
????????//?overflow-conscious?code????????if?(minCapacity?-?elementData.length?>?0)
????????????grow(minCapacity);}其中有一個(gè)重要的實(shí)例變量modCount，它是在AbstractList類中定義的，在使用迭代器遍歷的時(shí)候，用modCount來檢查列表中的元素是否發(fā)生結(jié)構(gòu)性變化（列表元素?cái)?shù)量發(fā)生改變）了，如果modCount值改變，則代表列表中元素發(fā)生了結(jié)構(gòu)性變化。
前面說過，ArrayList是非線程安全的，modCount主要在多線程環(huán)境下進(jìn)行安全檢查，防止一個(gè)線程正在迭代遍歷，另一個(gè)線程修改了這個(gè)列表的結(jié)構(gòu)。如果在使用迭代器進(jìn)行遍歷ArrayList的時(shí)候modCount值改變，則會報(bào)ConcurrentModificationException異常。
可以看出，直接在數(shù)組后面插入一個(gè)元素add(e)效率也很高，但是如果要按下標(biāo)來插入元素，則需要調(diào)用System.arraycopy()方法來移動部分受影響的元素，這會導(dǎo)致性能低下，這也是使用數(shù)組實(shí)現(xiàn)的ArrayList的劣勢。
同理，remove()方法也會改變modCount的值，效率與按下標(biāo)插入元素相似，在此不加贅述。
addAll()方法
public?boolean?addAll(Collection?c)?{
????????Object[]?a?=?c.toArray();
????????int?numNew?=?a.length;
????????ensureCapacityInternal(size?+?numNew);??//?Increments?modCount????????System.arraycopy(a,?0,?elementData,?size,?numNew);
????????size?+=?numNew;
????????return?numNew?!=?0;}public?boolean?addAll(int?index,?Collection?c)?{
????????rangeCheckForAdd(index);
????????Object[]?a?=?c.toArray();
????????int?numNew?=?a.length;
????????ensureCapacityInternal(size?+?numNew);??//?Increments?modCount
????????int?numMoved?=?size?-?index;
????????if?(numMoved?>?0)
????????????System.arraycopy(elementData,?index,?elementData,?index?+?numNew,
?????????????????????????????numMoved);
????????System.arraycopy(a,?0,?elementData,?index,?numNew);
????????size?+=?numNew;
????????return?numNew?!=?0;}addAll方法也分在末尾插入和在指定位置插入，先將入?yún)⒅械募蟘轉(zhuǎn)換成數(shù)組，根據(jù)轉(zhuǎn)換后數(shù)組的程度和ArrayList的size拓展容量，之后調(diào)用System.arraycopy()方法復(fù)制元素到相應(yīng)位置，調(diào)整size。根據(jù)返回的內(nèi)容分析，只要集合c的大小不為空，即轉(zhuǎn)換后的數(shù)組長度不為0則返回true。
容易看出，addAll()方法的時(shí)間開銷是跟添加元素的個(gè)數(shù)成正比的。
trimToSize()方法
下面來看一個(gè)簡單但是很有用的方法trimToSize()。
public?void?trimToSize()?{
????????modCount++;
????????if?(size?由于elementData的長度會被拓展，size標(biāo)記的是其中包含的元素的個(gè)數(shù)。所以會出現(xiàn)size很小但elementData.length很大的情況，將出現(xiàn)空間的浪費(fèi)。trimToSize()將返回一個(gè)新的數(shù)組給elementData，元素內(nèi)容保持不變，length和size相同，節(jié)省空間。
在實(shí)際應(yīng)用中，考慮這樣一種情形，當(dāng)某個(gè)應(yīng)用需要，一個(gè)ArrayList擴(kuò)容到比如size=10000，之后經(jīng)過一系列remove操作size=15，在后面的很長一段時(shí)間內(nèi)這個(gè)ArrayList的size一直保持在<100以內(nèi)，那么就造成了很大的空間浪費(fèi)，這時(shí)候建議顯式調(diào)用一下trimToSize()方法，以優(yōu)化一下內(nèi)存空間。 或者在一個(gè)ArrayList中的容量已經(jīng)固定，但是由于之前每次擴(kuò)容都擴(kuò)充50%，所以有一定的空間浪費(fèi)，可以調(diào)用trimToSize()消除這些空間上的浪費(fèi)。
LinkedList
LinkedList與ArrayList一樣也實(shí)現(xiàn)了List接口，LinkedList使用雙向鏈表實(shí)現(xiàn)，允許存儲元素重復(fù)，鏈表與ArrayList的數(shù)組實(shí)現(xiàn)相比，在進(jìn)行插入和刪除操作時(shí)效率更高，但查找操作效率更低，因此在實(shí)際使用中應(yīng)根據(jù)自己的程序計(jì)算需求來從二者中取舍。
與ArrayList一樣，LinkedList也是非線程安全的。
底層實(shí)現(xiàn)
java.util.LinkedList的繼承關(guān)系如下：
publicclassLinkedListextendsAbstractSequentialListimplementsList,Deque,Cloneable,java.io.Serializable
LinkedList繼承自抽象類AbstractSequenceList，其實(shí)AbstractSequenceList已經(jīng)實(shí)現(xiàn)了List接口，這里標(biāo)注出List只是更加清晰而已。AbstractSequenceList提供了List接口骨干性的實(shí)現(xiàn)以減少從而減少了實(shí)現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈表）支持的此接口所需的工作。對于隨機(jī)訪問數(shù)據(jù)（如數(shù)組），則應(yīng)該優(yōu)先使用抽象類AbstractList。
可以看到，LinkedList除了實(shí)現(xiàn)了List接口外，還實(shí)現(xiàn)了Deque接口，Deque即“Double Ended Queue”，是可以在兩端插入和移動數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)，我們熟知的棧和隊(duì)列皆可以通過實(shí)現(xiàn)Deque接口來實(shí)現(xiàn)。因此在LinkedList的實(shí)現(xiàn)中，除了提供了列表相關(guān)的方法如add()、remove()等，還提供了棧和隊(duì)列的pop()、peek()、poll()、offer()等相關(guān)方法。這些方法中有些彼此之間只是名稱的區(qū)別，內(nèi)部實(shí)現(xiàn)完全相同，以使得這些名字在特定的上下文中顯得更加的合適。
LinkedList定義的字段如下：
transientintsize=0;transientNodefirst;transientNodelast;
Size代表的是鏈表中存儲的元素個(gè)數(shù)，而first和last分別代表鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。 其中Node是LinkedList定義的靜態(tài)內(nèi)部類：
private?static?class?Node?{
????E?item;
????Node?next
????Node?prev;
????Node(Node?prev,?E?element,?Node?next)?{
????????this.item?=?element;
????????this.next?=?next;
????????this.prev?=?prev;
????}}
Node是鏈表的節(jié)點(diǎn)類，其中的三個(gè)屬性item、next、prev分別代表了節(jié)點(diǎn)的存儲屬性值、前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)。
常用API
add(e)方法
public?boolean?add(E?e)?{
????????linkLast(e);
????????return?true;}void?linkLast(E?e)?{
????final?Node?l?=?last;
????final?Node?newNode?=?new?Node<>(l,?e,?null);
????last?=?newNode;
????if?(l?==?null)
????????first?=?newNode;
????else
????????l.next?=?newNode;
????size++;
????????modCount++;}由上述代碼可見，LinkedList在表尾添加元素，只要直接修改相關(guān)節(jié)點(diǎn)的前后繼節(jié)點(diǎn)信息，而無需移動其他元素的位置，因此執(zhí)行添加操作時(shí)效率很高。此外，LinkedList也是非線程安全的
remove(o)方法
public?boolean?remove(Object?o)?{
????if?(o?==?null)?{
????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(x.item?==?null)?{
????????????????unlink(x);
????????????????return?true;
????????????}
????????}
????}?else?{
????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(o.equals(x.item))?{
????????????????unlink(x);
????????????????return?true;
????????????}
????????}
????}
????return?false;}E?unlink(Node?x)?{
????//?assert?x?!=?null;????final?E?element?=?x.item;
????final?Node?next?=?x.next;
????final?Node?prev?=?x.prev;
????if?(prev?==?null)?{
????????first?=?next;
????}?else?{
????????prev.next?=?next;
????????x.prev?=?null;
????}
????if?(next?==?null)?{
????????last?=?prev;
????}?else?{
????????next.prev?=?prev;
????????x.next?=?null;
????}
????
????x.item?=?null;
????size--;
????modCount++;
????return?element;}與add方法一樣，remove方法的底層實(shí)現(xiàn)也無需移動列表里其他元素的位置，而只需要修改被刪除節(jié)點(diǎn)及其前后節(jié)點(diǎn)的prev與next屬性即可。
get(index)方法
該方法可以返回指定位置的元素，下面來看一看代碼
public?E?get(int?index)?{
????checkElementIndex(index);
????return?node(index).item;}Node?node(int?index)?{
????//?assert?isElementIndex(index);
????if?(index?>?1))?{
????????Node?x?=?first;
????????for?(int?i?=?0;?i??x?=?last;
????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????x?=?x.prev;
????????return?x;
????}}可以看到，LinkedList要想找到index對應(yīng)位置的元素，必須要遍歷整個(gè)列表，在源碼實(shí)現(xiàn)中已經(jīng)使用了二分查找（size >> 1即是除以2）的方法來進(jìn)行優(yōu)化，但查找元素的開銷依然很大，并且與查找的位置有關(guān)。相比較ArrayList的常數(shù)級時(shí)間的消耗而言，差距很大。
clear()方法
public?void?clear()?{
????//?Clearing?all?of?the?links?between?nodes?is?"unnecessary",?but:????//?-?helps?a?generational?GC?if?the?discarded?nodes?inhabit????//?more?than?one?generation????//?-?is?sure?to?free?memory?even?if?there?is?a?reachable?Iterator????for?(Node?x?=?first;?x?!=?null;?)?{
????????Node?next?=?x.next;
????????x.item?=?null;
????????x.next?=?null;
????????x.prev?=?null;
????????x?=?next;
????}
????first?=?last?=?null;
????size?=?0;
????modCount++;}該方法并不復(fù)雜，作用只是遍歷列表，清空表中的元素和節(jié)點(diǎn)連接而已。之所以單獨(dú)拿出來講，是基于GC方面的考慮，源碼注釋中講道，該方法中將所有節(jié)點(diǎn)之間的“連接”都斷開并不是必要的，但是由于鏈表中的不同節(jié)點(diǎn)可能位于分代GC的不同年代中，如果它們互相引用會給GC帶來一些額外的麻煩，因此執(zhí)行此方法斷開節(jié)點(diǎn)間的相互引用，可以幫助分代GC在這種情況下提高性能。
Vector
作為伴隨JDK早期誕生的容器，Vector現(xiàn)在基本已經(jīng)被棄用，不過依然有一些老版本的代碼使用到它，因此也有必要做一些了解。Vector與ArrayList的實(shí)現(xiàn)基本相同，它們底層都是基于Object數(shù)組實(shí)現(xiàn)的，兩者最大的區(qū)別在于ArrayList是非線程安全的，而Vector是線程安全的。由于Vector與ArrayList的實(shí)現(xiàn)非常相近，前面對于ArrayList已經(jīng)進(jìn)行過詳細(xì)介紹了，這里很多東西就不在贅述，重點(diǎn)介紹Vector與ArrayList的不同之處。
容量擴(kuò)展
Vector與ArrayList還有一處細(xì)節(jié)上的不同，那就是Vector進(jìn)行添加操作時(shí)，如果列表容量不夠需要擴(kuò)容，每次增加的大小是原來的100%，而前面已經(jīng)講過，ArrayList一次只增加原有容量的50%。具體代碼如下：
private?void?grow(int?minCapacity)?{
????//?overflow-conscious?code????int?oldCapacity?=?elementData.length;
????int?newCapacity?=?oldCapacity?+?((capacityIncrement?>?0)??
?capacityIncrement?:?oldCapacity);
????if?(newCapacity?-?minCapacity??0)
????????newCapacity?=?hugeCapacity(minCapacity);
????elementData?=?Arrays.copyOf(elementData,?newCapacity);}線程安全
Vector類內(nèi)部的大部分方法與ArrayList均相同，區(qū)別僅在于加上了synchronized關(guān)鍵字，比如：
public?synchronized?void?trimToSize()?{
????modCount++;
????int?oldCapacity?=?elementData.length;
????if?(elementCount?這也保證了同一時(shí)刻只有一個(gè)線程能夠?qū)慥ector，避免多線程同時(shí)寫而引起的不一致性，但實(shí)現(xiàn)同步需要很高的花費(fèi)，因此，訪問Vector比訪問ArrayList要慢。
前面說過，由于性能和一些設(shè)計(jì)問題，Vector現(xiàn)在基本已被棄用，當(dāng)涉及到線程安全時(shí)，可以如前文介紹ArrayList時(shí)所說的，對ArrayList進(jìn)行簡單包裝，即可實(shí)現(xiàn)同步。
Stack類
Vector還有一個(gè)子類叫Stack，其實(shí)現(xiàn)了棧的基本操作。這也是在JDK早期出現(xiàn)的容器，很多設(shè)計(jì)不夠規(guī)范，現(xiàn)在已經(jīng)過時(shí)，使用Queue接口的相關(guān)實(shí)現(xiàn)可以完全取代它。
總結(jié)
重慶分公司
重慶分公司
