關(guān)于ArrayList的源碼德迹，給出幾點比較重要的總結(jié)：
ArrayList是基于數(shù)組實現(xiàn)的闹蒜，是一個動態(tài)數(shù)組寺枉，其容量能自動增長，類似于C語言中的動態(tài)申請內(nèi)存绷落，動態(tài)增長內(nèi)存姥闪。
ArrayList不是線程安全的，只能在單線程環(huán)境下砌烁，多線程環(huán)境下可以考慮用collections.synchronizedList(List l)函數(shù)返回一個線程安全的ArrayList類筐喳，也可以使用concurrent并發(fā)包下的CopyOnWriteArrayList類催式。
ArrayList實現(xiàn)了Serializable接口，因此它支持序列化避归，能夠通過序列化傳輸荣月，實現(xiàn)了RandomAccess接口，支持快速隨機訪問梳毙，實際上就是通過下標序號進行快速訪問，實現(xiàn)了Cloneable接口账锹，能被克隆。
- 注意其三個不同的構(gòu)造方法奸柬。無參構(gòu)造方法構(gòu)造的ArrayList的容量默認為10，帶有Collection參數(shù)的構(gòu)造方法廓奕，將Collection轉(zhuǎn)化為數(shù)組賦給ArrayList的實現(xiàn)數(shù)組elementData。
- 注意擴充容量的方法ensureCapacity懂从。ArrayList在每次增加元素（可能是1個授段，也可能是一組）時侵贵，都要調(diào)用該方法來確保足夠的容量。當容量不足以容納當前的元素個數(shù)時窍育，就設(shè)置新的容量為舊的容量的1.5倍加1，如果設(shè)置后的新容量還不夠宴胧，則直接新容量設(shè)置為傳入的參數(shù)（也就是所需的容量），而后用Arrays.copyof()方法將元素拷貝到新的數(shù)組（詳見下面的第3點）恕齐。從中可以看出，當容量不夠時显歧，每次增加元素仪或，都要將原來的元素拷貝到一個新的數(shù)組中，非常之耗時士骤，也因此建議在事先能確定元素數(shù)量的情況下范删，才使用ArrayList，否則建議使用LinkedList拷肌。
- ArrayList的實現(xiàn)中大量地調(diào)用了Arrays.copyof()和System.arraycopy()方法到旦。我們有必要對這兩個方法的實現(xiàn)做下深入的了解旨巷。
首先來看Arrays.copyof()方法。它有很多個重載的方法添忘，但實現(xiàn)思路都是一樣的采呐，我們來看泛型版本的源碼：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
很明顯調(diào)用了另一個copyof方法，該方法有三個參數(shù)昔汉，最后一個參數(shù)指明要轉(zhuǎn)換的數(shù)據(jù)的類型，其源碼如下：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
這里可以很明顯地看出拴清，該方法實際上是在其內(nèi)部又創(chuàng)建了一個長度為newlength的數(shù)組靶病，調(diào)用System.arraycopy()方法，將原來數(shù)組中的元素復(fù)制到了新的數(shù)組中口予。
下面來看System.arraycopy()方法娄周。該方法被標記了native，調(diào)用了系統(tǒng)的C/C++代碼沪停，在JDK中是看不到的煤辨，但在openJDK中可以看到其源碼。該函數(shù)實際上最終調(diào)用了C語言的memmove()函數(shù)木张，因此它可以保證同一個數(shù)組內(nèi)元素的正確復(fù)制和移動众辨，比一般的復(fù)制方法的實現(xiàn)效率要高很多，很適合用來批量處理數(shù)組舷礼。Java強烈推薦在復(fù)制大量數(shù)組元素時用該方法鹃彻，以取得更高的效率。
- 注意ArrayList的兩個轉(zhuǎn)化為靜態(tài)數(shù)組的toArray方法妻献。
第一個蛛株，Object[] toArray()方法。該方法有可能會拋出java.lang.ClassCastException異常育拨，如果直接用向下轉(zhuǎn)型的方法谨履，將整個ArrayList集合轉(zhuǎn)變?yōu)橹付愋偷腁rray數(shù)組，便會拋出該異常熬丧，而如果轉(zhuǎn)化為Array數(shù)組時不向下轉(zhuǎn)型笋粟，而是將每個元素向下轉(zhuǎn)型，則不會拋出該異常析蝴，顯然對數(shù)組中的元素一個個進行向下轉(zhuǎn)型矗钟，效率不高，且不太方便嫌变。
第二個吨艇， T[] toArray(T[] a)方法东涡。該方法可以直接將ArrayList轉(zhuǎn)換得到的Array進行整體向下轉(zhuǎn)型（轉(zhuǎn)型其實是在該方法的源碼中實現(xiàn)的）组贺，且從該方法的源碼中可以看出失尖，參數(shù)a的大小不足時掀潮，內(nèi)部會調(diào)用Arrays.copyOf方法仪吧，該方法內(nèi)部創(chuàng)建一個新的數(shù)組返回鞠眉，因此對該方法的常用形式如下：
public static Integer[] vectorToArray2(ArrayList<Integer> v) {
Integer[] newText = (Integer[])v.toArray(new Integer[0]);
return newText;
}
ArrayList基于數(shù)組實現(xiàn)械蹋，可以通過下標索引直接查找到指定位置的元素哗戈，因此查找效率高，但每次插入或刪除元素暇仲，就要大量地移動元素奈附，插入刪除元素的效率低斥滤。
在查找給定元素索引值等的方法中勉盅，源碼都將該元素的值分為null和不為null兩種情況處理草娜，ArrayList中允許元素為null。
關(guān)于LinkedList的源碼茬贵，給出幾點比較重要的總結(jié)：
LinkedList簡介 LinkedList是基于雙向循環(huán)鏈表（從源碼中可以很容易看出）實現(xiàn)的，除了可以當作鏈表來操作外老充，它還可以當作棧啡浊，隊列和雙端隊列來使用胶背。
LinkedList同樣是非線程安全的奄妨，只在單線程下適合使用砸抛。
LinkedList實現(xiàn)了Serializable接口树枫，因此它支持序列化，能夠通過序列化傳輸奔誓，實現(xiàn)了Cloneable接口厨喂，能被克隆庄呈。
- 從源碼中很明顯可以看出，LinkedList的實現(xiàn)是基于雙向循環(huán)鏈表的斜纪，且頭結(jié)點中不存放數(shù)據(jù)盒刚。
注意兩個不同的構(gòu)造方法绿贞。無參構(gòu)造方法直接建立一個僅包含head節(jié)點的空鏈表，包含Collection的構(gòu)造方法贮聂，先調(diào)用無參構(gòu)造方法建立一個空鏈表吓懈，然后將Collection中的數(shù)據(jù)加入到鏈表的尾部后面耻警。
在查找和刪除某元素時，源碼中都劃分為該元素為null和不為null兩種情況來處理腮恩，LinkedList中允許元素為null温兼。
LinkedList是基于鏈表實現(xiàn)的募判，因此不存在容量不足的問題，所以這里沒有擴容的方法释液。
注意源碼中的Entry entry(int index)方法误债。該方法返回雙向鏈表中指定位置處的節(jié)點寝蹈，而鏈表中是沒有下標索引的登淘，要指定位置出的元素，就要遍歷該鏈表槽惫，從源碼的實現(xiàn)中界斜，我們看到這里有一個加速動作合冀。源碼中先將index與長度size的一半比較，如果index<size/2开缎，就只從位置0往后遍歷到位置index處奕删，而如果index>size/2疗认，就只從位置size往前遍歷到位置index處横漏。這樣可以減少一部分不必要的遍歷缎浇，從而提高一定的效率（實際上效率還是很低）。
注意鏈表類對應(yīng)的數(shù)據(jù)結(jié)構(gòu)Entry二蓝。如下;
// 雙向鏈表的節(jié)點所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)侣夷。
// 包含3部分：上一節(jié)點仑乌，下一節(jié)點琴锭，當前節(jié)點值决帖。
private static class Entry<E> {
// 當前節(jié)點所包含的值
E element;
// 下一個節(jié)點
Entry<E> next;
// 上一個節(jié)點
Entry<E> previous;
/**
* 鏈表節(jié)點的構(gòu)造函數(shù)。
* 參數(shù)說明：
* element —— 節(jié)點所包含的數(shù)據(jù)
* next —— 下一個節(jié)點
* previous —— 上一個節(jié)點
*/
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
LinkedList是基于鏈表實現(xiàn)的，因此插入刪除效率高刻像，查找效率低（雖然有一個加速動作）细睡。
要注意源碼中還實現(xiàn)了棧和隊列的操作方法，因此也可以作為棧湃缎、隊列和雙端隊列來使用嗓违。
ArrayList和LinkedList在性能上各有優(yōu)缺點，都有各自所適用的地方比庄，總的說來可以描述如下：
1．對ArrayList和LinkedList而言佳窑，在列表末尾增加一個元素所花的開銷都是固定的神凑。對ArrayList而言溉委，主要是在內(nèi)部數(shù)組中增加一項瓣喊，指向所添加的元素藻三，偶爾可能會導致對數(shù)組重新進行分配棵帽；而對LinkedList而言逗概，這個開銷是統(tǒng)一的忘衍，分配一個內(nèi)部Entry對象枚钓。
2．在ArrayList的中間插入或刪除一個元素意味著這個列表中剩余的元素都會被移動；而在LinkedList的中間插入或刪除一個元素的開銷是固定的秘噪。
3．LinkedList不支持高效的隨機元素訪問狸吞。
4．ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當?shù)目臻g
可以這樣說：當操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間,并且需要隨機地訪問其中的元素時,使用ArrayList會提供比較好的性能；當你的操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù),并且按照順序訪問其中的元素時,就應(yīng)該使用LinkedList了蹋偏。
