01

官方文檔：

LinkedList是Collection下的一個list實現(xiàn)，就像ArrayList一樣。

和ArrayList不同的是它是鏈表結構，而ArrayList是順序結構。我們平常使用的list是一樣的，理論上來說一種list就可以完成我們所有的需求。但是它們在運行過程中有區(qū)別的，完成需求所需要的資源也不相同，至于什么情況下使用哪種list就看需求和當前情況了。

LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。

LinkedList 可以被當作堆棧、隊列或雙端隊列進行操作。

LinkedList 實現(xiàn) List 接口，所以能對它進行隊列操作。

LinkedList 實現(xiàn) Deque 接口，能將LinkedList當作雙端隊列使用。

LinkedList 實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能克隆。

LinkedList 實現(xiàn)java.io.Serializable接口，所以LinkedList支持序列化，能通過序列化去傳輸。

LinkedList 是非同步的。

LinkedList的本質是雙向鏈表

LinkedList繼承于AbstractSequentialList，并且實現(xiàn)了Dequeue接口。

LinkedList包含兩個重要的成員：header 和 size。

　　header是雙向鏈表的表頭，它是雙向鏈表節(jié)點所對應的類Entry的實例。Entry中包含成員變量：previous, next, element。其中，previous是該節(jié)點的上一個節(jié)點，next是該節(jié)點的下一個節(jié)點，element是該節(jié)點所包含的值。

　　size是雙向鏈表中節(jié)點的個數(shù)。

雙向鏈表結構的講解：

• 鏈表：鏈表是一種重要的數(shù)據(jù)結構，有單鏈表和雙鏈表之分

單鏈表：

單鏈表（單向鏈表）：由兩部分組成 數(shù)據(jù)域（Data）和結點域(Node),單鏈表就像是一條打了很多結的繩子，每一個繩結相當于一個結點，每個節(jié)結點間都有繩子連接，這樣原理的實現(xiàn)是通過Node結點區(qū)的頭指針head實現(xiàn)的，每個結點都有一個指針，每個節(jié)點指針的指向都是指向自身結點的下一個結點，最后一個結點的head指向為null,這樣一來就連成了上述所說繩子一樣的鏈，對單鏈表的操作只能從一端開始，如果需要查找鏈表中的某一個結點，則需要從頭開始進行遍歷。

雙向鏈表結構

雙鏈表（雙向鏈表）：雙鏈表和單鏈表相比，多了一個指向尾指針（tail），雙鏈表的每個結點都有一個頭指針head和尾指針tail,雙鏈表相比單鏈表更容易操作，雙鏈表結點的首結點的head指向為null，tail指向下一個節(jié)點的tail;尾結點的head指向前一個結點的head，tail 指向為null，是雙向的關系；在單鏈表中若需要查找某一個元素時，都必須從第一個元素開始進行查找，而雙向鏈表除開頭節(jié)點和最后一個節(jié)點外每個節(jié)點中儲存有兩個指針，這連個指針分別指向前一個節(jié)點的地址和后一個節(jié)點的地址，這樣無論通過那個節(jié)點都能夠尋找到其他的節(jié)點。

• 插入刪除不需要移動元素外，可以原地插入刪除

• 可以在結構的前后插入數(shù)據(jù)

• 可以雙向遍歷

接口的示例圖：

LinkedList同時實現(xiàn)了List接口和Deque接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。這樣看來，LinkedList簡直就是個全能冠軍。當你需要使用?；蛘哧犃袝r，可以考慮使用LinkedList，一方面是因為Java官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個叫做Queue的類（它是個接口名字）。關于?；蜿犃?，現(xiàn)在的首選是ArrayDeque，它有著比LinkedList（當作?；蜿犃惺褂脮r）有著更好的性能。

構造函數(shù)：

LinkedList底層通過雙向鏈表實現(xiàn)，本節(jié)將著重講解插入和刪除元素時雙向鏈表的維護過程，也即是直接跟List接口相關的函數(shù)，而將Queue和Stack以及Deque相關的知識放在下一節(jié)講。雙向鏈表的每個節(jié)點用內部類Node表示。LinkedList通過first和last引用分別指向鏈表的第一個和最后一個元素。注意這里沒有所謂的啞元，當鏈表為空的時候first和last都指向null。

? ? ? ? ? ? ? ? ??

//Node內部類
private static class Node<E> {
? ?E item;
? ?Node<E> next;
? ?Node<E> prev;
? ?Node(Node<E> prev, E element, Node<E> next) {
? ? ? ?this.item = element;
? ? ? ?this.next = next;
? ? ? ?this.prev = prev;
? ?}
}

LinkedList的實現(xiàn)方式?jīng)Q定了所有跟下標相關的操作都是線性時間，而在首段或者末尾刪除元素只需要常數(shù)時間。為追求效率LinkedList沒有實現(xiàn)同步（synchronized），如果需要多個線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對其進行包裝。

02

方法剖析

add()的官方文檔：

add()方法有兩個版本，一個是add(E e)，該方法在LinkedList的末尾插入元素，因為有l(wèi)ast指向鏈表末尾，在末尾插入元素的花費是常數(shù)時間。只需要簡單修改幾個相關引用即可；另一個是add(int index, E element)，該方法是在指定下表處插入元素，需要先通過線性查找找到具體位置，然后修改相關引用完成插入操作。

結合上圖，可以看出add(E e)的邏輯非常簡單。

//add(E e)
public boolean add(E e) {
? ?final Node<E> l = last;
? ?final Node<E> newNode = new Node<>(l, e, null);
? ?last = newNode;
? ?if (l == null)
? ? ? ?first = newNode;//原來鏈表為空，這是插入的第一個元素
? ?else
? ? ? ?l.next = newNode;
? ?size++;
? ?return true;
}

? ? ? ? ? ? ? ?? ?

add(int index, E element)的邏輯稍顯復雜，可以分成兩部分，1.先根據(jù)index找到要插入的位置；2.修改引用，完成插入操作。

//add(int index, E element)
public void add(int index, E element) {
? ? ? ?checkPositionIndex(index);//index >= 0 && index <= size;
? ? ? ?if (index == size)//插入位置是末尾，包括列表為空的情況
? ? ? ? ? ?add(element);
? ? ? ?else {
? ? ? ? ? ?Node<E> succ = node(index);//1.先根據(jù)index找到要插入的位置
? ? ? ? ? ?//2.修改引用，完成插入操作。
? ? ? ? ? ?final Node<E> pred = succ.prev;
? ? ? ? ? ?final Node<E> newNode = new Node<>(pred, e, succ);
? ? ? ? ? ?succ.prev = newNode;
? ? ? ? ? ?if (pred == null)//插入位置為0
? ? ? ? ? ? ? ?first = newNode;
? ? ? ? ? ?else
? ? ? ? ? ? ? ?pred.next = newNode;
? ? ? ? ? ?size++;
? ? ? ?}
? ?}

上面代碼中的node(int index)函數(shù)有一點小小的trick，因為鏈表雙向的，可以從開始往后找，也可以從結尾往前找，具體朝那個方向找取決于條件index < (size >> 1)，也即是index是靠近前端還是后端。

03

remove()的官方文檔?

remove()方法也有兩個版本，一個是刪除跟指定元素相等的第一個元素remove(Object o)，另一個是刪除指定下標處的元素remove(int index)。

兩個刪除操作都要1.先找到要刪除元素的引用，2.修改相關引用，完成刪除操作。在尋找被刪元素引用的時候remove(Object o)調用的是元素的equals方法，而remove(int index)使用的是下標計數(shù)，兩種方式都是線性時間復雜度。在步驟2中，兩個remove()方法都是通過unlink(Node<E> x)方法完成的。這里需要考慮刪除元素是第一個或者最后一個時的邊界情況。

//unlink(Node<E> x)，刪除一個Node
E unlink(Node<E> x) {
? ?final E element = x.item;
? ?final Node<E> next = x.next;
? ?final Node<E> prev = x.prev;
? ?if (prev == null) {//刪除的是第一個元素
? ? ? ?first = next;
? ?} else {
? ? ? ?prev.next = next;
? ? ? ?x.prev = null;
? ?}
? ?if (next == null) {//刪除的是最后一個元素
? ? ? ?last = prev;
? ?} else {
? ? ? ?next.prev = prev;
? ? ? ?x.next = null;
? ?}
? ?x.item = null;//let GC work
? ?size--;
? ?return element;

}

04

get()的官方文檔：

get(int index)得到指定下標處元素的引用，通過調用上文中提到的node(int index)方法實現(xiàn)。

public E get(int index) {
? ?checkElementIndex(index);//index >= 0 && index < size;
? ?return node(index).item;
}

05

set()的官方文檔：

set(int index, E element)方法將指定下標處的元素修改成指定值，也是先通過node(int index)找到對應下表元素的引用，然后修改Node中item的值。

public E set(int index, E element) {
? ?checkElementIndex(index);
? ?Node<E> x = node(index);
? ?E oldVal = x.item;
? ?x.item = element;//替換新值
? ?return oldVal;
}

總結：

1.LinkedList底層是雙向鏈表實現(xiàn)的，所以新增和刪除效率高

2.為追求效率LinkedList沒有實現(xiàn)同步（synchronized），如果需要多個線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對其進行包裝。

3.底層實現(xiàn)了Deque接口可以看作隊列，也是list下面的子集

? ? ? ? ?