采用數(shù)組方式存儲(chǔ)數(shù)據(jù)，可以添加null元素，此數(shù)組元素?cái)?shù)大于實(shí)際存儲(chǔ)的數(shù)據(jù)以便增加插入元素锈遥，都允許直接序號(hào)索引元素，但是插入數(shù)據(jù)要涉及到數(shù)組元素移動(dòng)等內(nèi)存操作勘畔，所以插入數(shù)據(jù)慢所灸，查找有下標(biāo)，所以查詢數(shù)據(jù)快
看了這幾篇文章炫七，一個(gè)系列的爬立，講的非常好，感謝作者万哪，下面我只進(jìn)行一些要點(diǎn)的補(bǔ)充以及總結(jié)侠驯。
https://zhuanlan.zhihu.com/p/27873515
https://zhuanlan.zhihu.com/p/27878015
https://zhuanlan.zhihu.com/p/27938717
https://zhuanlan.zhihu.com/p/28016098
ArrayList是線程不安全的，相比于Vector奕巍，Vector在真正操作數(shù)據(jù)的函數(shù)都需要加入synchronized關(guān)鍵字
ArrayList的緩存：
主要是利用static和final的變量特性吟策，不需要我們new，JVM會(huì)提前初始化好的止，并且static變量只有唯一一份踊挠，無論多少該類有多少個(gè)對(duì)象，因而冲杀，每次使用ArrayList的無參構(gòu)造函數(shù)new新的對(duì)象效床，作者為了避免我們反復(fù)的創(chuàng)建無用數(shù)組，所有新new出來的ArrayList底層數(shù)組都指向緩存在方法區(qū)里的Object[]數(shù)組权谁，其實(shí)是指向了最根本的DEFAULTCAPACITY_EMPTY_ELEMENTDATA靜態(tài)數(shù)組剩檀。
ArrayList允許存在null元素
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;
}
比如其indexOf方法，只要在size范圍內(nèi)旺芽，如果存在即可
ArrayList的add(E e)：
先確保容量沪猴，使用ensureCapacityInternal()辐啄，默認(rèn)容量DEFAULT_CAPACITY為10，不得不上圖
這里运嗜，grow方法壶辜，ArrayList的數(shù)組拓展為原數(shù)組的1.5倍（使用length，size表示實(shí)際的元素有多少個(gè)担租，length是數(shù)組帶有的屬性）砸民。
稍微提一下，這里利用到了Arrays的copyOf方法奋救，其底層實(shí)現(xiàn)有native關(guān)鍵字岭参，表示是非java語(yǔ)言實(shí)現(xiàn)的，因而尝艘，如果有數(shù)組拷貝演侯，建議使用java自帶的此方法
ArrayList的add(int index, E element)：
判斷下標(biāo)是否合法，先確保容量背亥，再將index及其后的元素往后復(fù)制秒际，再插入
主要關(guān)注時(shí)間復(fù)雜度：如果我們不指定位置直接添加元素時(shí)(add(E element))，元素會(huì)默認(rèn)會(huì)添加在最后狡汉，不會(huì)觸發(fā)底層數(shù)組的復(fù)制娄徊，不考慮底層數(shù)組自動(dòng)擴(kuò)容的話，時(shí)間復(fù)雜度為O(1) 轴猎，在指定位置添加元素(add(int index, E element))嵌莉，需要復(fù)制底層數(shù)組进萄，根據(jù)最壞打算捻脖，時(shí)間復(fù)雜度是O(n)。
add()都需要考慮確保容量問題
EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的區(qū)別：
DEFAULTCAPACITY_EMPTY_ELEMENTDATA與EMPTY_ELEMENTDATA數(shù)組的區(qū)別在于當(dāng)?shù)谝粋€(gè)元素被加入進(jìn)來的時(shí)候它知道如何擴(kuò)張中鼠；可以看到在無參構(gòu)造函數(shù)中可婶，代碼
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
在這里其實(shí)是構(gòu)造了一個(gè)初始容量為 10 的空列表，為何援雇？看add函數(shù)便知矛渴，在源碼中函數(shù)add(E e)中的第一行代碼中的所在的函數(shù)就是這句話的實(shí)現(xiàn)，當(dāng)中調(diào)用ensureCapacityInternal惫搏，代碼在此處確定了容量至少為10（即默認(rèn)容量）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
==其實(shí)依舊不是很明白具温，有大神知否？==
ArryList的remove()：
有兩種形式
- remove(int index)——檢查下標(biāo)合法筐赔，進(jìn)行元素刪除铣猩，并且拷貝后面的元素覆蓋，將最后一個(gè)元素置為null
- remove(Object o)——先判斷o是否為空茴丰，在size范圍內(nèi)如果有空达皿，fastRemove后返回true天吓，如果不為空，使用equals判斷峦椰，其他情況返回false龄寞。注意：使用此方法進(jìn)行刪除元素，一般需要重寫equals
最終汤功，remove都只是將elementData[i]=null物邑，clear也是一樣，但clear需要遍歷每一個(gè)元素賦值為null冤竹，而不是直接將elementData=null拂封，
時(shí)間復(fù)雜度：如果底層數(shù)組長(zhǎng)度為n，當(dāng)我們用下標(biāo)方式去刪除元素時(shí)鹦蠕，如果刪除的是最后一個(gè)元素冒签，不會(huì)觸發(fā)數(shù)組底層的復(fù)制，時(shí)間復(fù)雜度為O(1)钟病。如果刪除第i的元素萧恕，會(huì)觸發(fā)底層數(shù)組復(fù)制n-i次，根據(jù)最壞情況肠阱，時(shí)間復(fù)雜度為O(n)票唆。
fastRemove其實(shí)只是將代碼提取出來，做了拷貝工作而已（在ArrayList中屹徘，fastRemove只是給remove方法使用）
ArrayList的RangeCheck()：
應(yīng)用于一下幾個(gè)函數(shù)（add函數(shù)使用rangeCheckForAdd）
- get(int index)
- set(int index, E element)
- remove(int index)
比較需要關(guān)注的走趋，在RangeCheck里面，沒有檢查index是否<0噪伊，因?yàn)檫@些方法在調(diào)用了rangeCheck()方法后簿煌，會(huì)馬上調(diào)用elementData(int index)方法來獲取指定位置元素的值。（個(gè)人表示不咋理解為啥要這么弄鉴吹，有理解的朋友麻煩講講姨伟？）這兩個(gè)方法調(diào)用保證了0 < index < size()
ArrayList的get()和set()：
由于是數(shù)組，底層數(shù)組存/取元素效率非常的高豆励，時(shí)間復(fù)雜度是O(1)
clone()
實(shí)現(xiàn)clone()需要有Cloneable接口夺荒，否則拋出CloneNotSupportedException，ArrayList的clone只是淺復(fù)制良蒸，也就是引用的元素本身是跟原本同樣的
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
ArrayList的優(yōu)劣勢(shì)：
下標(biāo)的標(biāo)索引技扼、存/取快
查找（非下標(biāo)查詢），插入和刪除元素效率似乎不太高嫩痰，時(shí)間復(fù)雜度為O(n)剿吻，尤其是在有大量數(shù)據(jù)的時(shí)候。
插入和刪除元素效率->找LinkedList
查找元素效率不高->找HashMap
