前話：本次解析基于JDK1.8.0蚁阳，SDK26。
一鸽照、數(shù)據(jù)結(jié)構(gòu)
ArrayList 是Java提供的一個(gè)存儲數(shù)據(jù)的工具類螺捐，其內(nèi)部使用 一個(gè)Object[] （數(shù)組）來存儲我們的數(shù)據(jù)。后續(xù)的添加矮燎、刪除定血、查詢等操作實(shí)際上都是對數(shù)組進(jìn)行操作。
transient Object[]elementData; //transient是序列化和反序列化的知識點(diǎn)
二诞外、構(gòu)造方法
使用ArrayList的前提就是定義ArrayList對象澜沟，先來看一下ArrayList類中的幾個(gè)重要的成員變量：
//實(shí)際存儲數(shù)據(jù)的數(shù)組
transient Object[] elementData;
//數(shù)組中實(shí)際數(shù)據(jù)的個(gè)數(shù)，注意并不是數(shù)組的長度（這塊要特別注意峡谊，后邊會用到）茫虽。默認(rèn)為0
private int size;
//數(shù)組的默認(rèn)容量或長度
private static final int DEFAULT_CAPACITY = 10;
//靜態(tài)的空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//靜態(tài)的默認(rèn)的空數(shù)組，在后邊的構(gòu)造函數(shù)會看到和EMPTY_ELEMENTDATA的不同
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1既们、首先分析最簡單的一種定義方式：
ArrayList list = new ArrayList();
其內(nèi)部實(shí)現(xiàn)：
public ArrayList() {
//直接把默認(rèn)的靜態(tài)的空數(shù)組賦值給elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2濒析、帶有初始化容量的構(gòu)造方法：
ArrayList list = new ArrayList(20);
其內(nèi)部實(shí)現(xiàn)：
//指定創(chuàng)建一個(gè)長度為initialCapacity的數(shù)組
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//要求的長度>0，則直接創(chuàng)建一個(gè)該長度的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//賦值為空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果長度小于零啥纸，直接拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
三号杏、add方法
對add方法的總結(jié)就是：當(dāng)向ArrayList中添加一個(gè)元素時(shí)，先判斷當(dāng)前數(shù)組中是否還有剩余空間脾拆，如果有剩余空間則直接將該元素添加至數(shù)組中元素的末尾馒索，如果沒有剩余空間，先將數(shù)組擴(kuò)容（擴(kuò)容的算法簡單說就是將當(dāng)前的數(shù)組容量擴(kuò)大1.5倍）名船，再將元素添加至數(shù)組中元素的末尾绰上。
public boolean add(E e) {
//每次add一個(gè)元素之前，先判斷size+1之后數(shù)組是否還有空余空間,
//如果沒有剩余空間渠驼，對elementData進(jìn)行擴(kuò)容蜈块，如果有剩余空間則直接進(jìn)行下一步。
// 注意：size并不是數(shù)組的長度迷扇，而是數(shù)組中實(shí)際存儲對象的長度
ensureCapacityInternal(size + 1); // Increments modCount!!
//注意size++百揭，每次添加一個(gè)素，size增加1.
elementData[size++] = e;
return true;
}
來重點(diǎn)看下ensureCapacityInternal方法：
private void ensureCapacityInternal(int minCapacity) {
// elementData就是實(shí)際存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)：Object[]
// 如果當(dāng)前數(shù)組為空數(shù)組
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY 為 10蜓席，是默認(rèn)數(shù)組的長度
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//繼續(xù)調(diào)用方法
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//等價(jià)于：minCapacity > elementData.length
if (minCapacity - elementData.length > 0)
// 第一次add的時(shí)候器一，elementData.length=0，數(shù)組為空數(shù)組厨内，所以肯定要把當(dāng)前數(shù)組擴(kuò)容
// 如果是第N次add祈秕，此時(shí)minCapacity > elementData.length,也就是數(shù)組需要更大的空間
//所以也需要擴(kuò)容渺贤。
grow(minCapacity);
}
private void grow(int minCapacity) {
//當(dāng)前數(shù)組的長度(擴(kuò)容之前的長度)
int oldCapacity = elementData.length;
//oldCapacity >> 1：位運(yùn)算符，相當(dāng)于oldCapacity/2,
//新的容量等于：原來的容量 + 原來的容量的一半
//所以每次擴(kuò)容都是將數(shù)組的長度擴(kuò)大為原來的1.5倍请毛。
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新的擴(kuò)大1.5倍后志鞍，數(shù)組的空間仍然不夠
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果需要的空間比 MAX_ARRAY_SIZE 還要大，
if (newCapacity - MAX_ARRAY_SIZE > 0)
//hugeCapacity:申請最大的空間
newCapacity = hugeCapacity(minCapacity);
//最后根據(jù)需要的空間和原來的數(shù)組中的數(shù)據(jù)方仿，將elementData重新賦值為擁有更大空間的數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
三固棚、get方法
根據(jù)元素的坐標(biāo)獲取元素，先判斷index是否合法仙蚜，如果合法直接返回元素此洲。
public E get(int index) {
if (index >= size)
//size是當(dāng)前數(shù)組中元素的個(gè)數(shù)，并不是數(shù)組的長度委粉，如果查詢的index超過size黍翎，拋異常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//直接返回index對應(yīng)的元素
return (E) elementData[index];
}
四、set方法
set(int index, E element）方法是將原數(shù)組中的下標(biāo)為index的元素替換為新的數(shù)據(jù)艳丛。
public E set(int index, E element) {
if (index >= size)
//老規(guī)矩匣掸，還是先判斷size的長度
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//將老的元素替換為新的元素，并把老元素返回
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
五氮双、remove方法
public E remove(int index) {
if (index >= size)
//老規(guī)矩碰酝，先判斷size合法
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
//獲取要刪除的元素
E oldValue = (E) elementData[index];
// 假設(shè)一個(gè)數(shù)組有3個(gè)元素，現(xiàn)在刪除第二個(gè)元素（下標(biāo)為1）戴差，numMoved= 3-1-1=1
//numMoved表示在數(shù)組中刪除一個(gè)元素后送爸，需要將該元素后邊的元素全部向前挪一位，那么一共要挪動的元素的個(gè)數(shù)即為numMoved
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
//最后將刪除的元素返回
return oldValue;
}
六暖释、indexOf 方法
indexOf 可以接受為Null的數(shù)據(jù)袭厂，如果數(shù)據(jù)為null，則返回整個(gè)數(shù)組中第一個(gè)為null的元素的下標(biāo)球匕。如果不為null纹磺，則遍歷整個(gè)數(shù)組中的元素，找到相等的元素并返回下標(biāo)亮曹。
需要注意的是：indexOf(E e) 方法的平均時(shí)間復(fù)雜度為O(n)橄杨，因?yàn)樗鼉?nèi)部是一個(gè)循環(huán)，所以在使用indexOf方法的時(shí)候照卦，盡量不要再一個(gè)for循環(huán)中再使用indexOf式矫，因?yàn)檫@樣的時(shí)間復(fù)雜度為O(n*n)，在內(nèi)存充足的情況下可以考慮使用“空間換時(shí)間”的方法役耕，使用HashSet或者HashMap代替ArrayList采转。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
七、size()方法
public int size() {
//前邊已經(jīng)提到多次瞬痘，ArrayList的size方法返回的是數(shù)組中元素的個(gè)數(shù)故慈，不是整個(gè)數(shù)組的長度锄列。
return size;
}
總結(jié)
其實(shí)ArrayList內(nèi)部還有幾個(gè)操作方法，但是總體的思路都是針對于數(shù)組進(jìn)行操作惯悠，另外，在寫代碼的時(shí)候一定要注意indexOf的使用竣况，這句代碼的時(shí)間復(fù)雜度為O(n)克婶。
