LinkedList 的實現原理淺析

本文簡單分析一下JDK1.7的LinkedList源碼，看一下其內部的結構以及典型方法的實現~

LinkedList內部結構

查看LinkedList的源碼，發現其繼承自AbstractSequentialList，實現了List，Deque，Cloneable以及Serializable介面，如：

也就意味著：

LinkedList 是一個繼承於AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。

LinkedList 實現 List 介面，能對它進行列表操作。

LinkedList 實現 Deque 介面，即能將LinkedList當作雙端隊列使用。

LinkedList 實現了Cloneable介面，即覆蓋了函數clone()，能克隆。

LinkedList 實現java.io.Serializable介面，這意味著LinkedList支持序列化，能通過序列化去傳輸。

從上述代碼可以看出，LinkedList中有size，first以及last全局變數，其作用分別是：

size -- 存放當前鏈表有多少個節點。

first -- 指向鏈表的第一個節點的引用

last -- 指向鏈表的最後一個節點的引用

其中，Node是內部類，內容如下：

從上述代碼可以看出，

一個節點除了包含元素內容之外，同時包含前一個節點和後一個節點的引用~

各個節點通過指定前一個節點和後一個節點，最終形成了一個鏈表~

代碼示例：

輸出結果：

debug查看LinkedList的結構如下：

形成了一個鏈表

方法 add 的實現

源代碼

add方法會調用linkLast方法，會在鏈表尾端添加節點~

linkLast方法步驟獲取原來的last節點，然後創建一個新的節點，其prev為原來的last節點，其next節點為null將last只想新的節點如果原來的last節點為null，其實就是還沒有元素，那麼新的節點同樣也是first節點；如果不為null，則原來的last節點的next就是新的節點因為有新元素加入，size加1，且修改次數加1（modCount++）

方法 addAll 的實現

源代碼

addAll在LinkedList內部其實就是調用了方法addAll(int index, Collection

方法addAll(int index, Collection

方法addAll(int index, Collection

檢查指定index是否合理

index的有效位置是[0,size]

定義pred和succ節點，並根據index的大小確定pred和succ節點

對Collection轉換成數組（Object[] a = c.toArray()）的元素進行循環遍歷，確定first、pred.next等節點信息

檢查succ是否為空，如果為null，則表示目前的pred節點就是最後一個了，將last節點指向pred；反之，如果不為null，則將prev的next節點指向succ，同時succ的prev節點指向pred。

最後修改size和modCount的值

上述是往指定位置添加多個元素，那麼，往指定位置添加單個元素add(int index, E element) 就變得很簡單了。

方法add(int index, E element)

該方法包含如下兩個步驟

檢查指定index的值是否有效[0,size]

如果index == size 則使用linkLast添加在尾部；如果index ！= size， 則使用linkBefore將新元素添加在指定位置之前~

linkBefore方法如下

本文上述已經講述了linkLast，linkBefore的方法實現思路類似，這裡就不再具體給出解釋了。

此外，LinkedList還提供了addFirst以及addLast方法，分別用於將元素插在列表頭部和尾部~

其中，linkFirst和linkLast方法如下：

方法 remove 的實現

LinkedList支持多種刪除元素的方法~

一起來看看具體是怎麼樣的~

無參數remove方法

無參數的remove方法其實就是調用了removeFirst方法，也就是移除first元素~

removeFirst方法

removeFirst使用了unlinkFirst方法來移除元素~

unlinkFirst方法處理主要包含如下幾個步驟：

獲取first元素值，然後獲取first的next元素

將first節點指向next，同時原來的first節點的屬性值置為null（包括item和next）

如果next節點（原first節點的nex節點）為null，則將last置為null值；如果不為null，則將next節點的prev屬性置為null

然後修正元素個數以及修改次數（size和modCount）

同樣，也存在移除尾節點的方法removeLast

removeLast方法

其使用了unlinkLast方法實現

unlinked方法的實現與unlinkedFirst的方法思路類似，就不在這裡一一說明了~

方法remove(int index)

按照指定位置移除元素，主要包含如下幾個部分：

檢查index是否有效

通過node(index)查找index位置下的節點

從上述代碼可以看出，方法node(int index)中

先判斷index和中間點（size >>1）位置的大小。如果index < (size >> 1), 那麼按下標從小到大查找；否則，按下標從大到小查找~

使用unlink(Node x)修改鏈表的連接關係，達到移除元素的效果

方法remove(Object o)

按照指定對象的移除，在代碼中，區分刪除的元素是否為null值，然後從first開始遍歷鏈表，如果元素值和刪除的值內容一致，則調用unlink方法移除元素~

方法 indexOf 的實現

源代碼

從上述代碼可以看出：

LinkedList的indexOf實現區分null和非null值。從first節點開始遍歷，如果找到符合條件的元素，則返回元素所在的下標值。如果沒有找到，則返回-1~

與之對應的還有lastIndexOf方法，該方法和indexOf的思路一致，區別就是，lastIndexOf是以last節點開始往前尋找~

方法 contains 的實現

源代碼

從上述代碼可以看出，contains方法內調用了indexOf方法，然後採用獲取的結果與-1比較，如果不相等表示有匹配的元素，否則表示沒有符合條件的元素~

方法 clear 的實現

源代碼

clear方法，從first開始遍歷鏈表，將元素的item、prev和nex屬性置為null值，然後將first和last置為null。同時將size置為0，修改次數加1（modCount+）

方法 get 的實現

LinkedList支持按索引查找以及獲取first和last元素的操作~ 如：

方法get(int index)的實現

此方法包含兩個步驟：

檢查指定的index的值是否有效

調用node(index)獲取節點，返回值node(index).item即可

方法getFirst

方法getFirst獲取first節點的值item即可，得先判斷first是否為空~

方法getLast

方法getLast獲取last節點的值item即可，得先判斷last是否為空~

方法 listIterator 的實現

源代碼

其使用了內部類ListItr來實現，ListItr類內容如下：

listIterator介面繼承自Iterator介面，具備更多的方法，如add，set，previous等等

ListIterator示例

輸出結果：

方法descendingIterator的實現

源代碼

descendingIterator與Iterator的區別在於，Iterator是從first開始往後遍歷；而descendingIterator是從last開始往前遍歷；

Iterator和descendingIterator示例：

輸出結果：

方法 toArray 的實現

源代碼

從first節點開始，依次遍歷，然後得到一個數組對象~

其它的方法就不一一列舉了。

本次LinkedList源碼閱讀分析就到這裡，有興趣的朋友可以實際去讀一下，讀源碼，懂思想，還是很不錯的~

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！