linkedlist
linkedlist是一種可以在任何位置進行高效地插入和刪除操作的有序序列。
它的最基本存儲結構是一個節點：每個節點將存儲對象，以及前后節點的引用。
結構圖
從上面的結構圖中，我們可以了解到 listedlist 底層是基于雙向鏈表實現的。
圍起來的可以看成 linkedlist 類，它定義了三個 transient 成員變量：first、last、size。這三個變量是整個 linkedlist 類的關鍵點。
- 由于是雙向鏈表（每個node都有保存前后節點的引用），因此我們不管是由 first 還是 last 節點開始迭代，都可以將整個鏈表的數據找出來；
- 在查詢、隨機插入以及set等操作都有涉及 size 判斷；
- 由于 linkedlist 是雙向鏈表，類中只存儲了首尾兩個節點，因此查詢第n個元素都要從頭遍歷進行查找。
源碼分析
add(e e) 源碼分析
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/** * appends the specified element to the end of this list. * * <p>this method is equivalent to {@link #addlast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link collection#add}) */ public boolean add(e e) { linklast(e); return true; } /** * links e as last element. */ void linklast(e e) { final node<e> l = last; // 將當前最后一個元素寄存在 l final node<e> newnode = new node<>(l, e, null); // new 一個新節點：pre的引用為l；存儲元素為e；next的引用為null last = newnode; // 將新節點引用覆蓋成員變量 last if (l == null) first = newnode; // 若l為null，說明之前鏈表為空，此時新節點為首個元素 else l.next = newnode; // 否則，更新l的next引用 size++; // size+1 modcount++; // 非查詢操作 modcount 都會 +1 } |
add(int index, e element) 方法分析
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
/** * inserts the specified element at the specified position in this list. * shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws indexoutofboundsexception {@inheritdoc} */ public void add(int index, e element) { checkpositionindex(index); // 檢查 index 是否大于 size if (index == size) linklast(element); // 直接在鏈表末尾追加 else linkbefore(element, node(index)); // 插入index 節點前面 } // 檢查 index 是否超出范圍 超出則拋出 indexoutofboundsexception private void checkpositionindex(int index) { if (!ispositionindex(index)) throw new indexoutofboundsexception(outofboundsmsg(index)); } /** * tells if the argument is the index of a valid position for an * iterator or an add operation. */ private boolean ispositionindex(int index) { return index >= 0 && index <= size; } /** * 根據 index 查找 node * 該方法利用了雙向鏈表的特性，index 距離哪個鏈表頭近就從哪邊開始開始遍歷 * 時間復雜度為 o(n/2)； * 當 index 接近 size 的中間值時，效率最低 * returns the (non-null) node at the specified element index. */ node<e> node(int index) { // assert iselementindex(index); if (index < (size >> 1)) { // size 右移一位（除以2） node<e> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { node<e> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } |
優缺點
優點
增刪元素效率高（只需要更新節點附近的引用即可）
缺點
由于查詢需要進行遍歷，因此效率低
知識腦圖
以上所述是小編給大家介紹的java 集合系列（三）—— linkedlist詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對服務器之家網站的支持！
