1秦叛、ArrayList定義
ArrayList 是一個(gè)數(shù)組隊(duì)列览露，相當(dāng)于 動(dòng)態(tài)數(shù)組判莉。與Java中的數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)甲捏。它繼承于A(yíng)bstractList，實(shí)現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable這些接口鞭执。
ArrayList 繼承了AbstractList司顿，實(shí)現(xiàn)了List芒粹。它是一個(gè)數(shù)組隊(duì)列，提供了相關(guān)的添加大溜、刪除是辕、修改、遍歷等功能猎提。
ArrayList 實(shí)現(xiàn)了RandmoAccess接口，即提供了隨機(jī)訪(fǎng)問(wèn)功能旁蔼。RandmoAccess是java中用來(lái)被List實(shí)現(xiàn)锨苏，為L(zhǎng)ist提供快速訪(fǎng)問(wèn)功能的。在A(yíng)rrayList中棺聊，我們即可以通過(guò)元素的序號(hào)快速獲取元素對(duì)象伞租；這就是快速隨機(jī)訪(fǎng)問(wèn)。稍后限佩，我們會(huì)比較List的“快速隨機(jī)訪(fǎng)問(wèn)”和“通過(guò)Iterator迭代器訪(fǎng)問(wèn)”的效率葵诈。
ArrayList 實(shí)現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()祟同，能被克隆作喘。
ArrayList 實(shí)現(xiàn)java.io.Serializable接口，這意味著ArrayList支持序列化晕城，能通過(guò)序列化去傳輸泞坦。
和Vector不同，ArrayList中的操作不是線(xiàn)程安全的砖顷！所以贰锁，建議在單線(xiàn)程中才使用ArrayList，而在多線(xiàn)程中可以選擇Vector或者CopyOnWriteArrayList滤蝠。
2豌熄、ArrayList源碼分析
ArrayList 有以下三種初始化的方法，此為1.8.0的源碼物咳，和之前的源碼有所區(qū)別锣险，在之前的源碼中，默認(rèn)情況下览闰，初始容量為10囱持，而在1.8的源碼中，默認(rèn)情況下則為
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 指定一個(gè)初始容量的構(gòu)造方法
*
* @param ArrayList的初始容量
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
//如果初始容量>0 焕济，則以指定的值為初始容量
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//如果指定的值為0纷妆，則直接賦值為空數(shù)組
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*在此方法中則默認(rèn)賦值一個(gè)DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空數(shù)組，此數(shù)組和EMPTY_ELEMENTDATA 區(qū)分開(kāi)來(lái)晴弃，用來(lái)在添加第一個(gè)元素的時(shí)候掩幢，確定要擴(kuò)容多少
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
*構(gòu)造一個(gè)包含指定元素的list逊拍，這些元素的是按照Collection的迭代器返回的順序排列的
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//如果是非空的集合，則直接拷貝進(jìn)入當(dāng)前數(shù)組
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果傳入的數(shù)據(jù)為空际邻，則使用默認(rèn)的空數(shù)組代替
this.elementData = EMPTY_ELEMENTDATA;
}
}
3芯丧、增刪改查
add方法
/**
* 直接在集合的末尾添加一個(gè)元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add方法分成了兩步進(jìn)行，
判斷并擴(kuò)充容量（ ensureCapacityInternal(size + 1)）+賦值（ elementData[size++] = e）
從代碼中可以看出世曾，進(jìn)行添加數(shù)據(jù)操作的時(shí)候缨恒，會(huì)先判斷當(dāng)前底層的數(shù)組是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，這個(gè)數(shù)組在構(gòu)造方法 ArrayList() 中被賦值轮听，用來(lái)區(qū)別于EMPTY_ELEMENTDATA 骗露，在第一次進(jìn)行數(shù)組操作的時(shí)候進(jìn)行判斷，從源碼可以看出血巍，會(huì)和默認(rèn)的容量10進(jìn)行比較萧锉，取較大的值，相對(duì)于之前直接 賦值為 10 的容量述寡，個(gè)人覺(jué)得有兩點(diǎn)優(yōu)勢(shì)：1柿隙、初始化的時(shí)候不會(huì)直接開(kāi)辟空間 2、減少了一次擴(kuò)容操作鲫凶；效率上有一定的提升禀崖，設(shè)計(jì)還是比較巧妙的
private void ensureCapacityInternal(int minCapacity) {
//如果調(diào)用的是 參數(shù)為空的構(gòu)造方法，第一次操作的時(shí)候螟炫，就判斷一下帆焕，
//如果此時(shí)請(qǐng)求的容量大于默認(rèn)初始容量10，取請(qǐng)求的容量不恭，否則為默認(rèn)容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//明確容量
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果請(qǐng)求的最小容量大于數(shù)組長(zhǎng)度叶雹，則進(jìn)行一次擴(kuò)容，以?xún)?chǔ)存所有數(shù)據(jù)
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//增加容量折晦，以確保能容納mincapacity指定的元素
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//擴(kuò)容，新的容量為原來(lái)的 1.5倍
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:
//將老數(shù)據(jù)copy到新的數(shù)組中
elementData = Arrays.copyOf(elementData, newCapacity);
}
add 的其他方法
從源碼可以很明確的看出來(lái)满着，和add（E e）非常接近，僅在copy數(shù)據(jù)的時(shí)候有所差別
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
//和add（E e）方法的區(qū)別僅這一行代碼贯莺，擴(kuò)容之后风喇，將老數(shù)據(jù)在從指定位置(index)開(kāi)始
//之后的數(shù)據(jù)都向后移動(dòng)一位，然后將index位置的賦值為 e
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//和add 方法類(lèi)似缕探，區(qū)別在于將傳入的集合轉(zhuǎn)化成數(shù)組魂莫，然后整體位移copy
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//擴(kuò)容判斷
ensureCapacityInternal(size + numNew); // Increments modCount
//將傳入的數(shù)據(jù)copy進(jìn)入數(shù)組
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
刪除 remove方法
移出數(shù)據(jù)有 remove(int index) remove(Object o) ，兩個(gè)方法本質(zhì)都是根據(jù)index爹耗，直接利用數(shù)組的下標(biāo)刪除指定數(shù)據(jù)耙考，同時(shí)會(huì)將數(shù)據(jù)進(jìn)行位移谜喊，填補(bǔ)空缺
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)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
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;
}
查找 get（int index）
ArrayList底層是數(shù)組，因此查找就非常簡(jiǎn)單倦始，直接根據(jù)數(shù)組下標(biāo)找到數(shù)據(jù)
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
更改 set(int index, E element)
更改也是非常簡(jiǎn)單斗遏，直接根據(jù)數(shù)組下標(biāo)更改數(shù)據(jù)
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
增刪改查小結(jié)
從上面的源碼可以很明顯的看出，ArrayList的增刪改查操作實(shí)質(zhì)上就是對(duì)底層數(shù)組的操作鞋邑，新增的時(shí)候诵次，都需要對(duì)數(shù)組進(jìn)行擴(kuò)容+copy操作，刪除也需要對(duì)數(shù)組進(jìn)行copy枚碗，所以ArrayList的增加和刪除效率會(huì)非常低逾一，但是相對(duì)的，得利于底層的數(shù)組結(jié)果视译，在進(jìn)行查找和更改操作的時(shí)候，可以根據(jù)下標(biāo)直接進(jìn)行操作归敬，只有O(1)的復(fù)雜度酷含，因此在查找需求比較頻繁的操作中，可以使用ArrayList汪茧，極大的增加操作效率椅亚，但是在增刪比較頻繁的時(shí)候，就需要考慮其他的數(shù)據(jù)結(jié)構(gòu)了舱污；
同時(shí)呀舔，合理的使用ArrayList的構(gòu)造方法，例如在初始化的時(shí)候扩灯，如果已經(jīng)知道當(dāng)前數(shù)據(jù)的大小媚赖，可以直接使用ArrayList(int initialCapacity) 構(gòu)造方法指定初始容量，這樣可以避免在添加數(shù)據(jù)的時(shí)候頻繁擴(kuò)容降低性能珠插，同時(shí)也可以避免1.5倍擴(kuò)容機(jī)制造成的空間浪費(fèi)
