概要
- 類繼承關(guān)系
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList<E>
- 定義
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
實(shí)現(xiàn)
- 創(chuàng)建
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
}
}
由代碼可知茸习，ArrayList采用數(shù)組方式存放對(duì)象硼讽。無(wú)參構(gòu)造器創(chuàng)建一個(gè)空Object數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
- 插入：add(E)
add方法其實(shí)就是給數(shù)組中某元素賦值為傳入的對(duì)象俯渤，但add時(shí)有個(gè)明顯的問(wèn)題是氧枣，數(shù)組滿了怎么辦？我們接著往下看埋市。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal函數(shù)的作用是保證數(shù)組大小是夠用的掘宪。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
參數(shù)傳入數(shù)組的size + 1搏恤， 如果數(shù)組為空數(shù)組，則將minCapacity設(shè)為10或者minCapacity中的大值
private static final int DEFAULT_CAPACITY = 10;
函數(shù)ensureExplicitCapacity用來(lái)產(chǎn)生明確的容量, 如果minCapacity大于數(shù)組大小舶赔，則進(jìn)行擴(kuò)容扫倡。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
擴(kuò)容代碼如下：
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
首先產(chǎn)生新的數(shù)組大小為原來(lái)的1.5倍，若新的容量仍小于minCapacity竟纳，則minCapacity為新的容量撵溃，得出新的容量值后，調(diào)用Arrays.copyOf來(lái)生成新的數(shù)組對(duì)象锥累，如想調(diào)整容量的生長(zhǎng)策略缘挑，可繼承ArrayList, 并覆寫(xiě)ensureCapacity方法。
在Collection中增加對(duì)象時(shí)桶略，ArrayList還提供add(int, E)這樣的方法语淘，允許將元素直接插入到int位置。它要將當(dāng)前數(shù)組的對(duì)象進(jìn)行一次復(fù)制际歼，即將目前index及其后的數(shù)據(jù)都往后挪一位惶翻，該方式要多一次復(fù)制數(shù)組的代價(jià)。
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++;
}
- 刪除：remove(E)
先上代碼：
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;
}
如果要?jiǎng)h除的對(duì)象為null, 循環(huán)遍歷整個(gè)數(shù)組鹅心，找到為null值的元素吕粗，調(diào)用fastRemove刪除相應(yīng)位置的對(duì)象。
private void fastRemove(int index) {
modCount++;
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
}
又代碼可知旭愧，fastRemove是一次數(shù)組的復(fù)制颅筋，將index后的對(duì)象統(tǒng)一向前移動(dòng)一位宙暇，將最后一位設(shè)為null, 釋放此對(duì)象的引用。
若對(duì)象非null, 則通過(guò)equals來(lái)進(jìn)行比較垃沦，同樣通過(guò)fastRemove來(lái)刪除元素客给。
- 獲取單個(gè)對(duì)象：get(int)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
先做數(shù)組范圍檢查，在返回對(duì)象肢簿。
- 遍歷對(duì)象：iterator
public Iterator<E> iterator() { return new Itr();}
每次調(diào)用iterator方法時(shí)靶剑，都會(huì)new一個(gè)Itr的實(shí)例。
當(dāng)調(diào)用此實(shí)例的hasNext方法時(shí)池充，比較當(dāng)前指向的數(shù)組的位置是否和數(shù)組中已有元素大小相等桩引，如相等返回false，否則返回true收夸。
坑匠、、卧惜、
public boolean hasNext() {
return cursor != size; // cursor標(biāo)識(shí)下一個(gè)返回元素的位置
}
厘灼、、咽瓷、
當(dāng)調(diào)用實(shí)例的next方法時(shí)设凹，首先比較在創(chuàng)建此Iterator時(shí)獲取的modCount與當(dāng)前的modCount，如果不等茅姜，則說(shuō)明在獲取next元素時(shí)闪朱，發(fā)生了對(duì)集合大小產(chǎn)生影響（新增、刪除）的動(dòng)作钻洒。當(dāng)發(fā)生這種情況時(shí)奋姿，則拋出ConcurrentModificationException。
- 判斷對(duì)象時(shí)候存在：contains(E)
public boolean contains(Object o) { return indexOf(o) >= 0;}
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;
}
如果E為null,則直接判斷已有元素是否為null, 否則通過(guò)判斷E.equals和元素是否相等素标。
- transient
transient Object[] elementData; // non-private to simplify nested class access
聲明為transient后称诗，這個(gè)字段不會(huì)被序列化。
- SuppressWarnings
@SuppressWarnings("unchecked")
告訴編譯器糯钙，對(duì)特定類型的warning保持沉默粪狼。
注：
- ArrayList基于數(shù)組實(shí)現(xiàn)，無(wú)容量的限制任岸。
- ArrayList插入元素時(shí)可能要擴(kuò)容再榄，刪除時(shí)并不會(huì)減小數(shù)組的容量。
- 若希望縮小數(shù)組容量享潜，可以調(diào)用ArrayList的trimToSize()
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
- ArrayList非線程安全困鸥。
