? ? ArrayList是經(jīng)常使用的集合類肤寝，底層基于數(shù)組實(shí)現(xiàn)戒良，訪問元素的時(shí)間復(fù)雜度是O(1),但是增刪元素的時(shí)間復(fù)雜度為O(n),這點(diǎn)和LinkedList剛好相反混槐。每次增刪會(huì)修改modCount（從父類AbstractList繼承而來）癞季。數(shù)組容量不夠時(shí)，一般來說會(huì)1.5倍擴(kuò)容呕童。不多說，下面看看數(shù)組列表的屬性和方法吧淆珊。

1.基本屬性

? ? private static final int DEFAULT_CAPACITY = 10;//默認(rèn)初始大小

? ? private static final Object[] EMPTY_ELEMENTDATA = {};//空數(shù)組夺饲，指定大小的空的ArrayList共享此對(duì)象

? ? private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空數(shù)組，默認(rèn)大小的空的ArrayList共享

? ? transient Object[] elementData; //對(duì)象數(shù)組

? ? private int size;//數(shù)組實(shí)際存儲(chǔ)對(duì)象大小施符，注意與“elementData.length”的區(qū)別

2.構(gòu)造方法

? ? ArrayList有三個(gè)構(gòu)造方法往声，分別為指定初始容量、無參構(gòu)造戳吝、傳入Collection構(gòu)造三個(gè)構(gòu)造方法浩销。不多說，其中會(huì)用到上面提到的兩個(gè)類變量EMPTY_ELEMENTDATA以及DEFAULTCAPACITY_EMPTY_ELEMENTDATA听哭。

圖1 構(gòu)造方法

3.擴(kuò)容

? ? ensureCapacity方法的調(diào)用可能會(huì)引起數(shù)組擴(kuò)容慢洋。假設(shè)第一次調(diào)用ensureCapacity方法時(shí)elementData為空，則minExpand為0陆盘，一般而言會(huì)引起擴(kuò)容普筹；之后再調(diào)用ensureCapacity方法，minExpand至少為10隘马。不多說太防，詳見代碼注釋。

圖2 ?擴(kuò)容_1

之后調(diào)用ensureExplicitCapacity()方法酸员，調(diào)用grow()方法通過Arrays.copyOf()擴(kuò)容蜒车。如果擴(kuò)容，容量至少會(huì)增加0.5倍（有這么幾種特殊情況會(huì)導(dǎo)致增加超過0.5倍或達(dá)不到0.5倍：第一次可能從0擴(kuò)大到10沸呐、整體容量不能超過Integer.MAX_VALUE限制醇王、假設(shè)原來有10個(gè)元素，現(xiàn)需要通過addAll方法添加100個(gè)元素）崭添，具體過程詳見代碼和注釋寓娩。

圖3 擴(kuò)容_2

4.清除數(shù)組多余容量trimToSize()方法，調(diào)用后size與elementData.length相等呼渣。

圖4 trimToSize()方法

? ? 5.是否包含元素[contains()]棘伴、得到指定元素序號(hào)[indexOf()]。之所以這里兩個(gè)方法放在一起講屁置，是因?yàn)閏ontains()調(diào)用indexOf()方法判斷是否包含某元素焊夸。index返回指定元素首次出現(xiàn)的序號(hào)，如果不存在則返回-1蓝角。如果元素為空則用“==”判斷阱穗，如果非空則利用“equals()”判斷饭冬。

圖6 序號(hào)&包含

? ? 6.根據(jù)size得到列表容量，列表是否為空揪阶。

圖7 容量&是否為空

? ? 7.獲取指定序號(hào)的元素昌抠。可以通過0-(size-1)獲取指定元素鲁僚。rangeCheck()會(huì)使大于等于size的序號(hào)拋出異常炊苫。底層通過數(shù)組快速定為到指定元素。

圖8 獲取元素

? ? 8.修改指定序號(hào)的元素冰沙。注意侨艾，這里并沒有修改modCount，因?yàn)榇朔椒ú]有修改數(shù)組的整體結(jié)構(gòu)拓挥。

圖9 修改指定序號(hào)的元素

? ? 9.添加元素的兩個(gè)方法唠梨。如果沒有制定序號(hào)，則在數(shù)組最后一位添加撞叽。ensureCapacityInternal()方法會(huì)使modCount++姻成。如果指定序號(hào)，則從序號(hào)到size的元素都要往后移動(dòng)一位愿棋。這就是ArrayList添加元素相對(duì)低效的原因科展。

圖10 添加元素

? ? 10.刪除元素。如果指定序號(hào)糠雨，則從序號(hào)后一位到size的元素往前移動(dòng)一位才睹；如果傳入指定對(duì)象，則先通過遍歷找到該對(duì)象第一次出現(xiàn)的序號(hào)甘邀，通過fastRemove()移動(dòng)元素琅攘。當(dāng)然，數(shù)組最后位的需要置空松邪，并且size--坞琴。

圖11 指定序號(hào)刪除

圖12 指定對(duì)象刪除

? ? 11.清空數(shù)組元素clear()方法。

圖13 清空元素

? ? 12 添加Collection所有元素到列表逗抑。如果指定沒有制定序號(hào)剧辐，則拷貝到列表尾部；如果指定序號(hào)邮府，則拷貝到序號(hào)后面荧关，原序號(hào)后元素移動(dòng) [Collection對(duì)象長(zhǎng)度] 位數(shù)。

圖14 批量添加

? ? 13.刪除區(qū)間褂傀，注意這是一個(gè)protected方法忍啤。[fromIndex，toIndex)之間的數(shù)據(jù)將會(huì)被刪除仙辟。

圖15 區(qū)段刪除

? ? 14.批量刪除batchRemove方法同波。removeAll和retainAll的底層實(shí)現(xiàn)鳄梅。“c.contains(elementData[r]) == complement”是關(guān)鍵代碼参萄，其中c是Collection參數(shù)卫枝，complement是boolean類型參數(shù)。如果complement為false讹挎，意味著原列表中不在c集合的元素將會(huì)保留（c.contains(elementData[r])為false，elementData[r]將會(huì)保留）吆玖；同理筒溃，如果complement為true，意味著原列表元素在c集合的元素將會(huì)保留（此時(shí)沾乘，c.contains(elementData[r])為true怜奖，與complement相等，elementData[r]將會(huì)保留）翅阵，詳細(xì)過程請(qǐng)看代碼注釋歪玲。

圖16 批量刪除

? ? 15轉(zhuǎn)換數(shù)組，有兩個(gè)方法toArray()和toArray(T[] a)掷匠。對(duì)于toArray()滥崩，通過Arrays.copyOf()會(huì)返回Object[]數(shù)組，雖然該數(shù)組中的元素還是T類型讹语，但是如果把Object[]強(qiáng)制轉(zhuǎn)換成T[]钙皮，則會(huì)報(bào)ClassCastException異常。

圖17 強(qiáng)轉(zhuǎn)異常

? ? 對(duì)于toArray(T[] a)顽决，如果a.length小于size短条，則會(huì)返回一個(gè)新的數(shù)組，否則返回a才菠。如果a.length大于size茸时，還會(huì)把 a[size]置空，size+1后元素不變赋访。

圖18 轉(zhuǎn)換數(shù)組_2

? ? 總結(jié)可都，相對(duì)而言數(shù)組列表還是比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，它底層通過數(shù)組實(shí)現(xiàn)进每。關(guān)于列表的equals和hashCode以及迭代相關(guān)方法后續(xù)會(huì)專門講解汹粤。