- elementData:就是實際存儲元素的數(shù)組,被transient,表明不參與序列化喇辽，意味著elementData里的數(shù)據(jù)僅存在調(diào)用者的內(nèi)存中
- EMPTY_ELEMENT空數(shù)組
-
DEFAULTCAPACITY_EMPTY_ELEMENT: 不同于EMPTY_ELEMENT岛琼，這個空的Object[]有啥用？
（為什么要兩個空數(shù)組龙助？3號空數(shù)組用法如下，那么二號呢欺殿？其實二號要解決的是當(dāng)我想創(chuàng)建一個空集合時拔莱，即調(diào)用new ArrayList(0),在隨后調(diào)用add方法時，不會被自動擴容成大小為10匿又，這就是二者區(qū)別-defaultCapacity方灾。)
無參構(gòu)造函數(shù)當(dāng)調(diào)用無參構(gòu)造函數(shù)時，將它賦給elementData碌更，這樣做感覺好像沒多大用裕偿？其實它就像一個標(biāo)記，什么時候會用到它呢针贬？當(dāng)?shù)谝粋€元素被添加的時候
size： 是實際元素個數(shù)
---DEFAULT_CAPACITY = 10击费；也就是說當(dāng)你new ArrayList()調(diào)用add(E e)或是其它add方法后拢蛋，會根據(jù)需要創(chuàng)建一個Object[minCapacity]初始數(shù)組-------(感覺寫了半天細(xì)枝末節(jié)的東西)
---modeCount是用作Fail-Fast機制
---grow()執(zhí)行數(shù)組擴容操作桦他，利用Arrays.copyOf(),繼續(xù)追蹤發(fā)現(xiàn)是調(diào)用了System.arrayCopy(),創(chuàng)建了一個擴容后大小的新數(shù)組copy[]，返回copy
ArrayList還有一類構(gòu)造函數(shù)：ArrayList(Collection<? extends E> c),它什么原理呢谆棱？ Collection接口有個toArray()快压，舉例如具體實現(xiàn)類ArrayList的toArray()里調(diào)用Arrays.copyOf()，如上所述它返還一個copy[]垃瞧，而該構(gòu)造函數(shù)里就利用了這個來將c轉(zhuǎn)化為數(shù)組賦給elementData蔫劣。其實很多地方都用到了Arrays.copy(),比如trimToSize()..
ADD（）：
ArrayList其實是一個動態(tài)變化的數(shù)組，我們來看它在添加刪除元素時的變化：
從add入手：add(E e); add(int index; E elementi); add(Collention<? extends E> c); add(int index, Collection<? extends E> c)四種方法个从。
- add(E e):首先會調(diào)用ensureCapacityInternal(size+1),該方法又會調(diào)用ensureEcplicitCapacity(),在該方法里如果size+1>elementData.length脉幢，則調(diào)用growth()方法進(jìn)行擴容歪沃，邏輯如下
一般情況下擴容為原來的1.5倍，這里又用到 了Arrays.copyOf()
- add(int index, E e)
顯而易見嫌松，先判斷index是否越界沪曙，在進(jìn)行擴容判斷，之后調(diào)用System.arraycopy()將原數(shù)組index及之后的元素后挪一位萎羔，最后添加
- add(Collention<? extends E> c)與add(int index, Collection<? extends E> c)核心類是toArray()與System.arraycopy(),與之前提的一樣（代碼不貼了--累人Ｒ鹤摺）
indexOf(Object o）與lastIndexOf(Object o)都會對o進(jìn)行null判斷，因為ArrayList可以添加null贾陷；clone()為淺拷貝缘眶，elementData數(shù)據(jù)不包括在內(nèi)
get,set,remove方法都沒什么好說的
removeAll(Collection<?> c), retainAll(Collection<?> c)
這兩個方法中若c==null則拋出NullPointException異常，接著調(diào)用batchRemove(Collection<?> c, boolean complement)
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];
} 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;
}
//w == size則說明沒有改變髓废，返回false巷懈，removeAll與retainAll結(jié)果為false
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
該方法在complement為true時，取elementData與c的交集慌洪，即相同部分保留砸喻；為false時，取elementData獨有部分保留蒋譬。所以removeAll調(diào)用batchRemove(c, false)割岛，retainAll調(diào)用batchRemove(c, true);
迭代器
- Iterator
private class Itr implements Iterator<E> {
int cursor; // 下一個要返回的元素的下標(biāo)
int lastRet = -1; // 被返回的元素的下標(biāo)，即調(diào)用next()返回elementData[lastRet]
int expectedModCount = modCount; //fail-fast,迭代中若數(shù)組被更改(add,remove
添加刪除操作）會造成二者不相等犯助，拋ConcurrentModificationException
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); //fail-fast
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet); //調(diào)用的是ArrayList的remove方法
cursor = lastRet; //lastRet表示被刪除的位置癣漆，后被cusor前挪一位填補上，cusor變?yōu)閘astRet
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//如果相對elementData中每個元素都執(zhí)行相同操作剂买，你可以寫一類實現(xiàn)Consumer接口惠爽，
復(fù)寫accept（），在調(diào)用該方法
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Consumer是個函數(shù)式接口瞬哼，函數(shù)描述符為：T → void, 多用于lambda
- ListIterator
//繼承itr婚肆，實現(xiàn)ListIterator implements Iterator<E>,ListIterator拓展了Iterator
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
//是否有前一個元素
public boolean hasPrevious() {
return cursor != 0;
}
//下一個元素位置
public int nextIndex() {
return cursor;
}
//前一個元素位置
public int previousIndex() {
return cursor - 1;
}
//返回前一個元素，即cusor-1處坐慰；cusor退一位较性，反復(fù)調(diào)用實現(xiàn)倒敘；如果之后你接著調(diào)用next(),
previous()將返回同一個結(jié)果
@SuppressWarnings("unchecked")
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];
}
//下面的add（）方法會重置lastRet = -1;所以add后避免調(diào)用set
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//add會插入到原本調(diào)用next函數(shù)返回的元素之前结胀，cusor自增1仍指向原本next函數(shù)返回的元素赞咙，
此時可通過previous來得到新增的元素；這樣設(shè)計保證了next函數(shù)不受影響
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();
}
}
}
SubList extends AbstractList<E> implements RandomAccess
內(nèi)部類private class SubList糟港，作用就是生成一個[fromeIndex,toIndex)大小的小型List攀操，麻雀雖小五臟俱全，只能通過subList(int fromIndex, int toIndex)函數(shù)調(diào)用秸抚，功能實現(xiàn)依賴外部類ArrayList速和，實現(xiàn)了自己的迭代器ListIterator歹垫。
還有一方法Arraylist.sort在這篇文章里介紹MergeSort與TimSort，ComparableTimSort
