上一章分析了AbstractList抽樣類，這一章我們將全面分析最常用的集合ArrayList。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
ArrayList繼承自AbstractList類，實現(xiàn)了List接口，RandomAccess這個可隨機訪問的標記接口，Cloneable可克隆標記接口，和Serializable可序列化標記接口。
一.成員屬性
// 默認ArrayList集合的大小。
private static final int DEFAULT_CAPACITY = 10;
// 如果是空集合，那么都指向這個空數(shù)組常量，減少創(chuàng)建多個空數(shù)組變量。
private static final Object[] EMPTY_ELEMENTDATA = {};
// 如果是默認集合，先用這個空數(shù)組常量代替，當添加元素時，再創(chuàng)建DEFAULT_CAPACITY長度的數(shù)組
// 作用就是減少內(nèi)存使用。
// 例如我們new 多個ArrayList集合時，只要我們還沒有添加元素，它們內(nèi)部elementData都指向這個空數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 采用Object[]數(shù)組來存儲集合中的元素
transient Object[] elementData;
// 集合中元素的數(shù)量
private int size;
它有兩個重要屬性，elementData Object數(shù)組用來存儲集合中元素，size表示集合中元素的數(shù)量。還有一個重要屬性就是繼承自AbstractList的modCount屬性。
二. 構(gòu)造函數(shù)
2.1 默認構(gòu)造函數(shù)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
注意這里和老版本不一樣，當我們調(diào)用ArrayList空參構(gòu)造時，它僅僅只是將空數(shù)組賦值給elementData，而不是創(chuàng)建一個DEFAULT_CAPACITY大小的新數(shù)組。當我們真正調(diào)用添加元素方法時，才會創(chuàng)建新數(shù)組。延遲創(chuàng)建默認大小的數(shù)組。
2.2 設置數(shù)組初始長度的構(gòu)造函數(shù)
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
根據(jù)initialCapacity的值創(chuàng)建對應大小的Object數(shù)組，如果小于0就拋出異常。
注意這里沒有使用延遲創(chuàng)建數(shù)組的方法，因為這里數(shù)組初始大小是由用戶自定義的。當然也可以用一個成員變量記錄，然后延遲創(chuàng)建，只不過它這里沒有這么做。
2.3 通過Collection實例構(gòu)建集合
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray 返回的可能不是Object[]數(shù)組，所以進行處理一下
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果c是一個空集合，那么這里就設置成EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
}
}
通過toArray方法，將集合c轉(zhuǎn)成數(shù)組，如果數(shù)組長度為0，那么就將 this.elementData設置成空數(shù)組常量EMPTY_ELEMENTDATA，而不是集合c轉(zhuǎn)成那個空數(shù)組，就可以讓這個新創(chuàng)建的空數(shù)組內(nèi)存釋放了。
還要注意一點就是，c.toArray()方法返回的可能并不是Object[]數(shù)組，所以這里做了判斷。
三. 重要方法
3.1 數(shù)組擴容方法
我們知道使用數(shù)組中存放元素的大小是固定的，而ArrayList集合好像是無限大小的，但是ArrayList集合又是通過數(shù)組來實現(xiàn)的，所以它一定幫我們做了數(shù)組擴容。
public void ensureCapacity(int minCapacity) {
// 如果是默認構(gòu)造函數(shù)創(chuàng)建的ArrayList集合，那么它的最小數(shù)組長度都是DEFAULT_CAPACITY。
// 如果不是的話，那么它最小數(shù)組長度就是0
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
// 當minCapacity > minExpand，那么就有可能要對數(shù)組進行擴容。
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
這個是供給外部調(diào)用的方法，來確保數(shù)組的長度大于這個minCapacity值。
private void ensureCapacityInternal(int minCapacity) {
// 如果相等，表示通過默認構(gòu)造函數(shù)創(chuàng)建的ArrayList集合，而且還沒有創(chuàng)建新數(shù)組。
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 取minCapacity和DEFAULT_CAPACITY中較大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
這是供給類內(nèi)部使用的方法，在集合的添加元素方法中都會調(diào)用這個方法，確保數(shù)組長度不小于minCapacity值。
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 表示集合修改了
// 當數(shù)組長度小于minCapacity時，就要進行擴容了
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
會調(diào)用grow方法，進行數(shù)組擴容操作。
private void grow(int minCapacity) {
// 獲取老數(shù)組長度
int oldCapacity = elementData.length;
// 先進行1.5倍擴容， oldCapacity >> 1 與oldCapacity/2 效果一樣，但是采用右移操作，速度比除法快得多。
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果進行擴容之后，還是小于minCapacity值，那么就直接用minCapacity值當成數(shù)組長度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 處理newCapacity值大于MAX_ARRAY_SIZE情況，集合容量也是有上限的。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 使用Arrays.copyOf方法，將老數(shù)組的元素拷貝到newCapacity長度的新數(shù)組中，并返回這個新數(shù)組。
elementData = Arrays.copyOf(elementData, newCapacity);
}
進行數(shù)組擴容，先將新數(shù)組長度擴充至老數(shù)組1.5倍，如果還是小于minCapacity，那么就直接使用minCapacity作為新數(shù)組長度，然后再處理超出最大數(shù)組長度問題。最后使用Arrays.copyOf方法，將老數(shù)組元素拷貝到新數(shù)組中。
3.2 添加元素
public boolean add(E e) {
// 確保數(shù)組容量
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
在集合末尾添加元素，先確保數(shù)組容量，然后再在集合末尾添加元素，最后將集合數(shù)量size加一。
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++;
}
在集合指定索引位置添加元素。先檢查索引位置是否越界，確保數(shù)組容量滿足要求，然后調(diào)用System.arraycopy方法，將從索引位置開始的元素全部右移一位，再將索引位置設置成新元素element，最后集合數(shù)量size自增。
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
- 將集合c轉(zhuǎn)成數(shù)組a，并得到數(shù)組長度numNew
- 確保集合數(shù)組長度不小于size + numNew
- 通過System.arraycopy方法，將數(shù)組a的全部元素拷貝到數(shù)組elementData的size位置之后，就是集合末尾。
- 將集合數(shù)量size加上numNew大小。
public boolean addAll(int index, Collection<? extends E> 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;
}
- 檢查索引位置是否越界。
- 將集合c轉(zhuǎn)成數(shù)組a，并得到數(shù)組長度numNew。
- 確保集合數(shù)組長度不小于size + numNew。
- numMoved 表示原數(shù)組要移動元素的數(shù)量
- 將原數(shù)組index之后的元素(包括index)，都向后移動numNew個位置
我們要向一個數(shù)組從index位置插入numNew個元素，那么這個數(shù)組從index位置開始到結(jié)尾的都要移動numNew個位置，一共移動size - index個元素。
- 將數(shù)組a中全部元素插入到elementData數(shù)組index之后位置(包括index)。
- 將集合數(shù)量size加上numNew大小。
3.3 刪除元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 清理引用，讓垃圾回收器可以回收無用的對象內(nèi)存
elementData[--size] = null;
}
遍歷數(shù)組，找到與o相等的索引位置，然后調(diào)用fastRemove方法刪除這個索引位置的元素。
要刪除數(shù)組index位置元素，就是將index之后的元素都向前移動一位，即使用System.arraycopy(elementData, index+1, elementData, index, numMoved)方法完成。
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);
// 清理引用，讓垃圾回收器可以回收無用的對象內(nèi)存
elementData[--size] = null;
return oldValue;
}
先通過elementData(index)方法得到index位置的元素，便于返回這個被刪除的元素。然后通過System.arraycopy方法將數(shù)組index位置之后的元素都向前移動一位，最后將數(shù)組最后位置的元素置位null，并將集合容量size自減。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
移除與集合c相同元素，和只保留與集合c相同元素都調(diào)用batchRemove方法。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// 如果complement為true，表示本集合只保留集合c中包含的元素
// 如果complement為false，就刪除集合c中包含的元素，所以集合c中不包含的元素才保留到本集合中
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 發(fā)生異常之后的補救處理
// 如果r不等于size，表示數(shù)組沒有遍歷完成，將數(shù)組r位置之后的元素拷貝到數(shù)組w位置之后。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
// w就表示現(xiàn)在集合的數(shù)量
w += size - r;
}
// 如果不相等，說明本集合刪除元素了，就要進行一些處理
if (w != size) {
// 將w位置之后的元素置位null，方便垃圾回收器回收。
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
// 將w的值賦值給size。
size = w;
modified = true;
}
}
return modified;
}
還記得我們在AbstractCollection類中是怎么操作的么?是調(diào)用迭代器的remove方法，但是在這里就不適用，因為數(shù)組刪除一個元素會導致數(shù)組的移動，很浪費時間。這里用了很巧妙的方法。
想一想我們平常怎么刪除數(shù)組中特定元素的。
- 第一種是新建一個長度一樣的數(shù)組，然后遍歷原數(shù)組，將滿足條件的元素才加入到新數(shù)組中，這樣就可以刪除不滿足條件的元素了。這種方式效率很快，但是需要多余的內(nèi)存。
- 第二種是反向遍歷數(shù)組，如果發(fā)現(xiàn)不滿足條件的元素，將這個位置之后的元素前移一位，這樣就覆蓋不滿足條件的元素了。這種方式不需要多余內(nèi)存，但是需要進行數(shù)組的移動，耗費時間。
- 第三種就采用非常巧妙的方法了，這里用到兩個位置索引r和w，用r索引來遍歷整個數(shù)組，用w表示保留下來元素的索引。所以遍歷數(shù)組，如果滿足條件，就將這個元素elementData[r]存放到elementData[w] w位置，并將w數(shù)量加一。因為r一定大于或者等于w，所以不存在前面位置的元素覆蓋后面位置的元素。這種方式速度快，而且不用多余內(nèi)存。
public void clear() {
modCount++;
// 清理引用，讓垃圾回收器可以回收無用的對象內(nèi)存
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
清除集合中元素。
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// 清理引用，讓垃圾回收器可以回收無用的對象內(nèi)存
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
刪除集合中fromIndex位置到toIndex位置的元素(包括fromIndex，但是不包括toIndex)。通過 System.arraycopy方法將toIndex(包括toIndex位置)之后的元素全部向前移動到fromIndex位置，所以toIndex位置的元素還是保留在集合中。然后將無效位置的元素全部置位null，方便垃圾回收器回收。
3.4 替換元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
就是將數(shù)組對應位置替換成新元素element
3.5 查詢方法
E elementData(int index) {
return (E) elementData[index];
}
返回對應索引位置元素，并強轉(zhuǎn)成E類型。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
通過elementData方法獲取元素。
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;
}
正向遍歷數(shù)組，查找與o相同元素，如果查找到就返回對應下標位置，如果沒有查到就返回-1。
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
反向遍歷數(shù)組，查找與o相同元素，如果查找到就返回對應下標位置，如果沒有查到就返回-1。
public Iterator<E> iterator() {
return new Itr();
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
與AbstractList一樣，ArrayList提供兩個迭代器，都是ArrayList內(nèi)部類。
四. ArrayList的內(nèi)部類Itr
4.1 成員屬性
// 光標索引位置，0表示在集合開始位置(因為這是一個list集合，所以可以用索引表示開始位置)
int cursor;
// 表示讀取到的當前元素位置
int lastRet = -1;
// 用來判斷原集合是否被修改，拋出ConcurrentModificationException異常。
int expectedModCount = modCount;
4.2 遍歷集合
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
如果集合中modCount的值與迭代器中expectedModCount的值不相等，就說明在迭代器期間集合被修改了，那么遍歷的數(shù)據(jù)已經(jīng)失效，就拋出異常。
public boolean hasNext() {
return cursor != size;
}
判斷集合中是否還有未讀取的元素，即cursor光標已經(jīng)移動到最后了。
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
- 先檢查集合有沒有沒被修改。
- 將cursor光標位置賦值給變量i
- 然后判斷i位置是否有效
- 將cursor光標位置加1，指向下一個元素。
- 將i賦值給lastRet，并返回i位置的元素，表示當前遍歷到的元素。
4.3 刪除元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
- 如果lastRet < 0表示當前位置元素無效，不能進行刪除操作，拋出異常。
- 檢查集合有沒有沒被修改。
- 調(diào)用ArrayList集合remove(lastRet)方法刪除集合當前元素。
- 將當前元素位置索引lastRet賦值給cursor，然后將lastRet置位-1，表示當前位置已失效。
注意這里的處理方法與AbstractList不一樣，但是實現(xiàn)的效果是一樣的。都是將cursor重置成當前位置坐標。
- 重新設置expectedModCount的值
五. ArrayList的內(nèi)部類 ListItr
它繼承自Itr類，實現(xiàn)了ListIterator接口。它實現(xiàn)了對List集合的反向遍歷，以及添加和替換集合中元素的方法。
5.1 構(gòu)造函數(shù)
ListItr(int index) {
super();
cursor = index;
}
表示從index - 1位置開始，反向遍歷集合元素。
5.2 反向遍歷集合
public boolean hasPrevious() {
return cursor != 0;
}
判斷集合中是否還有未讀取的元素。當cursor==0，表示已經(jīng)讀取到第一元素了，前面以及沒有元素了。
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
- 先檢查集合有沒有沒被修改。
- 將cursor-1賦值給變量i
- 然后判斷i位置是否有效
- 將i的值賦值給cursor和lastRet;
- 并返回i位置的元素，表示當前遍歷到的元素。
5.3 返回索引位置。
// 如果是正向遍歷集合，nextIndex返回值表示集合中下一個元素的索引位置。
// 如果是反向遍歷集合，nextIndex返回值表示集合中當前元素的索引位置。
public int nextIndex() {
return cursor;
}
// 如果是正向遍歷集合，previousIndex返回值表示集合中當前元素的索引位置。
// 如果是反向遍歷集合，previousIndex返回值表示集合中前一個元素的索引位置。
public int previousIndex() {
return cursor-1;
}
5.4 替換當前元素
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
- lastRet < 0 表示當前位置無效，不能更換元素，拋出異常。
- checkForComodification方法檢查集合有沒有沒被修改。
- 調(diào)用List集合的set(lastRet, e)方法，替換當前元素。
- 因為修改了集合，那么重新賦值expectedModCount = modCount
5.5 添加元素
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
- 調(diào)用checkForComodification方法檢查集合有沒有沒被修改。
- 調(diào)用List的add(i, e)方法，在cursor光標位置插入元素。
那么就有兩種情況了，正向遍歷的時候，就是在當前元素下一個索引位置插入，而反向遍歷時，就是在當前元素索引位置插入。
- lastRet = -1 設置當前元素索引位置無效。
- cursor = i + 1 將光標位置加1
這里就有問題了，它只能保證正向遍歷的時候，不會遍歷到剛剛插入的元素。但是反向遍歷的時候，因為將cursor光標位置加一，那么下次獲取前一個元素正好是剛剛添加的元素。
- 因為修改了集合，那么重新賦值expectedModCount = modCount。
總結(jié)
ArrayList內(nèi)部是通過數(shù)組儲存元素的，數(shù)組的長度是固定，所以集合中元素數(shù)量超出數(shù)組長度時，要對數(shù)組進行擴容。
- 一般先將長度擴大到原數(shù)組長度的1.5倍。
- 與集合元素數(shù)量進行比較，如果還是小于，就直接將元素數(shù)量當成數(shù)組長度。
- 考慮最大上限問題。
- 最后利用 Arrays.copyOf(elementData, newCapacity)，創(chuàng)建一個新數(shù)組，將原數(shù)組元素都拷貝到新數(shù)組中，返回新數(shù)組賦值給elementData
數(shù)組擴容操作一般都是在添加元素中判斷的，因為只有添加元素，才能超出原數(shù)組儲存大小的情況。
添加元素
我們就以最復雜的一種情況為例，在索引index位置添加一個集合c。
- 檢查索引位置是否越界。
- 通過集合c的toArray方法，將集合轉(zhuǎn)成數(shù)組。
- 確保集合數(shù)組長度不小于本集合元素數(shù)量與集合c元素數(shù)量之和。(調(diào)用ensureCapacityInternal方法)
- 先通過System.arraycopy方法，將index位置之后的元素，全部右移集合c元素數(shù)量的位數(shù)。
這樣就將index 到index+ numNew位置全部空出來，正好可以存放集合c全部元素了。
- 再使用System.arraycopy方法，將集合c中元素拷貝到本集合數(shù)組index 到index+ numNew位置。
- 最后將集合數(shù)量size加上numNew大小。
刪除元素
從源碼中看，ArrayList刪除元素分兩種情況。
- 刪除某一位置index的單個元素。就是通過System.arraycopy來實現(xiàn)index之后元素全部左移一位，實現(xiàn)了刪除效果。
記著將無效位置元素置位null，方便垃圾回收器回收內(nèi)存。
- 刪除多個元素。這里用了很巧妙的方法，具體請看文章中關(guān)于batchRemove(Collection<?> c, boolean complement)方法的詳解。
查詢方法
主要就是遍歷數(shù)組，很簡單。
