電子發(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對象里面存儲的元素個(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 }
只定義了存儲的元素、前一個(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 }
工商網(wǎng)監(jiān)
評論