Java集合架構剖析(4)——LinkedList

• LinkedList是一個繼承與AbatractSequentialList的雙向連結清單。它也可以被當作堆棧、隊列或雙端隊列進行操作。
• LinkedList實作了List接口，能對它進行隊列操作。
• LinkedList實作了Deque接口，即能将LinkedList當作雙端隊列使用。
• LinkedList實作了java.io.Serializable接口，這意味着LinkedList支援序列化，能通過序列化去傳輸。

順便說一下LinkedList的父類AbstractSequentialList

雖然LinkedList沒有實作RandomAccess接口，但是其父類AbstractSequentialList實作了get、set、add、remove方法

這些接口都是随機通路List的，LinkedList是雙向連結清單，既然它繼承與AbstractSequentialList，就相當于已經實作了“get(int index)”這些接口，可以支援随機通路了。

此外，如果我們需要通過AbstractSequentialList實作一個自己的清單，隻需要擴充此類，并提供listIterator()和size()方法的實作即可。若要實作不可修改的清單，則需要實作清單疊代器的hashNext、next、hashPrevious、previous和index方法即可。

下面先總覽一下LinkedList的構造函數和API:

LinkedList包含三個重要的成員：first、last和size：first是雙向連結清單的表頭，last是雙向連結清單的尾節點，size是雙向連結清單中的節點個數。

這裡先說一下

transient關鍵字

的用法：

一個對象隻要實作了Serilizable接口，這個對象就可以被序列化，java的這種序列化模式為開發者提供了很多便利，可以不必關系具體序列化的過程，

隻要這個類實作了Serilizable接口，這個的所有屬性和方法都會自動序列化。但是有種情況是有些屬性是不需要序列号的，是以就用到這個關鍵字。

隻需要實作Serilizable接口，将不需要序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。

源碼剖析

屬性

其中Node是一個内部類：

參數為前一個節點，元素，後一個節點

構造函數

依然是規範了兩種構造函數

頭尾節點的添加

其中的判定

f==null

表示此時的連結清單為空， modCount為Modified Count的縮寫，表示修改次數。

頭尾節點的删除

public接口，供外部調用

擷取頭尾節點

判定是否在連結清單中，以及index擷取

循環周遊，O(1)時間複雜度

add、remove

都是已元素為參數的，并且滿足一個即傳回

addAll、clear

随機位置操作

都是循環周遊的方式，是以如果用随機位置循環來周遊LinkedList的話，那真是腦門被門夾了。

搜尋操作

Queue操作

DeQueue操作

疊代器

LinkedList的疊代器分為雙向疊代器（ListItr）和前向疊代器（DescendingIterator）

雙向疊代器

都是連結清單的基本操作

前向疊代器

前向疊代器的next其實擷取的是previous

總結

1. LinkedList是通過雙向連結清單去實作的。 從LinkedList的實作方式中可以看出，它不存在容量不足的問題，因為是連結清單
2. LinkedList實作java.io.Serializable的方式。當寫入到輸出流時，先寫入“容量”，再依次寫出“每一個元素”；當讀出輸入流時，先讀取“容量”，再依次讀取“每一個元素”。
3. LinkdedList的克隆函數，即是将全部元素克隆到一個新的LinkedList中。
4. 由于LinkedList實作了Deque，而Deque接口定義了在雙端隊列兩端通路元素的方法。提供插入、移除和檢查元素的方法。
5. LinkedList可以作為FIFO（先進先出）的隊列，作為FIFO的隊列時，下标的方法等價：

   

   1. LinkedList可以作為LIFO（後進先出）的棧，作為LIFO的棧時，下表的方法等價：

      

周遊方式

1 .for方式

2. 疊代器方式

3. 快速随機通路

LinkedList适合for和疊代器，如果用快速随機通路的話那麼複雜度是O(n)

再次強調一遍不要用随機通路周遊LinkedList