在學習LinkedList之前，應瞭解一些關於LinkedList的其他知識，下圖是LinedList的類圖

此外，我們知道LinkedList底層是雙向循環鏈表實現的，那雙向循環鏈表這樣的數據結構與其他的鏈表數據結構之間的區別又是怎麼樣的呢？

1、單向鏈表

2、單向循環鏈表

3、雙向鏈表

4、雙向循環鏈表

小結：

單鏈表：通過每個節點的next域存放下一個節點的地址，最後一個節點的存放為null；

單向循環鏈表：與單鏈表的區別在於，最後一個接地啊存放的是頭結點的地址；

雙向鏈表：從圖中可以看出雙向循環鏈表的每一個結構體包含兩個存放地址的域，一個pre存放前一個節點的地址，一個next存放下一個節點的位置；且最後一個節點的next引用為null，第一個節點的pre的引用也為null；

雙向循環鏈表:與雙向鏈表的區別在於最後一個節點的next存放的是頭結點的地址，頭結點的pre存放的是最後一個接地的地址。這樣整個鏈表就構成一個環狀。

而LinkedList就採用的是雙向鏈表的結構實現的，而且頭結點是不存放數據的。

二、LinkedList概述

LinkedList與ArrayList一樣實現List接口，只是ArrayList是List接口的大小可變數組的實現，LinkedList是List接口鏈表的實現。基於鏈表實現的方式使得LinkedList在插入和刪除時更優於ArrayList，而隨機訪問則比ArrayList遜色些。LinkedList實現所有可選的列表操作，並允許所有的元素包括null。

除了實現 List 接口外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。

此類實現 Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。

所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。同時，與ArrayList一樣此實現不是同步的。

LinkedList定義：

public class LinkedList<E>extends AbstractSequentialList<E>

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

定義解析：LinkedList是一個繼承了AbstractSequentialList類的雙向鏈表，且實現了Deque接口，既是可以像雙端隊列。LinkedList實現了List接口，就可以對它進行隊列操作。此外，還實現了Cloneable，可以覆蓋父類的clone方法。實現的Serializable接口，使得它可以進行序列化和反序列化。

2.1底層數據結構

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

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

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

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

其中Entry是一個內部類，它的類定義如下：

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;

}

}

該類定義的存儲的元素，還有該元素的前一個節點和後一個節點。

2.2雙向循環鏈表操作性能

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

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

2.3構造函數

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

//構造一個空的列表

該構造函數是構造有一個空的列表，header頭結點表示如下：

形成一個閉環。

/**

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

**/

2.4添加方法

LinkedList類提供了兩種添加元素的方法，一種是向列表中添加某個元素，一種是添加collection集合中所有的元素。

1)

該方法調用了內部類Entry的addBefor(E e, Entry<E> entry)方法，意思就是在鏈表的末尾添加一個元素。每一次添加一個元素都要調用一次addBefore方法，在addBefore方法中需要new 一個Entry實例。

addBefore方法實現如下：

不必多說，該方法是一個私有的方法，只能在本類中調用。

當只有列表只有一個header節點時，向列表中添加一個元素的過程如下：

開始就一個header節點，且它的頭結點和next節點都指向的是本身，調用addBefore方法，開始初始化：

初始化後，newEntry指向的是頭結點，之後開始調整節點的位置，

當列表有多個元素時，向列表添加一個元素時的過程如下:

同樣先初始化一個newEntry的節點，不同的是，該節點的previous指向的是最後一個元素

初始化後調整節點的位置：

上述過程其實和方法addLast(Entry e)一樣，都是傳入的header

而addFirst(Entry e)方法傳入的是header.next

在初始化的過程是不一樣的：

調整後：

2) addAll(Collection<? extends E> c)

2.5包含

在方法體內調用了indexOf方法，indexOf（Object o）方法如下：

該方法先判斷傳入的對象是否為空，然後再從前向後遍歷元素，若傳入的對象為空，查找時直到找到列表中為空的元素位置，返回當前位置。

若傳入的對象不為空，循環遍歷查找列表中手否有節點和o相等，若相等則返回當前位置，若沒有，就返回-1。

2.6刪除元素

1）刪除某個元素Entry e

若要刪除的元素為entry1

刪除後：

2)移除所有的元素

該方法中的e可以看做一個不斷移動的指針，因為是雙向循環鏈表，所以當指向header的時候說明已經沒有節點了。

2.7 get方法

1）獲取指定位置的元素

該方法調用entry(index)方法，然後再取值。其中entry(int index)方法和方法indexOf(Object o)方法類似。只是在遍歷時運用了移位的方法，可以看出LinkedList類的特性，既可以從頭開始遍歷 ，又可以從尾向前遍歷

2）獲取最後一個為Obejct o的元素

2.8 set（）方法

該方法目的是用新元素改變原有的元素的值，返回就元素。

2.9 數據複製clone和toArray方法

2)toArray方法

與ArrayList類一樣，LinkedList提供了兩種轉換為數組的方法

toArray()

先判斷出入的數組a的大小是否足夠，若大小不夠則拓展。利用反射，重新實例化了一個大小為size的數組。之後將數組a賦值給數組 result，遍歷鏈表向result中添加的元素。最後判斷數組a的長度是否大於size，若大於則將size位置的內容設置為null。返回a。

 從代碼中可以看出，數組a的length小於等於size時，a中所有元素被覆蓋，被拓展來的空間存儲的內容都是null；若數組a的length的 length大於size，則0至size-1位置的內容被覆蓋，size位置的元素被設置為null，size之後的元素不變。

三、LinkedList與ArrayList比較

1.ArrayList是實現了基於動態數組的數據結構，LinkedList基於鏈表的數據結構。

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

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上更慢