1.定義
ArrayList是實(shí)現(xiàn)了List接口的大小可變數(shù)組，實(shí)現(xiàn)了所有可選列表操作磕潮，運(yùn)行Null在內(nèi)的所有元素翠胰。以下源碼是基于JDK 1.7.0_79 (疑問(wèn)提出：1.如何實(shí)現(xiàn)大小可變的?)
2.結(jié)構(gòu)
ArrayList的類(lèi)的結(jié)構(gòu)如下圖所示
從上圖中可以清晰的ArrayList的體系結(jié)構(gòu)，主要實(shí)現(xiàn)自脯、繼承的接口如下：
1.Collection 接口： Collection接口是所有集合類(lèi)的根節(jié)點(diǎn)之景，Collection表示一種規(guī)則，所有實(shí)現(xiàn)了Collection接口的類(lèi)遵循這種規(guī)則
2.List 接口： List是Collection的子接口膏潮，它是一個(gè)元素有序(按照插入的順序維護(hù)元素順序)锻狗、可重復(fù)、可以為null的集合
3.AbstractCollection 類(lèi)： Collection接口的骨架實(shí)現(xiàn)類(lèi)戏罢，最小化實(shí)現(xiàn)了Collection接口所需要實(shí)現(xiàn)的工作量(疑問(wèn)屋谭，為啥要這么做)
4.AbstractList 類(lèi)： List接口的骨架實(shí)現(xiàn)類(lèi)，最小化實(shí)現(xiàn)了List接口所需要實(shí)現(xiàn)的工作量
5.Cloneable 接口： 實(shí)現(xiàn)了該接口的類(lèi)可以顯示的調(diào)用Object.clone()方法龟糕，合法的對(duì)該類(lèi)實(shí)例進(jìn)行字段復(fù)制桐磁，如果沒(méi)有實(shí)現(xiàn)Cloneable接口的實(shí)例上調(diào)用Obejct.clone()方法，會(huì)拋出CloneNotSupportException異常讲岁。正常情況下我擂，實(shí)現(xiàn)了Cloneable接口的類(lèi)會(huì)以公共方法重寫(xiě)Object.clone()
6.Serializable 接口： 實(shí)現(xiàn)了該接口標(biāo)示了類(lèi)可以被序列化和反序列化，具體的 查詢序列化詳解
7.RandomAccess 接口： 實(shí)現(xiàn)了該接口的類(lèi)支持快速隨機(jī)訪問(wèn)
3.實(shí)現(xiàn)原理
下面通過(guò)源碼來(lái)分析ArrayList的實(shí)現(xiàn)原理缓艳，主要的關(guān)注的內(nèi)容如下幾點(diǎn)
3.1 底層結(jié)構(gòu)
3.1.1 基礎(chǔ)屬性
ArrayList部分源碼如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
//...省略部分代碼
}
如上代碼中為ArrayList的主要屬性
DEFAULT_CAPACITY：默認(rèn)容量校摩，即為初始值大小
EMPTY_ELEMENTDATA：共享的空數(shù)組，用于初始化空實(shí)例
elementData：ArrayList內(nèi)部結(jié)構(gòu)阶淘，是一個(gè)Object[]類(lèi)型的數(shù)組
size：數(shù)組長(zhǎng)度大小
3.1.2 構(gòu)造方法
如下為ArrayList的構(gòu)造方法
1.public ArrayList(int initialCapacity)
2.public ArrayList()
3.public ArrayList(Collection<? extends E> c){
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
1.構(gòu)造方法1衙吩，表示接受指定地容量值，初始化創(chuàng)建數(shù)組溪窒，建議在可估算數(shù)組大小時(shí),創(chuàng)建ArrayList可指定
2.構(gòu)造方法2坤塞，是默認(rèn)的構(gòu)造方法冯勉，它將創(chuàng)建一個(gè)空數(shù)組
3.構(gòu)造方法3，接收一個(gè)Collection的實(shí)體摹芙，將該Collection實(shí)體轉(zhuǎn)換為ArrayList對(duì)象
3.1.3 主干流程
1.添加指定元素代碼如下
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
可以看到實(shí)際上只有3行代碼灼狰，其流程主要如下：
1.擴(kuò)容 (這里便解釋了，在介紹時(shí)提出的問(wèn)題)：
主要源碼如下
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//最大數(shù)組容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
第一個(gè)方法的邏輯為：判斷是不是第一次添加元素浮禾，若為第一次交胚，則設(shè)置初始化大小為默認(rèn)的值10,否則使用傳入的參數(shù)
第二個(gè)方法的邏輯為：若長(zhǎng)度大于數(shù)組長(zhǎng)度，則擴(kuò)容
-
第三個(gè)方法的邏輯為:
1·擴(kuò)容的大小為3/2倍原數(shù)組長(zhǎng)度
2.若值newCapacity比傳入值minCapacity還要小盈电，則使用傳入minCapacity蝴簇，若newCapacity比設(shè)定的最大數(shù)組容量大，則使用最大整數(shù)值
3.實(shí)際擴(kuò)容挣轨，使用了Arrays.copyof(elementData, newCapacity)
(此處有兩個(gè)問(wèn)題
1.為啥擴(kuò)容是原來(lái)的3/2倍原數(shù)組的長(zhǎng)度?
2.調(diào)用Arrays.copyOf(elementData, newCapacity)方法具體做了什么操作?
)
2.賦值：將添加的值放置到size++的位置上
3.返回：返回true
2.添加指定元素到指定的位置上代碼如下
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++;
}
其流程為
1.校驗(yàn)下標(biāo)：調(diào)用rangeCheckForAdd方法進(jìn)行下標(biāo)校驗(yàn)军熏，不正確則會(huì)拋出IndexOutOfBoundsException異常
2.擴(kuò)容：詳見(jiàn)上部分中做的介紹
3.移動(dòng)數(shù)據(jù)：將數(shù)據(jù)index后面的數(shù)據(jù)，都向后移動(dòng)
4.賦值：將加入的值放置到index位置中
5.長(zhǎng)度增加：長(zhǎng)度增加
4.常用的方法
4.1 基本方法
ArrayList基本的方法如下所示
| 方法 | 說(shuō)明 | 實(shí)現(xiàn)原理 |
|---|---|---|
| boolean contains(Object o) | 返回列表中包含指定的元素 | 內(nèi)部調(diào)用indexOf()方法進(jìn)行判斷卷扮，遍歷列表進(jìn)行查詢荡澎，需要注意的是需要實(shí)現(xiàn)equals方法比較對(duì)象是否相等 |
| E get(int index) | 返回此列表中指定位置上的元素 | 內(nèi)部主要兩步，首先檢查索引晤锹，然后獲取數(shù)組對(duì)象索引的元素 |
| E set(int index, E element) | 用指定元素替代指定位置上的元素 | 需要注意的是該方法還會(huì)返回老的元素的值摩幔，內(nèi)部主要三步，首先檢查索引鞭铆，然后獲取老的元素或衡，賦值并返回 |
| E remove(int index) | 刪除指定位置上的元素 | 內(nèi)部實(shí)現(xiàn)步驟為 1.檢查索引 2.獲取老的元素 3.將index后的元素向前移動(dòng) 4.最后一個(gè)元素置為null并返回老的元素 |
| boolean remove(Object o) | 刪除列表中首次出現(xiàn)指定元素（如果存在） | 內(nèi)部實(shí)現(xiàn)為 1.判斷為NULL，若是則遍歷并刪除 2.若不是則遍歷并刪除 |
4.2 ArrayList遍歷
ArrayList遍歷方式主要有以下幾種方式
1.使用for循環(huán)的方式车遂，代碼如下
for (int i = 0; i < arrayList.size(); i++) {
System.out.println(arrayList.get(i));
}
2.使用foreach方式
for (String str : arrayList) {
System.out.println(str);
}
3.使用Iterator迭代器方式
Iterator<String> ite = arrayList.listIterator();
while (ite.hasNext()){
System.out.println(ite.next());
}
5.常見(jiàn)問(wèn)題
1.問(wèn)題描述
在使用ArrayList比較常見(jiàn)的一個(gè)問(wèn)題就是在遍歷ArrayList的時(shí)候調(diào)用remove()方法進(jìn)行元素的刪除操作,從而得到意想不到的結(jié)果封断，本人在開(kāi)發(fā)過(guò)程中也遇到過(guò)這樣的問(wèn)題，所以在這里提出了舶担，希望能夠幫助到大家坡疼。
2.實(shí)例及分析
如下代碼中，在遍歷List時(shí)衣陶，調(diào)用了remove方法柄瑰，刪除元素a
//arrayList中的值為 [a,a,c,a,a]
for (int i = 0; i < arrayList.size(); i++) {
if (arrayList.get(i) == "a") {
arrayList.remove(i);
}
}
System.out.println(arrayList);
這段代碼看似解決了刪除列表中所有的a元素，但是刪除后得出List的結(jié)果為[a, c, a]剪况，為什么這種方式?jīng)]有達(dá)到想要的效果教沾，其實(shí)仔細(xì)分析后會(huì)發(fā)現(xiàn)，在調(diào)用remove()方法時(shí)List的長(zhǎng)度會(huì)發(fā)生變化而且元素的位置會(huì)發(fā)生移動(dòng)译断，從而在遍歷時(shí)list實(shí)際上是變化的授翻，例如
當(dāng)i=0時(shí)，此時(shí)list中的元素為[a,a,c,a,a],
但當(dāng)i=1時(shí)，此時(shí)List中的元素為[a,c,a,a],元素的位置發(fā)生了移動(dòng)堪唐，從而導(dǎo)致在遍歷的過(guò)程中不能達(dá)到刪除的效果
3.解決方案
通過(guò)上述的分析可以看出隆箩，出現(xiàn)問(wèn)題的原因是元素的位置發(fā)生了移動(dòng)，從而導(dǎo)致異常的結(jié)果
方案一羔杨、逆向遍歷List刪除,代碼如下，這種做法可行主要是因?yàn)閞emove()方法刪除index處的元素時(shí)杨蛋，是將index+1到size-1索引處的元素前移兜材，而逆向遍歷可以避免元素位置的移動(dòng)
for (int i = arrayList.size()-1; i >=0 ; i--) {
if (arrayList.get(i) == "a") {
arrayList.remove(i);
}
}
System.out.println(arrayList);
方案二、使用迭代器中的remove方法逞力，迭代器具體參考Iterator詳解曙寡，主要代碼如下(這種方式比較推薦)
Iterator<String> ite = arrayList.listIterator();
while (ite.hasNext()){
if(ite.next() == "a")
ite.remove();
}
System.out.println(arrayList);
6.總結(jié)
本文主要講解ArrayList的底層實(shí)現(xiàn)、主要流程寇荧、常用方法等举庶，有寫(xiě)的不好的地方還望指正
