這篇教學延續前一篇 List家族 – ArrayList篇，是繼續介紹 List家族中個性比較獨立的長者，他們各自散落在記憶體空間儲存著程式設計師交付給他們的資料，他們手上同時也有下一個LinkedList 節點的聯絡方式(變形的LinkedList 還可以有上一個節點的聯絡方式，稱之為雙向鏈結)，就這樣串起所有的節點。是不是有種小說的感覺XDD，接下來我們就進入LinkedList的世界吧。
目錄
LinkedList 的種類
單向鏈結串列 (Single Link List)
由節點(Node)所組成的有序串列，節點包含資料欄位外，還儲存了Link欄位，這個欄位用來儲存下一個節點所在的記憶體位址(address)。
雙向鏈結串列 (Double Link List)
也是由節點(Node)所組成的，不過節點的內容除了與單向鏈結串列一樣的資料欄位與下一個節點所在記憶體位置外，還多儲存了上一個節點所在的記憶體位置。
環狀鏈結串列 (Circular Link List)
當單向鏈結串列最後一個Node的Link欄位指回第一個Node，如此一來就好像串成一個圓圈，稱之為環狀鏈結串列。
LinkedList常用操作圖解與程式碼巡禮
LinkedList 建構子(Constructor)
首先看一下LinkedList類別的繼承關係，與ArrayList不一樣的是LinkedList實作了 Deque介面，除此之外之乎一致。既然有繼承List介面，那麼顯然LinkedList也必須要實作List介面定義出來的介面方法。
List介面有定義哪一些介面方法呢？ 點這裡回去查看
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
}
再來我們關心LinkedList類別的生命起始，也就是建構子。建構子有兩個，一個是無參數的建構子，沒有做任何事情，另一個是可以傳入一個Collection當做參數。這裡比較值得提到的是LinkedList 用來儲存資料的物件是 Node<E>，請看下面一段程式碼的第1,2行 Node<E> first與 Node<E> last，我們來看一下Node<E> 的結構是什麼。
transient Node<E> first;
transient Node<E> last;
/*** Constructs an empty list. */
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
Node 結構的程式碼位於LinkedList的第970行，他是一個私有的(private)靜態的(static)類別，先不用擔心這兩個名詞，暫時不管他，不過我們目前知道類別(class)就應該會有生命的起點，也就是建構子(Constructor)，現階段我們比較關心Constructor。
先來看一下這個類別有什麼參數(Variable)，
“E item” 是要儲存的結構，
“Node<E> next” 是指向下一個Node，
“Node<E> prev”是指向前一個Node。
而Node的建構子聲明，如果要創造一個Node 傳入的參數要有前一個 Node、元素、與下一個Node，分別為
。
到這裡我們來思考一下JDK提供的LinkedList是屬於三種基本LinkedList的哪一種？
答案就是雙向鏈結(Double LinkedList)。
LinkedList 新增 (add)
這裡的新增(add), 刪除(remove), 查詢(get) 所描述的時間複雜度(time complexity)都是指這個行為完成的時間複雜度，並不包含要做這個行為前所做的前置條件。
首先我們先用簡單的圖解來對LinkedList的新增有些基本的了解。
接下來我們來追蹤LinkedList在JDK 的程式碼，LinkedList的 add(e) ，這是把元素加到整個LinkedList最後面的方法。可以看到 add() 方法內會呼叫 linkLast(e) 方法。而 linkLast()方法的流程是這樣的，把LinkedList最後一個 Node last，指派給 Node l ，接著創造一個新Node 參數名是 newNode，此時要傳入這個Node的資料是前一個Node的位置 -> l 、自己的元素 e、還有下一個Node的位置，不過這裡沒有下一個Node，因為新增加的這個Node就是目前最後一個Node。
接下來把newNode 指派成為 last ，最後別忘紀要把 l 的下一個Node指向給 newNode ，才不會出現斷鏈現象喔。
✪Tips : 程式碼中的 last有點抽象不太好理解，可以把它想像成一個標籤，代表的是整個 LinkedList 最後一個元素。
LinkedList 刪除 (remove)
跟新增元素一樣，我們先來看一下圖解說明，可以更容易了解LinkedList刪除的作法究竟是怎麼達成的。
再來就是來手把手的追蹤程式碼啦。
LinkedList刪除 remove(o) 看到第 364行，這裡的 for迴圈是找尋要刪除的 Object o 目標，當找到後就會進行 unlink(x) 的行為 。
接著進入unlink的方法，unlink(x) 會先將 x的下一個Node (x.next) 打上一個標籤 next ，也把 x的上一個Node (x.prev) 打上一個標籤 prev ，接下來開始進行判斷。若 prev這個標籤是 null (其實就代表當前要刪除的這個Node是整個LinkedList的第一個Node)則把 first指向這個 next標籤的位置 ，如果不是 null 那麼就將 x Node 的上一個Node (x.prev) 指向 next 這個Node ，接著把 x.prev這個指標設為 null 回收 。
同理，一樣判斷 next 是否為null，若是null則直接讓 last這個標籤指向 prev，若不是null 就將 x Node 下一個Node (x.next) 指向 prev 這個Node，接著回收 x.next 指標。
最後就是把 x.item 也回收 
，整體的LinkedList size 減一，modCount加一，如此一來整個x Node 就被回收了。
LinkedList 讀取 (get)
來到讀取的階段，LinkedList的讀取是透過傳入要取得的index 來取得資料，可以看到第477行呼叫了 node(index) 這一個方法，進入到這個方法後可以看到這裡採用一個減少搜尋的技巧，如果要找的 index 小於 size的一半那就從LinkedList的前頭找，反之如果要找的index大於 size的一半那就從尾端開始找。再來就是一個 for迴圈走到指定的index後回傳該index 的Node。
下一篇的教學我們要統整現階段我們所學會的兩個List家族資料結構 ArrayList與LinkedList 的應用與他們各種方法(add, remove, get) 操作所花費的時間，也就是俗稱的時間複雜度(time complexity)。