電子發(fā)燒友App
LinkedList也和ArrayList一樣實(shí)現(xiàn)了List接口，但是它執(zhí)行插入和刪除操作時(shí)比ArrayList更加高效，因?yàn)樗腔阪湵淼??；阪湵硪矝Q定了它在隨機(jī)訪問方面要比ArrayList遜色一點(diǎn)。
除此之外，LinkedList還提供了一些可以使其作為棧、隊(duì)列、雙端隊(duì)列的方法。這些方法中有些彼此之間只是名稱的區(qū)別，以使得這些名字在特定的上下文中顯得更加的合適。
先看LinkedList類的定義。
1 public class LinkedList《E》
2 extends AbstractSequentialList《E》
3 implements List《E》， Deque《E》， Cloneable， java.io.Serializable
LinkedList繼承自AbstractSequenceList、實(shí)現(xiàn)了List及Deque接口。其實(shí)AbstractSequenceList已經(jīng)實(shí)現(xiàn)了List接口，這里標(biāo)注出List只是更加清晰而已。AbstractSequenceList提供了List接口骨干性的實(shí)現(xiàn)以減少實(shí)現(xiàn)List接口的復(fù)雜度。Deque接口定義了雙端隊(duì)列的操作。
LinkedList中之定義了兩個(gè)屬性：
1 private transient Entry《E》 header = new Entry《E》（null， null， null）;
2 private transient int size = 0;
size肯定就是LinkedList對象里面存儲(chǔ)的元素個(gè)數(shù)了。LinkedList既然是基于鏈表實(shí)現(xiàn)的，那么這個(gè)header肯定就是鏈表的頭結(jié)點(diǎn)了，Entry就是節(jié)點(diǎn)對象了。一下是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 }
只定義了存儲(chǔ)的元素、前一個(gè)元素、后一個(gè)元素，這就是雙向鏈表的節(jié)點(diǎn)的定義，每個(gè)節(jié)點(diǎn)只知道自己的前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)。
來看LinkedList的構(gòu)造方法。
1 public LinkedList（） {
2 header.next = header.previous = header;
3 }
4 public LinkedList（Collection《？ extends E》 c） {
5 this（）;
6 addAll（c）;
7 }
LinkedList提供了兩個(gè)構(gòu)造方法。第一個(gè)構(gòu)造方法不接受參數(shù)，只是將header節(jié)點(diǎn)的前一節(jié)點(diǎn)和后一節(jié)點(diǎn)都設(shè)置為自身（注意，這個(gè)是一個(gè)雙向循環(huán)鏈表，如果不是循環(huán)鏈表，空鏈表的情況應(yīng)該是header節(jié)點(diǎn)的前一節(jié)點(diǎn)和后一節(jié)點(diǎn)均為null），這樣整個(gè)鏈表其實(shí)就只有header一個(gè)節(jié)點(diǎn)，用于表示一個(gè)空的鏈表。第二個(gè)構(gòu)造方法接收一個(gè)Collection參數(shù)c，調(diào)用第一個(gè)構(gòu)造方法構(gòu)造一個(gè)空的鏈表，之后通過addAll將c中的元素全部添加到鏈表中。來看addAll的內(nèi)容。
1 public boolean addAll（Collection《？ extends E》 c） {
2 return addAll（size， c）;
3 }
4 // index參數(shù)指定collection中插入的第一個(gè)元素的位置
5 public boolean addAll（int index， Collection《？ extends E》 c） {
6 // 插入位置超過了鏈表的長度或小于0，報(bào)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 // 若需要插入的節(jié)點(diǎn)個(gè)數(shù)為0則返回false，表示沒有插入元素
13 if （numNew==0）
14 return false;
15 modCount++;
16 // 保存index處的節(jié)點(diǎn)。插入位置如果是size，則在頭結(jié)點(diǎn)前面插入，否則獲取index處的節(jié)點(diǎn)
17 Entry《E》 successor = （index==size ？ header ： entry（index））;
18 // 獲取前一個(gè)節(jié)點(diǎn)，插入時(shí)需要修改這個(gè)節(jié)點(diǎn)的next引用
19 Entry《E》 predecessor = successor.previous;
20 // 按順序?qū)數(shù)組中的第一個(gè)元素插入到index處，將之后的元素插在這個(gè)元素后面
21 for （int i=0; i《numNew; i++） {
22 // 結(jié)合Entry的構(gòu)造方法，這條語句是插入操作，相當(dāng)于C語言中鏈表中插入節(jié)點(diǎn)并修改指針
23 Entry《E》 e = new Entry《E》（（E）a［i］， successor， predecessor）;
24 // 插入節(jié)點(diǎn)后將前一節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)，相當(dāng)于修改前一節(jié)點(diǎn)的next指針
25 predecessor.next = e;
26 // 相當(dāng)于C語言中成功插入元素后將指針向后移動(dòng)一個(gè)位置以實(shí)現(xiàn)循環(huán)的功能
27 predecessor = e;
28 }
29 // 插入元素前index處的元素鏈接到插入的Collection的最后一個(gè)節(jié)點(diǎn)
30 successor.previous = predecessor;
31 // 修改size
32 size += numNew;
33 return true;
34 }
構(gòu)造方法中的調(diào)用了addAll（Collection《？ extends E》 c）方法，而在addAll（Collection《？ extends E》 c）方法中僅僅是將size當(dāng)做index參數(shù)調(diào)用了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 // 根據(jù)這個(gè)判斷決定從哪個(gè)方向遍歷這個(gè)鏈表
7 if （index 《 （size 》》 1）） {
8 for （int i = 0; i 《= index; i++）
9 e = e.next;
10 } else {
11 // 可以通過header節(jié)點(diǎn)向前遍歷，說明這個(gè)一個(gè)循環(huán)雙向鏈表，header的previous指向鏈表的最后一個(gè)節(jié)點(diǎn)，這也驗(yàn)證了構(gòu)造方法中對于header節(jié)點(diǎn)的前后節(jié)點(diǎn)均指向自己的解釋
12 for （int i = size; i 》 index; i--）
13 e = e.previous;
14 }
15 return e;
16 }
結(jié)合上面代碼中的注釋及雙向循環(huán)鏈表的知識(shí)，應(yīng)該很容易理解LinkedList構(gòu)造方法所涉及的內(nèi)容。下面開始分析LinkedList的其他方法。
add（E e）
1 public boolean add（E e） {
2 addBefore（e， header）;
3 return true;
4 }
從上面的代碼可以看出，add（E e）方法只是調(diào)用了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）方法是個(gè)私有方法，所以無法在外部程序中調(diào)用（當(dāng)然，這是一般情況，你可以通過反射上面的還是能調(diào)用到的）。
addBefore（E e，Entry《E》 entry）先通過Entry的構(gòu)造方法創(chuàng)建e的節(jié)點(diǎn)newEntry（包含了將其下一個(gè)節(jié)點(diǎn)設(shè)置為entry，上一個(gè)節(jié)點(diǎn)設(shè)置為entry.previous的操作，相當(dāng)于修改newEntry的“指針”），之后修改插入位置后newEntry的前一節(jié)點(diǎn)的next引用和后一節(jié)點(diǎn)的previous引用，使鏈表節(jié)點(diǎn)間的引用關(guān)系保持正確。之后修改和size大小和記錄modCount，然后返回新插入的節(jié)點(diǎn)。
總結(jié)，addBefore（E e，Entry《E》 entry）實(shí)現(xiàn)在entry之前插入由e構(gòu)造的新節(jié)點(diǎn)。而add（E e）實(shí)現(xiàn)在header節(jié)點(diǎn)之前插入由e構(gòu)造的新節(jié)點(diǎn)。
add（int index，E e）
1 public void add（int index， E element） {
2 addBefore（element， （index==size ？ header ： entry（index）））;
3 }
也是調(diào)用了addBefore（E e，Entry《E》 entry）方法，只是entry節(jié)點(diǎn)由index的值決定。
構(gòu)造方法，addAll（Collection《？ extends E》 c），add（E e），addBefor（E e，Entry《E》 entry）方法可以構(gòu)造鏈表并在指定位置插入節(jié)點(diǎn)，為了便于理解，下面給出插入節(jié)點(diǎn)的示意圖。
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 }
看上面的示意圖，結(jié)合addBefore（E e，Entry《E》 entry）方法，很容易理解addFrist（E e）只需實(shí)現(xiàn)在header元素的下一個(gè)元素之前插入，即示意圖中的一號之前。addLast（E e）只需在實(shí)現(xiàn)在header節(jié)點(diǎn)前（因?yàn)槭茄h(huán)鏈表，所以header的前一個(gè)節(jié)點(diǎn)就是鏈表的最后一個(gè)節(jié)點(diǎn)）插入節(jié)點(diǎn)（插入后在2號節(jié)點(diǎn)之后）。
clear（）
1 public void clear（） {
2 Entry《E》 e = header.next;
3 // e可以理解為一個(gè)移動(dòng)的“指針”，因?yàn)槭茄h(huán)鏈表，所以回到header的時(shí)候說明已經(jīng)沒有節(jié)點(diǎn)了
4 while （e ！= header） {
5 // 保留e的下一個(gè)節(jié)點(diǎn)的引用
6 Entry《E》 next = e.next;
7 // 接觸節(jié)點(diǎn)e對前后節(jié)點(diǎn)的引用
8 e.next = e.previous = null;
9 // 將節(jié)點(diǎn)e的內(nèi)容置空
10 e.element = null;
11 // 將e移動(dòng)到下一個(gè)節(jié)點(diǎn)
12 e = next;
13 }
14 // 將header構(gòu)造成一個(gè)循環(huán)鏈表，同構(gòu)造方法構(gòu)造一個(gè)空的LinkedList
15 header.next = header.previous = header;
16 // 修改size
17 size = 0;
18 modCount++;
19 }
上面代碼中的注釋已經(jīng)足以解釋這段代碼的邏輯，需要注意的是提到的“指針”僅僅是概念上的類比，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鏈表中是否存在節(jié)點(diǎn)的element和o相等，若相等則返回該節(jié)點(diǎn)在鏈表中的索引位置，若不存在則放回-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（）方法調(diào)用了getFirst（）返回鏈表的第一個(gè)節(jié)點(diǎn)的元素。為什么要提供功能一樣的兩個(gè)方法，像是包裝了一下名字？其實(shí)這只是為了在不同的上下文“語境”中能通過更貼切的方法名調(diào)用罷了。
get（int index）
1 public E get（int index） {
2 return entry（index）.element;
3 }
get（int index）方法用于獲得指定索引位置的節(jié)點(diǎn)的元素。它通過entry（int index）方法獲取節(jié)點(diǎn)。entry（int index）方法遍歷鏈表并獲取節(jié)點(diǎn)，在上面有說明過，不再陳述。
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 }
先獲取指定索引的節(jié)點(diǎn)，之后保留原來的元素，然后用element進(jìn)行替換，之后返回原來的元素。
getLast（）
1 public E getLast（） {
2 if （size==0）
3 throw new NoSuchElementException（）;
4 return header.previous.element;
5 }
getLast（）方法和getFirst（）方法類似，只是獲取的是header節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的元素。因?yàn)槭茄h(huán)鏈表，所以header節(jié)點(diǎn)的前一節(jié)點(diǎn)就是鏈表的最后一個(gè)節(jié)點(diǎn)。
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 }
因?yàn)椴檎业氖莑ast index，即最后一次出現(xiàn)的位置，所以采用由后向前的遍歷方式。因?yàn)椴捎昧擞泻笙蚯暗谋闅v，所以index被賦值為size，并且循環(huán)體內(nèi)執(zhí)行時(shí)都進(jìn)行減操作。分兩種情況判斷是否存在，分別是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 }
在鏈表末尾插入元素。
上面這三個(gè)方法都只是調(diào)用了相應(yīng)的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 }
上面的三個(gè)方法也很簡單，只是調(diào)用了對應(yīng)的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相關(guān)的方法都是獲取并移除某個(gè)元素。都是和remove操作相關(guān)。
pop（）
1 public E pop（） {
2 return removeFirst（）;
3 }
push（E e）
1 public void push（E e） {
2 addFirst（e）;
3 }
這兩個(gè)方法對應(yīng)棧的操作，即彈出一個(gè)元素和壓入一個(gè)元素，僅僅是調(diào)用了removeFirst（）和addFirst（）方法。
下面集中看remove相關(guān)操作的方法。
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 }
幾個(gè)remove方法最終都是調(diào)用了一個(gè)私有方法：remove（Entry《E》 e），只是其他簡單邏輯上的區(qū)別。下面分析remove（Entry《E》 e）方法。
1 private E remove（Entry《E》 e） {
2 if （e == header）
3 throw new NoSuchElementException（）;
4 // 保留將被移除的節(jié)點(diǎn)e的內(nèi)容
5 E result = e.element;
6 // 將前一節(jié)點(diǎn)的next引用賦值為e的下一節(jié)點(diǎn)
7 e.previous.next = e.next;
8 // 將e的下一節(jié)點(diǎn)的previous賦值為e的上一節(jié)點(diǎn)
9 e.next.previous = e.previous;
10 // 上面兩條語句的執(zhí)行已經(jīng)導(dǎo)致了無法在鏈表中訪問到e節(jié)點(diǎn)，而下面解除了e節(jié)點(diǎn)對前后節(jié)點(diǎn)的引用
11 e.next = e.previous = null;
12 // 將被移除的節(jié)點(diǎn)的內(nèi)容設(shè)為null
13 e.element = null;
14 // 修改size大小
15 size--;
16 modCount++;
17 // 返回移除節(jié)點(diǎn)e的內(nèi)容
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 }
調(diào)用父類的clone（）方法初始化對象鏈表clone，將clone構(gòu)造成一個(gè)空的雙向循環(huán)鏈表，之后將header的下一個(gè)節(jié)點(diǎn)開始將逐個(gè)節(jié)點(diǎn)添加到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 }
創(chuàng)建大小和LinkedList相等的數(shù)組result，遍歷鏈表，將每個(gè)節(jié)點(diǎn)的元素element復(fù)制到數(shù)組中，返回?cái)?shù)組。
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 }
先判斷出入的數(shù)組a的大小是否足夠，若大小不夠則拓展。這里用到了發(fā)射的方法，重新實(shí)例化了一個(gè)大小為size的數(shù)組。之后將數(shù)組a賦值給數(shù)組result，遍歷鏈表向result中添加的元素。最后判斷數(shù)組a的長度是否大于size，若大于則將size位置的內(nèi)容設(shè)置為null。返回a。
從代碼中可以看出，數(shù)組a的length小于等于size時(shí)，a中所有元素被覆蓋，被拓展來的空間存儲(chǔ)的內(nèi)容都是null；若數(shù)組a的length的length大于size，則0至size-1位置的內(nèi)容被覆蓋，size位置的元素被設(shè)置為null，size之后的元素不變。
為什么不直接對數(shù)組a進(jìn)行操作，要將a賦值給result數(shù)組之后對result數(shù)組進(jìn)行操作？
---------------------------------------------------------------------------------------------------------------------------------
LinkedList的Iterator
除了Entry，LinkedList還有一個(gè)內(nèi)部類：ListItr。
ListItr實(shí)現(xiàn)了ListIterator接口，可知它是一個(gè)迭代器，通過它可以遍歷修改LinkedList。
在LinkedList中提供了獲取ListItr對象的方法：listIterator（int index）。
1 public ListIterator《E》 listIterator（int index） {
2 return new ListItr（index）;
3 }
該方法只是簡單的返回了一個(gè)ListItr對象。
LinkedList中還有通過集成獲得的listIterator（）方法，該方法只是調(diào)用了listIterator（int index）并且傳入0。
下面詳細(xì)分析ListItr。
1 private class ListItr implements ListIterator《E》 {
2 // 最近一次返回的節(jié)點(diǎn)，也是當(dāng)前持有的節(jié)點(diǎn)
3 private Entry《E》 lastReturned = header;
4 // 對下一個(gè)元素的引用
5 private Entry《E》 next;
6 // 下一個(gè)節(jié)點(diǎn)的index
7 private int nextIndex;
8 private int expectedModCount = modCount;
9 // 構(gòu)造方法，接收一個(gè)index參數(shù)，返回一個(gè)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賦值為第一個(gè)節(jié)點(diǎn)
18 next = header.next;
19 // 獲取指定位置的節(jié)點(diǎn)
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 // 根據(jù)nextIndex是否等于size判斷時(shí)候還有下一個(gè)節(jié)點(diǎn)（也可以理解為是否遍歷完了LinkedList）
30 public boolean hasNext（） {
31 return nextIndex ！= size;
32 }
33 // 獲取下一個(gè)元素
34 public E next（） {
35 checkForComodification（）;
36 // 如果nextIndex==size，則已經(jīng)遍歷完鏈表，即沒有下一個(gè)節(jié)點(diǎn)了（實(shí)際上是有的，因?yàn)槭茄h(huán)鏈表，任何一個(gè)節(jié)點(diǎn)都會(huì)有上一個(gè)和下一個(gè)節(jié)點(diǎn)，這里的沒有下一個(gè)節(jié)點(diǎn)只是說所有節(jié)點(diǎn)都已經(jīng)遍歷完了）
37 if （nextIndex == size）
38 throw new NoSuchElementException（）;
39 // 設(shè)置最近一次返回的節(jié)點(diǎn)為next節(jié)點(diǎn)
40 lastReturned = next;
41 // 將next“向后移動(dòng)一位”
42 next = next.next;
43 // index計(jì)數(shù)加1
44 nextIndex++;
45 // 返回lastReturned的元素
46 return lastReturned.element;
47 }
48
49 public boolean hasPrevious（） {
50 return nextIndex ！= 0;
51 }
52 // 返回上一個(gè)節(jié)點(diǎn)，和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 // 移除當(dāng)前Iterator持有的節(jié)點(diǎn)
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 // 修改當(dāng)前節(jié)點(diǎn)的內(nèi)容
87 public void set（E e） {
88 if （lastReturned == header）
89 throw new IllegalStateException（）;
90 checkForComodification（）;
91 lastReturned.element = e;
92 }
93 // 在當(dāng)前持有節(jié)點(diǎn)后面插入新節(jié)點(diǎn)
94 public void add（E e） {
95 checkForComodification（）;
96 // 將最近一次返回節(jié)點(diǎn)修改為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 }
下面是一個(gè)ListItr的使用實(shí)例。
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 結(jié)果：
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還有一個(gè)提供Iterator的方法：descendingIterator（）。該方法返回一個(gè)DescendingIterator對象。DescendingIterator是LinkedList的一個(gè)內(nèi)部類。
1 public Iterator《E》 descendingIterator（） {
2 return new DescendingIterator（）;
3 }
下面分析詳細(xì)分析DescendingIterator類。
1 private class DescendingIterator implements Iterator {
2 // 獲取ListItr對象
3 final ListItr itr = new ListItr（size（））;
4 // hasNext其實(shí)是調(diào)用了itr的hasPrevious方法
5 public boolean hasNext（） {
6 return itr.hasPrevious（）;
7 }
8 // next（）其實(shí)是調(diào)用了itr的previous方法
9 public E next（） {
10 return itr.previous（）;
11 }
12 public void remove（） {
13 itr.remove（）;
14 }
15 }
從類名和上面的代碼可以看出這是一個(gè)反向的Iterator，代碼很簡單，都是調(diào)用的ListItr類中的方法。
工商網(wǎng)監(jiān)
評論