ArrayList和LinkedList是我們在開發過程中常用的兩種集合類，本文將從底層源碼實現對其進行簡單介紹。

下圖是Java集合類所涉及的類圖。

一.ArrayList

從上面的集合類圖可以看出，ArrayList實現了List接口。ArrayList是順序的集合容器,容器中可以存放null元素，而底層則是通過一個可自動增長大小的動態數組實現的。ArrayList不是線程安全的，也沒有實現同步。

1.1 ArrayList操作性能

訪問數組中第 n 個數據的時間花費是?O(1)，但是要在數組中查找一個指定的數據則是 O(N)。當向數組中插入或者刪除數據的時候，最好的情況是在數組的末尾進行操作，時間復雜度是?O(1)，但是最壞情況是插入或者刪除第一個數據，時間復雜度是O(N)。在數組的任意位置插入或者刪除數據的時候，后面的數據全部需要移動，移動的數據還是和數據個數有關所以總體的時間復雜度仍然是O(N)。

1.2 私有屬性

ArrayList有兩個私有屬性，一個是實現數據存儲的數組，一個是表示數組中元素的個數。值得注意的是關鍵字transient。

ArrayList這個類實現了Serializable接口。Java的Serializable提供了一種持久化對象實例的機制，當持久化對象時，可能某個特殊的對象數據成員我們不想讓其用Serializable機制保存它，可以使用關鍵字transient來進行屏蔽。此外還有個保護的屬性：modCount，含義為已從結構上修改此列表的次數。從結構上修改是指更改列表的大小，或者打亂列表，從而使正在進行的迭代產生錯誤的結果。

1.3 構造方法

ArrayList中有三個構造函數，一個是默認構造一個容量為10的數組，一個指定容量的空列表和一個Collection類型的空列表。我們可以在使用時通過指定我們預估到的數組容量，來減少擴容次數

1.4 數組擴容

每一個ArrayList的實例都有一個容量，用來表示存儲數據的數組大小。容器內的元素不能大于當前當前的容器大小。當向容器中添加數據時，若容器的容量不足，容器會自動擴容。通過對比jdk1.7的ArrayList源碼發現，擴容兩個方法是不一樣的，jdk1.6中使用的是除法對其容量進行計算（加0.5倍），而jdk1.7中則使用的是移運算。

位運算是CPU直接操作的，除法等四則運算都是基于移位運算的，所以當有大量計算的時候，移位運算可以大大節約CPU的時間。通過1千萬次位運算和四則運算做對比數據結果如下：

可以看出，在計算大量數據的情況下，移位運算的花費時間比乘除法快很多。

1.5 數組復制方法

可以看到在ensureCapacity(intminCapacity)中調用的是Arrays的copyOf()方法，而在add方法中，調用的數組復制方法為：

native void arraycopy();Arrays的copyOf方法的實現：

實現copyOf的時候會新創建一個大小為newCapcity的數組，然后將舊的elementData放入其中。

1.6 小節

1、通過查看ArrayList的源碼，注意到有三個不同的構造方法，合理使用構造方法能減少數組擴容拷貝造成的額外開銷。

2、ArrayList大量調用了Arrays.copyOf和System.arrayCopy的方法，注意這兩個方法的區別。

3、jdk1.6和1.7中數組擴容的方法不一致，注意比較有差異的地方。

二.LinkedList

LinkedList與ArrayList一樣實現List接口，只是ArrayList是List接口的大小可變數組的實現，LinkedList是List接口鏈表的實現。基于鏈表實現的方式使得LinkedList在插入和刪除時更優于ArrayList，而隨機訪問則比ArrayList遜色些。

除了實現 List 接口外，LinkedList類還實現?Deque接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。

LinkedList定義：

public class LinkedList<E > extends AbstractSequentialList<E>

implements List<E>,Deque<E>, Cloneable, java.io.Serializable

2.1 底層數據結構

與ArrayList的區別在于，LinkedList底層是基于雙向鏈表實現的：

以上的數據結構可以從LinkedList的私有屬性看出：

private transient Entry<E> header = newEntry<E>(null, null, null);//頭結點是不存放元素的

private transient int size = 0;//雙向循環鏈表的大小

2.2 雙向循環列表的操作性能

對于雙向循環鏈表的插入和刪除操作只是多移動幾個指針。

備注：這里只是單純的描述雙向鏈表這種數據結構的插入和刪除性能，下文將對比ArrayList與LinkedList的性能。

2.3 構造函數

LinkedList類有兩個構造函數，一個是無參數的，一個是構造任意類型的集合類的列表

該構造函數構造一個空的列表，header頭結點表示如下, 形成一個閉環。

有參構造方法，參數為collection的c，this()調用默認的無參構造函數，然后再調用addAll()方法，將c中的元素添加加入列表。

三.LinkedList與ArrayList比較

1.ArrayList是基于數組的數據結構，LinkedList是基于鏈表的數據結構。

2.ArrayList內部的元素可以直接通過get與set方法進行訪問,因為ArrayList本質上就是一個數組.但LinkedList在get與set方面弱于ArrayList.

當然,這些對比都是指數據量很大或者操作很頻繁的情況下的對比,如果數據和運算量很小,那么對比將失去意義.

3.此外 LinkedList 還實現了?Queue?接口,該接口比List提供了更多的方法,包括?offer(),peek(),poll()等.

注意: 默認情況下ArrayList的初始容量非常小,所以如果可以預估數據量的話,分配一個較大的初始值屬于最佳實踐,這樣可以減少調整大小的開銷。

4.對于ArrayList與LinkedList性能下圖做個簡單比較

* 表中的 add() 代表 add(E e),而 remove()代表 remove(int index)

ArrayList 對于隨機位置的add/remove，時間復雜度為 O(n),但是對于列表末尾的添加/刪除操作,時間復雜度是 O(1). 而LinkedList對于隨機位置的add/remove，時間復雜度為 O(n),但是對于列表 末尾/開頭 的添加/刪除操作,時間復雜度是 O(1).

下面是測試代碼：

輸出結果截圖如下：

上述測試可以看出LinkedList在 進行add和remove操作時更快,而在進行get操作時較慢.

通過本次源碼學習之旅，我從LinkedList、ArrayList的底層結構出發，更深刻地了解了這兩個類的一些基本操作方法，文章中有不周全的地方歡迎指正，共同學習。