主要分析增加和刪除方法
//增加一個(gè)元素在末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//增加一個(gè)元素在指定位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
/**
*將從原來(lái)從下標(biāo)為index開(kāi)始起的數(shù)據(jù)整體向后移動(dòng)一格，將新數(shù)據(jù)放在index處
**/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//從指定位置增加一個(gè)元素集合
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)//如果新插入的位置不在原來(lái)列表的尾部，需要將原來(lái)的列表從插入位置開(kāi)始到原來(lái)結(jié)尾的所有數(shù)據(jù)整體向后移動(dòng)需要插入的元素個(gè)數(shù)個(gè)位置
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
//判斷是否需要擴(kuò)充容量
private void ensureCapacityInternal(int minCapacity) {
/**
*如果原來(lái)沒(méi)有數(shù)據(jù)，設(shè)置默認(rèn)容量與所傳入的容量的最大值為新的容量,DEFAULT_CAPACITY為10
**/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//判斷是否需要擴(kuò)充容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)//只有新的容量大于原來(lái)所分配空間才需要分配新的空間
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//新的空間為原來(lái)空間的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)//1.5倍以后如果大于默認(rèn)的最大值，就以 Integer.MAX_VALUE為最大值
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//開(kāi)辟新的存儲(chǔ)空間，原來(lái)的數(shù)據(jù)存放到新的空間，但是位置不變
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)//如果不是刪除最后一個(gè)元素，需要將從刪除位置之后的數(shù)據(jù)整體向前移動(dòng)一個(gè)位置，否則不需要移動(dòng)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //刪除位置標(biāo)記為空，讓垃圾回收器自動(dòng)清理
return oldValue;
}
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;
}
/**
* 如果不是刪除最后一個(gè)元素，需要將從刪除位置之后的數(shù)據(jù)整體向前移動(dòng)一個(gè)位置，否則不需要移動(dòng)
**/
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
}
/**
*批量刪除的邏輯，如果complement為true,表示刪除原來(lái)列表中未在傳入集合參數(shù)c中出現(xiàn)的元素
*如果complement為false,表示刪除原來(lái)列表中在傳入集合參數(shù)c中出現(xiàn)的元素
*/
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++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];//符合要求的值覆蓋原來(lái)位于[0,W]位置上的值
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)//刪除從[w，size-1]所有元素
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
//重新整理空間，讓元素的個(gè)數(shù)與分配數(shù)組空間的大小一致
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
在插入元素的時(shí)候會(huì)判斷是否需要擴(kuò)容，如果需要開(kāi)辟新的空間，那么新的空間大小為原來(lái)的空間大小的1.5倍，但是不能超過(guò)Integer.MAX_VALUE。
刪除元素的時(shí)候時(shí)候不會(huì)縮小原來(lái)分配的數(shù)組空間。只是將刪除位置的元素設(shè)置為空，雖然元素個(gè)數(shù)size會(huì)變化，但是原來(lái)分配的數(shù)組空間不變，也就是說(shuō)這個(gè)時(shí)候數(shù)組列表中不為空的元素的個(gè)數(shù)是小于或者等于所分配的空間，如果想重洗整理空間，調(diào)用trimToSize方法。
因?yàn)閿?shù)組要求元素連續(xù)存放，查詢某一個(gè)元素的時(shí)間代價(jià)為常數(shù)級(jí)（通過(guò)索引來(lái)獲?。?，但是插入和刪除的操作花費(fèi)非常昂貴，對(duì)于插入操作，需要將原來(lái)的數(shù)據(jù)從插入位置開(kāi)始整體向后挪動(dòng)一位以騰出空間給需要插入的元素存放，對(duì)于刪除元素，需要將表中的刪除點(diǎn)之后的所有數(shù)據(jù)向前移動(dòng)一個(gè)位置。
對(duì)于插入和刪除操作的最壞的情況是從位置0開(kāi)始，此時(shí)復(fù)雜度為O(n)。平均看來(lái)兩種運(yùn)算都需要移動(dòng)表的一半的元素，因此仍然需要線性時(shí)間。
因此對(duì)于插入刪除操作不是太頻繁的情況而查詢比較頻繁時(shí)，用ArrayList較好。
