List在數據結構中表現為是線性表的方式，其元素以線性方式存儲，集合中允許存放重復的對象，List接口主要的實現類有
ArrayList
ArrayList其實就是一組長度可變的數組，當實例化了一個ArrayList，該數據也被實例化了，當向集合中添加對象時，數組的大小也隨著改變，這樣它所帶來的有優點是快速的隨機訪問，即使訪問每個元素所帶來的性能問題也是很小的，但缺點就是想其中添加或刪除對象速度慢，當你創建的數組是不確定其容量，所以當我們改變這個數組時就必須在內存中做很多的處理，如你想要數組中任意兩個元素中間添加對象，那么在內存中數組要移動所有后面的對象。
LinkedList
LinkedList是通過節點的連接實現鏈表的數據結構，向linkedList中插入或刪除元素的速度是特別快，而隨機訪問的速度相對較慢，這個是由于鏈表本身的性質造成的，在鏈表中，每個節點都包含了前一個節點的引用，后一個節點的引用和節點存儲值，當一個新節點插入式，只需要修改其中相關的前后關系節點引用即可，刪除節點也是一樣。操作對象只需要改變節點的鏈接，新節點可以存放在內存的任何位置，但也就是因為如此LinkedList雖然存在get()方法，但是這個方法通過遍歷節點來定位所以速度很慢。LinkedList還單獨具addFrist(),addLast(),getFrist(),getLast(),removeFirst(),removeLast()方法，這些方法使得LinkedList可以作為堆棧，隊列，和雙隊列來使用。
說白了，ArrayList和LinkedList就是數據結構中的順序存儲表和鏈式存儲表。
ArrayList構造原理
上面已經清楚ArrayList和LinkedList就是數據結構的順序表和鏈表(不清楚的翻翻數據結構的書)，下面簡單分析一下它們的實現方式。
下表是摘自sum提供的ArrayList的api文檔
ArrayList()
構造一個初始容量為 10 的空列表。
ArrayList(Collection<? extends E> c)
構造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
ArrayList(int initialCapacity)
構造一個具有指定初始容量的空列表。
第一個構造函數是沒有默認構建了一個初始容量10的空列表，第二個構造函數是制定collection元素的列表，第三個構造函數是由用戶指定構造的列表初始化容量多少，如果使用第一個構造函數則表示默認調用該參數為initialCapacity=10來構造一個列表對象。
ArrayList源碼稍微進行分析
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
public int size() {
return size;
}
}
可以發現ArrayList中包含兩個主要的屬性
private transient Object[] elementData;
private int size;
其中elementData[]是列表的實現的核心數組，我們使用該數組來存放集合中的數據，而我們的構造函數所傳遞的initialCapacity參數是構建該數組的長度。
在看看size的實現形式，它的作用是返回size的屬性值的大小，我們再看看另外一個構造函數public ArrayList(Collection<? extends E> c)，該構造函數的作用是把另外一個容器對象中的元素放入當點的List對象中。首先是通過調用另外一個容器對象c的size()來設置當前List對象的size屬性的長度大小。接下來就似乎對elementData[]數組進行初始化，最后通過Arrays.copyOf(U[] original, int newLength, Class<? extends T[]> newType)方法把當前容器中的對象都存放進新的數組elementData，主要就完成了一個列表的創建。
ArrayList容量擴充
還有一個問題就是我們所建立的ArrayList是使用數組來實現的，但數組的長度一旦被初始化就不能改變，而我們在給此列表對象添加元素時卻沒有受到長度的限制，所以，ArrayList的elementData屬性一定是存在一個動態擴充容量的機制，下面把相關的部分源碼貼出來再做研究
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
protected transient int modCount = 0;
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
看看public boolean add(E e)方法，可以發現在添加一個元素到容器中的時候，我們會先通過ensureCapacity(size + 1)判斷該數組是否需要擴充。
public void ensureCapacity(int minCapacity)這個方法是用來判斷當前的數組是否需要擴充，并且該擴充多少。modCount++; 表示當前的對象對elementData數組進行了多少次擴充，清空和移除等操作，相當于是一個對當前List對象的一個操作記錄數。
int oldCapacity = elementData.length; 初始化oldCapacity，表示為當前elementData數組的長度。
if (minCapacity > oldCapacity) 判斷minCapacity和oldCapacity誰大，來決定是否需要擴充。
int newCapacity = (oldCapacity * 3)/2 + 1; 擴充的策列是判斷(oldCapacity * 3)/2 + 1和minCapacity兩者之間誰更大，取更大的數作為擴充后數組的initialCapacity值，然后使用數組拷貝的方式，把以前的數據轉移到新的數組對象中
如果minCapacity 小于 oldCapacity 就不需要再擴充。
ArrayList刪除元素
public E remove(int index) {
RangeCheck(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; // Let gc do its work
return oldValue;
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
在看看ArrayList移除元素是怎么實現的，首先判斷需要刪除的index是否在elementData數組的下標內，如不存在則拋出IndexOutOfBoundsException。
modCount++; 與擴充元素一個，刪除元素也記下來操作數。
E oldValue = (E) elementData[index]; 獲取需要刪除元素的對象。
int numMoved = size - index - 1; 獲取需要被刪除元素的下標，刪除該元素后，數組需要在此元素下標后的所有對象進行內存的移動。
System.arraycopy(elementData, index+1, elementData, index,numMoved);對numMoved后面的所有對象通過copy的方式進行內存的移動重新構建數組。
說完ArrayList的實現，再說說linkedList
構建雙鏈表(LinkedList)
LinkedList是類似于C語言的雙鏈表，雙鏈表比單鏈表多了一個域，這個雙鏈表就有了三個域，一個域來用存儲數據元素，一個用來指向后續節點，另一個是指向結點的直接前驅節點。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
public LinkedList() {
header.next = header.previous = header;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
}
在Entry類中，定義了三個屬性，分別為E element 表示數據與，Entry<E> next為后續指針域，Entry<E> previous為前驅指針域。
在LinkedList中定義了一個重要的屬性header，頭結點，不會納入鏈表的總元素,該節點的previous是指向最后節點，next是指向第一節點。
構造函數LinkedList() 構造一個空列表。將header的前驅指針域和后續指針域都指向了自己,看到這里可以發現，next和previous就是一個引用，其實也相等于C里面的指針，不過C不會處理空指針，直接放操作系統處理了，java就直接拋出NullPointerException，根本不讓它破壞系統的機會。
LinkedList元素變動
上面說到了LinkedList的新增和刪除的效率比ArrayList的高，實際上在 鏈表操作這些方法時，只需要改變2個節點各自的前驅指針和后續指針域，而ArrayList是需要移動很多的元素。
public boolean add(E e) {
addBefore(e, header);
return true;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
相比ArrayList的add()方法，LinkedList實現起來非常簡單，主要是兩行代碼：
newEntry.previous.next = newEntry;將上一節點的后續節點指向新增的節點
newEntry.next.previous = newEntry;頭節點的前驅節點指向新增節點，size和modCount自增記錄。
同樣remove的實現也非常簡單
e.previous.next = e.next;該節點的后一節點的后去節點指向該節點的后驅節點，
e.next.previous = e.previous;該節點的后一節點的前驅節點指向該節點的前驅節點。
e.next = e.previous = null;把該節點的前驅節點和后驅節點全部指向null。
e.element = null;把該節點的數據域設置為null。
隨機訪問
相比順序表，鏈表的隨機訪問效率要低得多(理論說法，不是絕對)，ArrayList可以根據索引號進行隨機訪問，而LinkedList則不要遍歷訪問。
public E get(int index) {
return entry(index).element;
}
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
上列的代碼是對一個鏈表的遍歷，其中包含了一個算法，如果給的索引號小于總節點數的一半，則在鏈表的前半部分第一個節點完進行遍歷，如果給的索引號大于總節點數的一半，則從最后一個節點往前進行遍歷直到索引號。
最后
總結一下ArrayList和LinkedList的各自特點
1.ArrayList是基于線性表的順序存儲表，LinkedList是基本線性表的鏈表存儲表。
2.對于新增和刪除元素，LinkedList比較占有優勢，只需要變前后2個節點，而ArrayList要移動數據。
3.對于隨機訪問來說，ArrayList比較占有優勢，可以根據索引號快速訪問，而LinkedList則需要遍歷集合的元素來定位。
4.而對于迭代操作(iterate)和查找操作(indexOf)，兩者是差不多。
不過上面都是基于理論，具體問題還是要根據事實進行分析，如ArrayList刪除的元素剛好是隊列的最后一個元素，那么是無需要移動數據的，大體我們可以認為需要隨機訪問較多的那么比較適合用ArrayList，如果是插入和刪除(如消息隊列)較多的那么就需要考慮LinkedList。
上面主要是參考了jdk源碼，數據結構和一些相關資料本著好記性不如爛博客的精神記錄下來，希望朋友們如果發覺哪里不對請指出來，虛心請教
----------------------------------------
by 陳于喆
QQ:34174409
Mail: dongbule@163.com