LinkedList的源碼分析

　　LinkedList也和ArrayList一樣實現了List接口，但是它執行插入和刪除操作時比ArrayList更加高效，因為它是基于鏈表的?；阪湵硪矝Q定了它在隨機訪問方面要比ArrayList遜色一點。

　　除此之外，LinkedList還提供了一些可以使其作為棧、隊列、雙端隊列的方法。這些方法中有些彼此之間只是名稱的區別，以使得這些名字在特定的上下文中顯得更加的合適。

　　先看LinkedList類的定義。

　　1 public class LinkedList《E》

　　2 extends AbstractSequentialList《E》

　　3 implements List《E》， Deque《E》， Cloneable， java.io.Serializable

　　LinkedList繼承自AbstractSequenceList、實現了List及Deque接口。其實AbstractSequenceList已經實現了List接口，這里標注出List只是更加清晰而已。AbstractSequenceList提供了List接口骨干性的實現以減少實現List接口的復雜度。Deque接口定義了雙端隊列的操作。

　　LinkedList中之定義了兩個屬性：

　　1 private transient Entry《E》 header = new Entry《E》（null， null， null）;

　　2 private transient int size = 0;

　　size肯定就是LinkedList對象里面存儲的元素個數了。LinkedList既然是基于鏈表實現的，那么這個header肯定就是鏈表的頭結點了，Entry就是節點對象了。一下是Entry類的代碼。

　　1 private static class Entry《E》 {

　　2 E element;

　　3 Entry《E》 next;

　　4 Entry《E》 previous;

　　5

　　6 Entry（E element， Entry《E》 next， Entry《E》 previous） {

　　7 this.element = element;

　　8 this.next = next;

　　9 this.previous = previous;

　　10 }

　　11 }

　　只定義了存儲的元素、前一個元素、后一個元素，這就是雙向鏈表的節點的定義，每個節點只知道自己的前一個節點和后一個節點。

　　來看LinkedList的構造方法。

　　1 public LinkedList（） {

　　2 header.next = header.previous = header;

　　3 }

　　4 public LinkedList（Collection《？ extends E》 c） {

　　5 this（）;

　　6 addAll（c）;

　　7 }

　　LinkedList提供了兩個構造方法。第一個構造方法不接受參數，只是將header節點的前一節點和后一節點都設置為自身（注意，這個是一個雙向循環鏈表，如果不是循環鏈表，空鏈表的情況應該是header節點的前一節點和后一節點均為null），這樣整個鏈表其實就只有header一個節點，用于表示一個空的鏈表。第二個構造方法接收一個Collection參數c，調用第一個構造方法構造一個空的鏈表，之后通過addAll將c中的元素全部添加到鏈表中。來看addAll的內容。

　　1 public boolean addAll（Collection《？ extends E》 c） {

　　2 return addAll（size， c）;

　　3 }

　　4 // index參數指定collection中插入的第一個元素的位置

　　5 public boolean addAll（int index， Collection《？ extends E》 c） {

　　6 // 插入位置超過了鏈表的長度或小于0，報IndexOutOfBoundsException異常

　　7 if （index 《 0 || index 》 size）

　　8 throw new IndexOutOfBoundsException（“Index： ”+index+

　　9 “， Size： ”+size）;

　　10 Object［］ a = c.toArray（）;

　　11 int numNew = a.length;

　　12 // 若需要插入的節點個數為0則返回false，表示沒有插入元素

　　13 if （numNew==0）

　　14 return false;

　　15 modCount++;

　　16 // 保存index處的節點。插入位置如果是size，則在頭結點前面插入，否則獲取index處的節點

　　17 Entry《E》 successor = （index==size ？ header ： entry（index））;

　　18 // 獲取前一個節點，插入時需要修改這個節點的next引用

　　19 Entry《E》 predecessor = successor.previous;

　　20 // 按順序將a數組中的第一個元素插入到index處，將之后的元素插在這個元素后面

　　21 for （int i=0; i《numNew; i++） {

　　22 // 結合Entry的構造方法，這條語句是插入操作，相當于C語言中鏈表中插入節點并修改指針

　　23 Entry《E》 e = new Entry《E》（（E）a［i］， successor， predecessor）;

　　24 // 插入節點后將前一節點的next指向當前節點，相當于修改前一節點的next指針

　　25 predecessor.next = e;

　　26 // 相當于C語言中成功插入元素后將指針向后移動一個位置以實現循環的功能

　　27 predecessor = e;

　　28 }

　　29 // 插入元素前index處的元素鏈接到插入的Collection的最后一個節點

　　30 successor.previous = predecessor;

　　31 // 修改size

　　32 size += numNew;

　　33 return true;

　　34 }

　　構造方法中的調用了addAll（Collection《？ extends E》 c）方法，而在addAll（Collection《？ extends E》 c）方法中僅僅是將size當做index參數調用了addAll（int index，Collection《？ extends E》 c）方法。

　　1 private Entry《E》 entry（int index） {

　　2 if （index 《 0 || index 》= size）

　　3 throw new IndexOutOfBoundsException（“Index： ”+index+

　　4 “， Size： ”+size）;

　　5 Entry《E》 e = header;

　　6 // 根據這個判斷決定從哪個方向遍歷這個鏈表

　　7 if （index 《 （size 》》 1）） {

　　8 for （int i = 0; i 《= index; i++）

　　9 e = e.next;

　　10 } else {

　　11 // 可以通過header節點向前遍歷，說明這個一個循環雙向鏈表，header的previous指向鏈表的最后一個節點，這也驗證了構造方法中對于header節點的前后節點均指向自己的解釋

　　12 for （int i = size; i 》 index; i--）

　　13 e = e.previous;

　　14 }

　　15 return e;

　　16 }