電子發燒友App
LinkedList也和ArrayList一樣實現了List接口，但是它執行插入和刪除操作時比ArrayList更加高效，因為它是基于鏈表的。基于鏈表也決定了它在隨機訪問方面要比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 }
結合上面代碼中的注釋及雙向循環鏈表的知識，應該很容易理解LinkedList構造方法所涉及的內容。下面開始分析LinkedList的其他方法。
add（E e）
1 public boolean add（E e） {
2 addBefore（e， header）;
3 return true;
4 }
從上面的代碼可以看出，add（E e）方法只是調用了addBefore（E e，Entry《E》 entry）方法，并且返回true。
addBefore（E e，Entry《E》 entry）
1 private Entry《E》 addBefore（E e， Entry《E》 entry） {
2 Entry《E》 newEntry = new Entry《E》（e， entry， entry.previous）;
3 newEntry.previous.next = newEntry;
4 newEntry.next.previous = newEntry;
5 size++;
6 modCount++;
7 return newEntry;
8 }
addBefore（E e，Entry《E》 entry）方法是個私有方法，所以無法在外部程序中調用（當然，這是一般情況，你可以通過反射上面的還是能調用到的）。
addBefore（E e，Entry《E》 entry）先通過Entry的構造方法創建e的節點newEntry（包含了將其下一個節點設置為entry，上一個節點設置為entry.previous的操作，相當于修改newEntry的“指針”），之后修改插入位置后newEntry的前一節點的next引用和后一節點的previous引用，使鏈表節點間的引用關系保持正確。之后修改和size大小和記錄modCount，然后返回新插入的節點。
總結，addBefore（E e，Entry《E》 entry）實現在entry之前插入由e構造的新節點。而add（E e）實現在header節點之前插入由e構造的新節點。
add（int index，E e）
1 public void add（int index， E element） {
2 addBefore（element， （index==size ？ header ： entry（index）））;
3 }
也是調用了addBefore（E e，Entry《E》 entry）方法，只是entry節點由index的值決定。
構造方法，addAll（Collection《？ extends E》 c），add（E e），addBefor（E e，Entry《E》 entry）方法可以構造鏈表并在指定位置插入節點，為了便于理解，下面給出插入節點的示意圖。
addFirst（E e）
1 public void addFirst（E e） {
2 addBefore（e， header.next）;
3 }
addLast（E e）
1 public void addLast（E e） {
2 addBefore（e， header）;
3 }
看上面的示意圖，結合addBefore（E e，Entry《E》 entry）方法，很容易理解addFrist（E e）只需實現在header元素的下一個元素之前插入，即示意圖中的一號之前。addLast（E e）只需在實現在header節點前（因為是循環鏈表，所以header的前一個節點就是鏈表的最后一個節點）插入節點（插入后在2號節點之后）。
clear（）
1 public void clear（） {
2 Entry《E》 e = header.next;
3 // e可以理解為一個移動的“指針”，因為是循環鏈表，所以回到header的時候說明已經沒有節點了
4 while （e ！= header） {
5 // 保留e的下一個節點的引用
6 Entry《E》 next = e.next;
7 // 接觸節點e對前后節點的引用
8 e.next = e.previous = null;
9 // 將節點e的內容置空
10 e.element = null;
11 // 將e移動到下一個節點
12 e = next;
13 }
14 // 將header構造成一個循環鏈表，同構造方法構造一個空的LinkedList
15 header.next = header.previous = header;
16 // 修改size
17 size = 0;
18 modCount++;
19 }
上面代碼中的注釋已經足以解釋這段代碼的邏輯，需要注意的是提到的“指針”僅僅是概念上的類比，Java并不存在“指針”的概念，而只有引用，為了便于理解所以部分說明使用了“指針”。
contains（Object o）
1 public boolean contains（Object o） {
2 return indexOf（o） ！= -1;
3 }
僅僅只是判斷o在鏈表中的索引。先看indexOf（Object o）方法。
1 public int indexOf（Object o） {
2 int index = 0;
3 if （o==null） {
4 for （Entry e = header.next; e ！= header; e = e.next） {
5 if （e.element==null）
6 return index;
7 index++;
8 }
9 } else {
10 for （Entry e = header.next; e ！= header; e = e.next） {
11 if （o.equals（e.element））
12 return index;
13 index++;
14 }
15 }
16 return -1;
17 }
indexOf（Object o）判斷o鏈表中是否存在節點的element和o相等，若相等則返回該節點在鏈表中的索引位置，若不存在則放回-1。
contains（Object o）方法通過判斷indexOf（Object o）方法返回的值是否是-1來判斷鏈表中是否包含對象o。
element（）
1 public E element（） {
2 return getFirst（）;
3 }
getFirst（）
1 public E getFirst（） {
2 if （size==0）
3 throw new NoSuchElementException（）;
4 return header.next.element;
5 }
element（）方法調用了getFirst（）返回鏈表的第一個節點的元素。為什么要提供功能一樣的兩個方法，像是包裝了一下名字？其實這只是為了在不同的上下文“語境”中能通過更貼切的方法名調用罷了。
get（int index）
1 public E get（int index） {
2 return entry（index）.element;
3 }
get（int index）方法用于獲得指定索引位置的節點的元素。它通過entry（int index）方法獲取節點。entry（int index）方法遍歷鏈表并獲取節點，在上面有說明過，不再陳述。
set（int index，E element）
1 public E set（int index， E element） {
2 Entry《E》 e = entry（index）;
3 E oldVal = e.element;
4 e.element = element;
5 return oldVal;
6 }
先獲取指定索引的節點，之后保留原來的元素，然后用element進行替換，之后返回原來的元素。
getLast（）
1 public E getLast（） {
2 if （size==0）
3 throw new NoSuchElementException（）;
4 return header.previous.element;
5 }
getLast（）方法和getFirst（）方法類似，只是獲取的是header節點的前一個節點的元素。因為是循環鏈表，所以header節點的前一節點就是鏈表的最后一個節點。
lastIndexOf（Object o）
1 public int lastIndexOf（Object o） {
2 int index = size;
3 if （o==null） {
4 for （Entry e = header.previous; e ！= header; e = e.previous） {
5 index--;
6 if （e.element==null）
7 return index;
8 }
9 } else {
10 for （Entry e = header.previous; e ！= header; e = e.previous） {
11 index--;
12 if （o.equals（e.element））
13 return index;
14 }
15 }
16 return -1;
17 }
因為查找的是last index，即最后一次出現的位置，所以采用由后向前的遍歷方式。因為采用了有后向前的遍歷，所以index被賦值為size，并且循環體內執行時都進行減操作。分兩種情況判斷是否存在，分別是null和不為空。
offer（E e）
1 public boolean offer（E e） {
2 return add（e）;
3 }
在鏈表尾部插入元素。
offerFirst（E e）
1 public boolean offerFirst（E e） {
2 addFirst（e）;
3 return true;
4 }
在鏈表開頭插入元素。
offerLast（E e）
1 public boolean offerLast（E e） {
2 addLast（e）;
3 return true;
4 }
在鏈表末尾插入元素。
上面這三個方法都只是調用了相應的add方法，同樣只是提供了不同的方法名在不同的語境下使用。
peek（）
1 public E peek（） {
2 if （size==0）
3 return null;
4 return getFirst（）;
5 }
peekFirst（）
1 public E peekFirst（） {
2 if （size==0）
3 return null;
4 return getFirst（）;
5 }
peekLast（）
1 public E peekLast（） {
2 if （size==0）
3 return null;
4 return getLast（）;
5 }
上面的三個方法也很簡單，只是調用了對應的get方法。
poll（）
1 public E poll（） {
2 if （size==0）
3 return null;
4 return removeFirst（）;
5 }
pollFirst（）
1 public E pollFirst（） {
2 if （size==0）
3 return null;
4 return removeFirst（）;
5 }
pollLast（）
1 public E pollLast（） {
2 if （size==0）
3 return null;
4 return removeLast（）;
5 }
poll相關的方法都是獲取并移除某個元素。都是和remove操作相關。
pop（）
1 public E pop（） {
2 return removeFirst（）;
3 }
push（E e）
1 public void push（E e） {
2 addFirst（e）;
3 }
這兩個方法對應棧的操作，即彈出一個元素和壓入一個元素，僅僅是調用了removeFirst（）和addFirst（）方法。
下面集中看remove相關操作的方法。
remove（）
1 public E remove（） {
2 return removeFirst（）;
3 }
remove（int index）
1 public E remove（int index） {
2 return remove（entry（index））;
3 }
remove（Object o）
1 public boolean remove（Object o） {
2 if （o==null） {
3 for （Entry《E》 e = header.next; e ！= header; e = e.next） {
4 if （e.element==null） {
5 remove（e）;
6 return true;
7 }
8 }
9 } else {
10 for （Entry《E》 e = header.next; e ！= header; e = e.next） {
11 if （o.equals（e.element）） {
12 remove（e）;
13 return true;
14 }
15 }
16 }
17 return false;
18 }
removeFirst（）
1 public E removeFirst（） {
2 return remove（header.next）;
3 }
removeLast（）
1 public E removeLast（） {
2 return remove（header.previous）;
3 }
removeFirstOccurrence（）
1 public boolean removeFirstOccurrence（Object o） {
2 return remove（o）;
3 }
removeLastOccurence（）
1 public boolean removeLastOccurrence（Object o） {
2 if （o==null） {
3 for （Entry《E》 e = header.previous; e ！= header; e = e.previous） {
4 if （e.element==null） {
5 remove（e）;
6 return true;
7 }
8 }
9 } else {
10 for （Entry《E》 e = header.previous; e ！= header; e = e.previous） {
11 if （o.equals（e.element）） {
12 remove（e）;
13 return true;
14 }
15 }
16 }
17 return false;
18 }
幾個remove方法最終都是調用了一個私有方法：remove（Entry《E》 e），只是其他簡單邏輯上的區別。下面分析remove（Entry《E》 e）方法。
1 private E remove（Entry《E》 e） {
2 if （e == header）
3 throw new NoSuchElementException（）;
4 // 保留將被移除的節點e的內容
5 E result = e.element;
6 // 將前一節點的next引用賦值為e的下一節點
7 e.previous.next = e.next;
8 // 將e的下一節點的previous賦值為e的上一節點
9 e.next.previous = e.previous;
10 // 上面兩條語句的執行已經導致了無法在鏈表中訪問到e節點，而下面解除了e節點對前后節點的引用
11 e.next = e.previous = null;
12 // 將被移除的節點的內容設為null
13 e.element = null;
14 // 修改size大小
15 size--;
16 modCount++;
17 // 返回移除節點e的內容
18 return result;
19 }
clone（）
1 public Object clone（） {
2 LinkedList《E》 clone = null;
3 try {
4 clone = （LinkedList《E》） super.clone（）;
5 } catch （CloneNotSupportedException e） {
6 throw new InternalError（）;
7 }
8 clone.header = new Entry《E》（null， null， null）;
9 clone.header.next = clone.header.previous = clone.header;
10 clone.size = 0;
11 clone.modCount = 0;
12 for （Entry《E》 e = header.next; e ！= header; e = e.next）
13 clone.add（e.element）;
14 return clone;
15 }
調用父類的clone（）方法初始化對象鏈表clone，將clone構造成一個空的雙向循環鏈表，之后將header的下一個節點開始將逐個節點添加到clone中。最后返回克隆的clone對象。
toArray（）
1 public Object［］ toArray（） {
2 Object［］ result = new Object［size］;
3 int i = 0;
4 for （Entry《E》 e = header.next; e ！= header; e = e.next）
5 result［i++］ = e.element;
6 return result;
7 }
創建大小和LinkedList相等的數組result，遍歷鏈表，將每個節點的元素element復制到數組中，返回數組。
toArray（T［］ a）
1 public 《T》 T［］ toArray（T［］ a） {
2 if （a.length 《 size）
3 a = （T［］）java.lang.reflect.Array.newInstance（
4 a.getClass（）.getComponentType（）， size）;
5 int i = 0;
6 Object［］ result = a;
7 for （Entry《E》 e = header.next; e ！= header; e = e.next）
8 result［i++］ = e.element;
9 if （a.length 》 size）
10 a［size］ = null;
11 return a;
12 }
先判斷出入的數組a的大小是否足夠，若大小不夠則拓展。這里用到了發射的方法，重新實例化了一個大小為size的數組。之后將數組a賦值給數組result，遍歷鏈表向result中添加的元素。最后判斷數組a的長度是否大于size，若大于則將size位置的內容設置為null。返回a。
從代碼中可以看出，數組a的length小于等于size時，a中所有元素被覆蓋，被拓展來的空間存儲的內容都是null；若數組a的length的length大于size，則0至size-1位置的內容被覆蓋，size位置的元素被設置為null，size之后的元素不變。
為什么不直接對數組a進行操作，要將a賦值給result數組之后對result數組進行操作？
---------------------------------------------------------------------------------------------------------------------------------
LinkedList的Iterator
除了Entry，LinkedList還有一個內部類：ListItr。
ListItr實現了ListIterator接口，可知它是一個迭代器，通過它可以遍歷修改LinkedList。
在LinkedList中提供了獲取ListItr對象的方法：listIterator（int index）。
1 public ListIterator《E》 listIterator（int index） {
2 return new ListItr（index）;
3 }
該方法只是簡單的返回了一個ListItr對象。
LinkedList中還有通過集成獲得的listIterator（）方法，該方法只是調用了listIterator（int index）并且傳入0。
下面詳細分析ListItr。
1 private class ListItr implements ListIterator《E》 {
2 // 最近一次返回的節點，也是當前持有的節點
3 private Entry《E》 lastReturned = header;
4 // 對下一個元素的引用
5 private Entry《E》 next;
6 // 下一個節點的index
7 private int nextIndex;
8 private int expectedModCount = modCount;
9 // 構造方法，接收一個index參數，返回一個ListItr對象
10 ListItr（int index） {
11 // 如果index小于0或大于size，拋出IndexOutOfBoundsException異常
12 if （index 《 0 || index 》 size）
13 throw new IndexOutOfBoundsException（“Index： ”+index+
14 “， Size： ”+size）;
15 // 判斷遍歷方向
16 if （index 《 （size 》》 1）） {
17 // next賦值為第一個節點
18 next = header.next;
19 // 獲取指定位置的節點
20 for （nextIndex=0; nextIndex《index; nextIndex++）
21 next = next.next;
22 } else {
23 // else中的處理和if塊中的處理一致，只是遍歷方向不同
24 next = header;
25 for （nextIndex=size; nextIndex》index; nextIndex--）
26 next = next.previous;
27 }
28 }
29 // 根據nextIndex是否等于size判斷時候還有下一個節點（也可以理解為是否遍歷完了LinkedList）
30 public boolean hasNext（） {
31 return nextIndex ！= size;
32 }
33 // 獲取下一個元素
34 public E next（） {
35 checkForComodification（）;
36 // 如果nextIndex==size，則已經遍歷完鏈表，即沒有下一個節點了（實際上是有的，因為是循環鏈表，任何一個節點都會有上一個和下一個節點，這里的沒有下一個節點只是說所有節點都已經遍歷完了）
37 if （nextIndex == size）
38 throw new NoSuchElementException（）;
39 // 設置最近一次返回的節點為next節點
40 lastReturned = next;
41 // 將next“向后移動一位”
42 next = next.next;
43 // index計數加1
44 nextIndex++;
45 // 返回lastReturned的元素
46 return lastReturned.element;
47 }
48
49 public boolean hasPrevious（） {
50 return nextIndex ！= 0;
51 }
52 // 返回上一個節點，和next（）方法相似
53 public E previous（） {
54 if （nextIndex == 0）
55 throw new NoSuchElementException（）;
56
57 lastReturned = next = next.previous;
58 nextIndex--;
59 checkForComodification（）;
60 return lastReturned.element;
61 }
62
63 public int nextIndex（） {
64 return nextIndex;
65 }
66
67 public int previousIndex（） {
68 return nextIndex-1;
69 }
70 // 移除當前Iterator持有的節點
71 public void remove（） {
72 checkForComodification（）;
73 Entry《E》 lastNext = lastReturned.next;
74 try {
75 LinkedList.this.remove（lastReturned）;
76 } catch （NoSuchElementException e） {
77 throw new IllegalStateException（）;
78 }
79 if （next==lastReturned）
80 next = lastNext;
81 else
82 nextIndex--;
83 lastReturned = header;
84 expectedModCount++;
85 }
86 // 修改當前節點的內容
87 public void set（E e） {
88 if （lastReturned == header）
89 throw new IllegalStateException（）;
90 checkForComodification（）;
91 lastReturned.element = e;
92 }
93 // 在當前持有節點后面插入新節點
94 public void add（E e） {
95 checkForComodification（）;
96 // 將最近一次返回節點修改為header
97 lastReturned = header;
98 addBefore（e， next）;
99 nextIndex++;
100 expectedModCount++;
101 }
102 // 判斷expectedModCount和modCount是否一致，以確保通過ListItr的修改操作正確的反映在LinkedList中
103 final void checkForComodification（） {
104 if （modCount ！= expectedModCount）
105 throw new ConcurrentModificationException（）;
106 }
107 }
下面是一個ListItr的使用實例。
1 LinkedList《String》 list = new LinkedList《String》（）;
2 list.add（“First”）;
3 list.add（“Second”）;
4 list.add（“Thrid”）;
5 System.out.println（list）;
6 ListIterator《String》 itr = list.listIterator（）;
7 while （itr.hasNext（）） {
8 System.out.println（itr.next（））;
9 }
10 try {
11 System.out.println（itr.next（））;// throw Exception
12 } catch （Exception e） {
13 // TODO： handle exception
14 }
15 itr = list.listIterator（）;
16 System.out.println（list）;
17 System.out.println（itr.next（））;
18 itr.add（“new node1”）;
19 System.out.println（list）;
20 itr.add（“new node2”）;
21 System.out.println（list）;
22 System.out.println（itr.next（））;
23 itr.set（“modify node”）;
24 System.out.println（list）;
25 itr.remove（）;
26 System.out.println（list）;
1 結果：
2 ［First， Second， Thrid］
3 First
4 Second
5 Thrid
6 ［First， Second， Thrid］
7 First
8 ［First， new node1， Second， Thrid］
9 ［First， new node1， new node2， Second， Thrid］
10 Second
11 ［First， new node1， new node2， modify node， Thrid］
12 ［First， new node1， new node2， Thrid］
LinkedList還有一個提供Iterator的方法：descendingIterator（）。該方法返回一個DescendingIterator對象。DescendingIterator是LinkedList的一個內部類。
1 public Iterator《E》 descendingIterator（） {
2 return new DescendingIterator（）;
3 }
下面分析詳細分析DescendingIterator類。
1 private class DescendingIterator implements Iterator {
2 // 獲取ListItr對象
3 final ListItr itr = new ListItr（size（））;
4 // hasNext其實是調用了itr的hasPrevious方法
5 public boolean hasNext（） {
6 return itr.hasPrevious（）;
7 }
8 // next（）其實是調用了itr的previous方法
9 public E next（） {
10 return itr.previous（）;
11 }
12 public void remove（） {
13 itr.remove（）;
14 }
15 }
從類名和上面的代碼可以看出這是一個反向的Iterator，代碼很簡單，都是調用的ListItr類中的方法。
工商網監
評論