電子發(fā)燒友App
結(jié)合上面代碼中的注釋及雙向循環(huán)鏈表的知識(shí)，應(yīng)該很容易理解LinkedList構(gòu)造方法所涉及的內(nèi)容。下面開(kā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è)私有方法，所以無(wú)法在外部程序中調(diào)用（當(dāng)然，這是一般情況，你可以通過(guò)反射上面的還是能調(diào)用到的）。
addBefore（E e，Entry《E》 entry）先通過(guò)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è)元素之前插入，即示意圖中的一號(hào)之前。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號(hào)節(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í)候說(shuō)明已經(jīng)沒(méi)有節(jié)點(diǎn)了
4 while （e ！= header） {
5 // 保留e的下一個(gè)節(jié)點(diǎn)的引用
6 Entry《E》 next = e.next;
7 // 接觸節(jié)點(diǎn)e對(duì)前后節(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)足以解釋這段代碼的邏輯，需要注意的是提到的“指針”僅僅是概念上的類(lèi)比，Java并不存在“指針”的概念，而只有引用，為了便于理解所以部分說(shuō)明使用了“指針”。
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）方法通過(guò)判斷indexOf（Object o）方法返回的值是否是-1來(lái)判斷鏈表中是否包含對(duì)象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í)這只是為了在不同的上下文“語(yǔ)境”中能通過(guò)更貼切的方法名調(diào)用罷了。
get（int index）
1 public E get（int index） {
2 return entry（index）.element;
3 }
get（int index）方法用于獲得指定索引位置的節(jié)點(diǎn)的元素。它通過(guò)entry（int index）方法獲取節(jié)點(diǎn)。entry（int index）方法遍歷鏈表并獲取節(jié)點(diǎn)，在上面有說(shuō)明過(guò)，不再陳述。
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 }
工商網(wǎng)監(jiān)
評(píng)論