Java集合源碼學習（三）LinkedList分析

前面學習了arraylist的源碼，

數組是順序存儲結構，存儲區間是連續的，占用記憶體嚴重，故空間複雜的很大。

但數組的二分查找時間複雜度小，為o(1)，數組的特點是尋址容易，插入和删除困難。

今天學習另外的一種常用資料結構linkedlist的實作，

linkedlist使用連結清單作為存儲結構，連結清單是線性存儲結構，在記憶體上不是連續的一段空間，

占用記憶體比較寬松，故空間複雜度很小，但時間複雜度很大，達o（n），連結清單的特點是尋址困難，插入和删除容易。

所有的代碼都基于jdk 1.6。

linkedlist繼承了abstractsequentiallist，實作了list，deque，cloneable，serializable 接口，

（1）繼承和實作

繼承abstractsequentiallist類，提供了相關的添加、删除、修改、周遊等功能。

實作list接口，提供了相關的添加、删除、修改、周遊等功能。

實作 deque 接口，即能将linkedlist當作雙端隊列使用，可以用做隊列或者棧

實作了cloneable接口，即覆寫了函數clone()，能被克隆複制，

實作java.io.serializable接口，linkedlist支援序列化，能通過序列化傳輸。

（2）線程安全

linkedlist是非同步的，即線程不安全，如果有多個線程同時通路linkedlist，可能會抛出concurrentmodificationexception異常。

1

2

3

4

<code>final</code> <code>void</code> <code>checkforcomodification() {</code>

<code>        </code><code>if</code> <code>(modcount != expectedmodcount)</code>

<code>        </code><code>throw</code> <code>new</code> <code>concurrentmodificationexception();</code>

<code>    </code><code>}</code>

　　代碼中，modcount記錄了linkedlist結構被修改的次數。iterator初始化時，expectedmodcount=modcount。任何通過iterator修改linkedlist結構的行為都會同時更新expectedmodcount和modcount，使這兩個值相等。通過linkedlist對象修改其結構的方法隻更新modcount。是以假設有兩個線程a和b。a通過iterator周遊并修改linkedlist，而b，與此同時，通過對象修改其結構，那麼iterator的相關方法就會抛出異常

和普通的連結清單不同，雙向連結清單每個節點不止維護指向下一個節點的next指針，還維護着指向上一個節點的previous指針。

（1）内部實作

linkedlist内部使用entry&lt;e&gt;來封裝雙向循環連結清單結點。

linkedlist頭結點的定義:

<code>//頭結點的定義</code>

<code>    </code><code>private</code> <code>transient</code> <code>entry&lt;e&gt; header = </code><code>new</code> <code>entry&lt;e&gt;(</code><code>null</code><code>, </code><code>null</code><code>, </code><code>null</code><code>);</code>

<code>    </code><code>//連結清單的實際長度</code>

<code>    </code><code>private</code> <code>transient</code> <code>int</code> <code>size = </code><code>0</code><code>;</code>

　　entry是一個靜态内部類，

5

6

7

8

9

10

11

<code>private</code> <code>static</code> <code>class</code> <code>entry&lt;e&gt; {</code>

<code>    </code><code>e element;</code>

<code>    </code><code>entry&lt;e&gt; next;</code>

<code>    </code><code>entry&lt;e&gt; previous;</code>

<code>    </code><code>entry(e element, entry&lt;e&gt; next, entry&lt;e&gt; previous) {</code>

<code>        </code><code>this</code><code>.element = element;</code>

<code>        </code><code>this</code><code>.next = next;</code>

<code>        </code><code>this</code><code>.previous = previous;</code>

　　

（2）構造函數

linkedlist内部提供了兩個構造函數，

12

13

<code>/**</code>

<code>    </code><code>* 初始化一個空的list，可以了解為一個雙向循環連結清單</code>

<code>    </code><code>*/</code>

<code>   </code><code>public</code> <code>linkedlist() {</code>

<code>       </code><code>header.next = header.previous = header;</code>

<code>   </code><code>}</code>

<code>   </code><code>/**</code>

<code>    </code><code>* 使用指定的collection構造一個list</code>

<code>   </code><code>public</code> <code>linkedlist(collection&lt;? </code><code>extends</code> <code>e&gt; c) {</code>

<code>   </code><code>this</code><code>();</code>

<code>   </code><code>addall(c);</code>

（1）周遊方式

linkedlist支援多種周遊方式。建議不要采用随機通路的方式去周遊linkedlist，而采用逐個周遊的方式。 (01) 第一種，通過疊代器周遊。即通過iterator去周遊。

(02) 通過快速随機通路周遊linkedlist

(03) 通過另外一種for循環來周遊linkedlist

(04) 通過pollfirst()來周遊linkedlist

(05) 通過polllast()來周遊linkedlist

(06) 通過removefirst()來周遊linkedlist

(07) 通過removelast()來周遊linkedlist

 

周遊linkedlist時，使用removefist()或removelast()效率最高。但用它們周遊時，會删除原始資料；若單純隻讀取，而不删除，應該使用第3種周遊方式。

連結清單的特點是記憶體空間不連續，插入和删除簡單，尋址的時間複雜度較高，随機通路去周遊linkedlist的效率是最低的。

（2）常用方法（從api摘的）

boolean add(e e)  将指定元素添加到此清單的結尾。  void add(int index, e element)  在此清單中指定的位置插入指定的元素。  boolean addall(collection&lt;? extends e&gt; c)  添加指定 collection 中的所有元素到此清單的結尾，順序是指定 collection 的疊代器傳回這些元素的順序。  boolean addall(int index, collection&lt;? extends e&gt; c)  将指定 collection 中的所有元素從指定位置開始插入此清單。  void addfirst(e e)  将指定元素插入此清單的開頭。  void addlast(e e)  void clear()  從此清單中移除所有元素。  object clone()  傳回此 linkedlist 的淺表副本。  boolean contains(object o)  如果此清單包含指定元素，則傳回 true。  iterator&lt;e&gt; descendingiterator()  傳回以逆向順序在此雙端隊列的元素上進行疊代的疊代器。  e element()  擷取但不移除此清單的頭（第一個元素）。  e get(int index)  傳回此清單中指定位置處的元素。  e getfirst()  傳回此清單的第一個元素。  e getlast()  傳回此清單的最後一個元素。  int indexof(object o)  傳回此清單中首次出現的指定元素的索引，如果此清單中不包含該元素，則傳回 -1。  int lastindexof(object o)  傳回此清單中最後出現的指定元素的索引，如果此清單中不包含該元素，則傳回 -1。  listiterator&lt;e&gt; listiterator(int index)  傳回此清單中的元素的清單疊代器（按适當順序），從清單中指定位置開始。  boolean offer(e e)  将指定元素添加到此清單的末尾（最後一個元素）。  boolean offerfirst(e e)  在此清單的開頭插入指定的元素。  boolean offerlast(e e)  在此清單末尾插入指定的元素。  e peek()  e peekfirst()  擷取但不移除此清單的第一個元素；如果此清單為空，則傳回 null。  e peeklast()  擷取但不移除此清單的最後一個元素；如果此清單為空，則傳回 null。  e poll()  擷取并移除此清單的頭（第一個元素）  e pollfirst()  擷取并移除此清單的第一個元素；如果此清單為空，則傳回 null。  e polllast()  擷取并移除此清單的最後一個元素；如果此清單為空，則傳回 null。  e pop()  從此清單所表示的堆棧處彈出一個元素。  void push(e e)  将元素推入此清單所表示的堆棧。  e remove()  擷取并移除此清單的頭（第一個元素）。  e remove(int index)  移除此清單中指定位置處的元素。  boolean remove(object o)  從此清單中移除首次出現的指定元素（如果存在）。  e removefirst()  移除并傳回此清單的第一個元素。  boolean removefirstoccurrence(object o)  從此清單中移除第一次出現的指定元素（從頭部到尾部周遊清單時）。  e removelast()  移除并傳回此清單的最後一個元素。  boolean removelastoccurrence(object o)  從此清單中移除最後一次出現的指定元素（從頭部到尾部周遊清單時）。  e set(int index, e element)  将此清單中指定位置的元素替換為指定的元素。  int size()  傳回此清單的元素數。

雙端隊列是一個限定插入和删除操作的資料結構，具有隊列和棧的性質，

雙端隊列與棧或隊列相比，是一種多用途的資料結構，在容器類庫中有時會用雙端隊列來提供棧和隊列兩種功能。

檢視源碼的實作，可以發現作為隊列和棧時的相關方法。

（1）作為隊列使用

add(e) 内部實作是addlast(e)

offer(e) 入隊，直接傳回add()

remove() 擷取并移除清單第一個元素，和poll()相同，内部調用removefirst()

poll() 出隊 擷取并移除隊頭元素 内部實作是調用removefirst()

element() 傳回清單第一個元素但不移除，内部調用getfirst()

peek() 傳回清單第一個元素但不移除，和element()相同，内部調用getfirst()

（2）作為棧使用

push(e) 入棧 即addfirst(e)

pop() 出棧 即removefirst()

peek() 擷取棧頂元素但不移除 即peekfirst()

（1）主要的節點更新操作

源碼中的兩個私有方法addbefore和remove是維護了節點更新的主要操作，

這一部分主要是資料結構中對連結清單的操作，了解起來比較簡單，

大部分的add、remode等操作都可以通過這兩個方法實作。

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

<code>    </code><code>* 在傳入節點之前插入新的節點元素</code>

<code>   </code><code>private</code> <code>entry&lt;e&gt; addbefore(e e, entry&lt;e&gt; entry) {</code>

<code>   </code><code>//構造一個新的節點</code>

<code>   </code><code>entry&lt;e&gt; newentry = </code><code>new</code> <code>entry&lt;e&gt;(e, entry, entry.previous);</code>

<code>   </code><code>//調整新節點前後節點的指向</code>

<code>   </code><code>newentry.previous.next = newentry;</code>

<code>   </code><code>newentry.next.previous = newentry;</code>

<code>   </code><code>size++;</code>

<code>   </code><code>modcount++;</code>

<code>   </code><code>return</code> <code>newentry;</code>

<code>   </code> 

<code>    </code><code>/**</code>

<code>    </code><code>* 在連結清單中删除這個節點</code>

<code>   </code><code>private</code> <code>e remove(entry&lt;e&gt; e) {</code>

<code>       </code><code>//e等于初始化時的空節點，抛出異常</code>

<code>   </code><code>if</code> <code>(e == header)</code>

<code>       </code><code>throw</code> <code>new</code> <code>nosuchelementexception();</code>

<code>       </code><code>e result = e.element;</code>

<code>       </code><code>/**</code>

<code>        </code><code>* 删除操作就是調整前後結點指針的指向，繞過傳入節點</code>

<code>        </code><code>* 然後再把傳入節點的前後指針以及value都置為null</code>

<code>        </code><code>*/</code>

<code>   </code><code>e.previous.next = e.next;</code>

<code>   </code><code>e.next.previous = e.previous;</code>

<code>       </code><code>e.next = e.previous = </code><code>null</code><code>;</code>

<code>       </code><code>e.element = </code><code>null</code><code>;</code>

<code>   </code><code>size--;</code>

<code>       </code><code>return</code> <code>result;</code>

（2）list疊代器 通過listitr内部類實作

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

<code>private</code> <code>class</code> <code>listitr </code><code>implements</code> <code>listiterator&lt;e&gt; {</code>

<code>  </code><code>private</code> <code>entry&lt;e&gt; lastreturned = header;</code>

<code>  </code><code>private</code> <code>entry&lt;e&gt; next;</code>

<code>  </code><code>private</code> <code>int</code> <code>nextindex;</code>

<code>  </code><code>private</code> <code>int</code> <code>expectedmodcount = modcount;</code>

<code>  </code><code>listitr(</code><code>int</code> <code>index) {</code>

<code>      </code><code>if</code> <code>(index &lt; </code><code>0</code> <code>|| index &gt; size)</code>

<code>      </code><code>throw</code> <code>new</code> <code>indexoutofboundsexception(</code><code>"index: "</code><code>+index+</code>

<code>                          </code><code>", size: "</code><code>+size);</code>

<code>      </code><code>if</code> <code>(index &lt; (size &gt;&gt; </code><code>1</code><code>)) {</code>

<code>      </code><code>next = header.next;</code>

<code>      </code><code>for</code> <code>(nextindex=</code><code>0</code><code>; nextindex&lt;index; nextindex++)</code>

<code>          </code><code>next = next.next;</code>

<code>      </code><code>} </code><code>else</code> <code>{</code>

<code>      </code><code>next = header;</code>

<code>      </code><code>for</code> <code>(nextindex=size; nextindex&gt;index; nextindex--)</code>

<code>          </code><code>next = next.previous;</code>

<code>      </code><code>}</code>

<code>  </code><code>}</code>

<code>  </code><code>public</code> <code>boolean</code> <code>hasnext() {</code>

<code>      </code><code>return</code> <code>nextindex != size;</code>

<code>  </code><code>public</code> <code>e next() {</code>

<code>      </code><code>checkforcomodification();</code>

<code>      </code><code>if</code> <code>(nextindex == size)</code>

<code>      </code><code>throw</code> <code>new</code> <code>nosuchelementexception();</code>

<code>      </code><code>lastreturned = next;</code>

<code>      </code><code>next = next.next;</code>

<code>      </code><code>nextindex++;</code>

<code>      </code><code>return</code> <code>lastreturned.element;</code>

<code>  </code><code>public</code> <code>boolean</code> <code>hasprevious() {</code>

<code>      </code><code>return</code> <code>nextindex != </code><code>0</code><code>;</code>

<code>  </code><code>public</code> <code>e previous() {</code>

<code>      </code><code>if</code> <code>(nextindex == </code><code>0</code><code>)</code>

<code>      </code><code>lastreturned = next = next.previous;</code>

<code>      </code><code>nextindex--;</code>

<code>  </code><code>public</code> <code>int</code> <code>nextindex() {</code>

<code>      </code><code>return</code> <code>nextindex;</code>

<code>  </code><code>public</code> <code>int</code> <code>previousindex() {</code>

<code>      </code><code>return</code> <code>nextindex-</code><code>1</code><code>;</code>

<code>  </code><code>public</code> <code>void</code> <code>remove() {</code>

<code>          </code><code>checkforcomodification();</code>

<code>          </code><code>entry&lt;e&gt; lastnext = lastreturned.next;</code>

<code>          </code><code>try</code> <code>{</code>

<code>              </code><code>linkedlist.</code><code>this</code><code>.remove(lastreturned);</code>

<code>          </code><code>} </code><code>catch</code> <code>(nosuchelementexception e) {</code>

<code>              </code><code>throw</code> <code>new</code> <code>illegalstateexception();</code>

<code>          </code><code>}</code>

<code>      </code><code>if</code> <code>(next==lastreturned)</code>

<code>              </code><code>next = lastnext;</code>

<code>          </code><code>else</code>

<code>      </code><code>lastreturned = header;</code>

<code>      </code><code>expectedmodcount++;</code>

<code>  </code><code>public</code> <code>void</code> <code>set(e e) {</code>

<code>      </code><code>if</code> <code>(lastreturned == header)</code>

<code>      </code><code>throw</code> <code>new</code> <code>illegalstateexception();</code>

<code>      </code><code>lastreturned.element = e;</code>

<code>  </code><code>public</code> <code>void</code> <code>add(e e) {</code>

<code>      </code><code>addbefore(e, next);</code>

<code>  </code><code>final</code> <code>void</code> <code>checkforcomodification() {</code>

<code>      </code><code>if</code> <code>(modcount != expectedmodcount)</code>

<code>      </code><code>throw</code> <code>new</code> <code>concurrentmodificationexception();</code>

fail-fast，快速失敗是java集合的一種錯誤檢測機制。

當多個線程對集合進行結構上的改變的操作時，有可能會産生fail-fast機制。

記住是有可能，而不是一定。例如：假設存在兩個線程（線程1、線程2），線程1通過iterator在周遊集合a中的元素，在某個時候線程2修改了集合a的結構（是結構上面的修改，而不是簡單的修改集合元素的内容），那麼這個時候程式就會抛出 concurrentmodificationexception 異常，進而産生fail-fast機制。

arraylist是一個基于數組的結構，裡面的節點互相之間沒有特别的聯系，預設的大小是10，最大大小是integer.max_value - 8。

當大小不夠時會自動增長，它可以通過get，set來直接擷取、修改某一個節點資料。

linkedlist是一個基于雙向連結清單的結構，每一個節點都有兩個指針來分别指向上一個節點和下一個節點。它是可變長度的。

這兩個實作類的差別在于，arraylist的get()/set()效率比linkedlist高，而linkedlist的add()/remove()效率比arraylist高。

具體來說：數組申請一塊連續的記憶體空間，是在編譯期間就确定大小的，運作時期不可動态改變，但為什麼arraylist可以改變大小呢，

因為在add如果超過了設定的大小就會建立一個新的更大的（增長率好像是0.5）arraylist，

然後将原來的list複制到新的list中，并将位址指向新的list，舊的list被gc回收，顯然這是非常消耗記憶體而且效率非常低的。

但是由于它申請的記憶體空間是連續的，可以直接通過下标來擷取需要的資料，時間複雜度為o(1)，而連結清單則是o(n)，

而連結清單結構不一樣，它可以動态申請記憶體空間。在需要加入的節點的上一個節點的指針解開并指向新加節點，再将新加節點的指針指向後一個節點即可。速度很快的。

是以說arraylist适合查詢，linkedlist适合增删。