電子發(fā)燒友App
結(jié)合上面代碼中的注釋及雙向循環(huán)鏈表的知識，應(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）方法是個私有方法，所以無法在外部程序中調(diào)用（當(dāng)然，這是一般情況，你可以通過反射上面的還是能調(diào)用到的）。
addBefore（E e，Entry《E》 entry）先通過Entry的構(gòu)造方法創(chuàng)建e的節(jié)點newEntry（包含了將其下一個節(jié)點設(shè)置為entry，上一個節(jié)點設(shè)置為entry.previous的操作，相當(dāng)于修改newEntry的“指針”），之后修改插入位置后newEntry的前一節(jié)點的next引用和后一節(jié)點的previous引用，使鏈表節(jié)點間的引用關(guān)系保持正確。之后修改和size大小和記錄modCount，然后返回新插入的節(jié)點。
總結(jié)，addBefore（E e，Entry《E》 entry）實現(xiàn)在entry之前插入由e構(gòu)造的新節(jié)點。而add（E e）實現(xiàn)在header節(jié)點之前插入由e構(gòu)造的新節(jié)點。
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é)點由index的值決定。
構(gòu)造方法，addAll（Collection《？ extends E》 c），add（E e），addBefor（E e，Entry《E》 entry）方法可以構(gòu)造鏈表并在指定位置插入節(jié)點，為了便于理解，下面給出插入節(jié)點的示意圖。
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）只需實現(xiàn)在header元素的下一個元素之前插入，即示意圖中的一號之前。addLast（E e）只需在實現(xiàn)在header節(jié)點前（因為是循環(huán)鏈表，所以header的前一個節(jié)點就是鏈表的最后一個節(jié)點）插入節(jié)點（插入后在2號節(jié)點之后）。
clear（）
1 public void clear（） {
2 Entry《E》 e = header.next;
3 // e可以理解為一個移動的“指針”，因為是循環(huán)鏈表，所以回到header的時候說明已經(jīng)沒有節(jié)點了
4 while （e ！= header） {
5 // 保留e的下一個節(jié)點的引用
6 Entry《E》 next = e.next;
7 // 接觸節(jié)點e對前后節(jié)點的引用
8 e.next = e.previous = null;
9 // 將節(jié)點e的內(nèi)容置空
10 e.element = null;
11 // 將e移動到下一個節(jié)點
12 e = next;
13 }
14 // 將header構(gòu)造成一個循環(huán)鏈表，同構(gòu)造方法構(gòu)造一個空的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é)點的element和o相等，若相等則返回該節(jié)點在鏈表中的索引位置，若不存在則放回-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（）返回鏈表的第一個節(jié)點的元素。為什么要提供功能一樣的兩個方法，像是包裝了一下名字？其實這只是為了在不同的上下文“語境”中能通過更貼切的方法名調(diào)用罷了。
get（int index）
1 public E get（int index） {
2 return entry（index）.element;
3 }
get（int index）方法用于獲得指定索引位置的節(jié)點的元素。它通過entry（int index）方法獲取節(jié)點。entry（int index）方法遍歷鏈表并獲取節(jié)點，在上面有說明過，不再陳述。
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)
評論