ArrayList是我們最常用的集合類缭召，我們看下它的實(shí)現(xiàn)(基于JDK1.8)。
支持原創(chuàng)偷仿，轉(zhuǎn)載請(qǐng)注明出處鸵赫。
繼承關(guān)系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public interface List<E> extends Collection<E>
ArrayList實(shí)現(xiàn)了List接口衣屏，List又實(shí)現(xiàn)了Collection接口。
核心成員變量
private static final int DEFAULT_CAPACITY = 10 ; //默認(rèn)容量
transient Object [] elementData; //保存元素
private int size ; //當(dāng)前元素個(gè)數(shù)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //空數(shù)組
我們注意辩棒，數(shù)組默認(rèn)的大小為10狼忱。
構(gòu)造函數(shù)
public ArrayList (int initialCapacity) {
if ( initialCapacity > 0) {
this. elementData = new Object [initialCapacity ] ; //初始化指定大小的數(shù)組
} else if ( initialCapacity == 0 ) {
this. elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException( "Illegal Capacity: "+
initialCapacity );
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
} //初始化一個(gè)空數(shù)組
添加元素
public boolean add(E e) { //在最后添加元素
ensureCapacityInternal(size + 1); //確保不會(huì)越界
elementData[size++] = e; //加入數(shù)組
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //加入該元素后的元素個(gè)數(shù)如果>數(shù)組的大小，進(jìn)行擴(kuò)容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //擴(kuò)容機(jī)制
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//拷貝原始數(shù)組到一個(gè)新的數(shù)組一睁，新的數(shù)組大小為newCapacity钻弄，可能截?cái)啵蛟谖膊刻砑觧ull
elementData = Arrays.copyOf(elementData, newCapacity);
}
加入元素e后者吁，首先確保添加該元素后不會(huì)溢出窘俺，必要時(shí)會(huì)進(jìn)行擴(kuò)容，擴(kuò)容機(jī)制為int newCapacity = oldCapacity + (oldCapacity >> 1)大約為原大小的1.5倍复凳，然后將原數(shù)組復(fù)制到新的長(zhǎng)度為newCapacity的數(shù)組中瘤泪。最后將該元素e加入到數(shù)組末尾灶泵。這里我們看到根據(jù)需要指定ArrayList的大小可以防止擴(kuò)容，提高效率对途。
查找元素
public E get(int index) {
rangeCheck(index); //檢查是否越界
return elementData(
}
E elementData(int index) {
return (E) elementData[index]; //返回對(duì)應(yīng)下標(biāo)的元素
}
查找很簡(jiǎn)單赦邻，先檢查是否越界，不越界就返回對(duì)象下標(biāo)的元素掀宋。
刪除元素
public E remove(int index) {
rangeCheck(index); //越界檢查
modCount++;
E oldValue = elementData(index); //保存要?jiǎng)h除的元素
int numMoved = size - index - 1; //計(jì)算要?jiǎng)h除元素后面的元素個(gè)數(shù)
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved); //將要?jiǎng)h除元素后面的元素向前復(fù)制一個(gè)位置深纲，填補(bǔ)被刪除的元素。
elementData[--size] = null; // clear to let GC do its work
return oldValue; //返回被刪除元素
}
在數(shù)組中間刪除元素同樣會(huì)進(jìn)行拷貝劲妙，如果是常用操作可以使用LinkedList代替湃鹊。
支持原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處镣奋。
github：https://github.com/gatsbydhn
