前言
上周末我們一起分析了arraylist的源碼并進行了一些總結，因為最近在看collection這一塊的東西，下面的圖也是大致的總結了collection里面重要的接口和類，如果沒有意外的話后面基本上每一個都會和大家一起學習學習，所以今天也就和大家一起來看看linkedlist吧！
2，記得首次接觸linkedlist還是在大學java的時候，當時說起linkedlist的特性和應用場景：linkedlist基于雙向鏈表適用于增刪頻繁且查詢不頻繁的場景，線程不安全的且適用于單線程（這點和arraylist很像）。然后還記得一個很深刻的是可以用linkedlist來實現棧和隊列，那讓我們一起看一看源碼到底是怎么來實現這些特點的
2.1 構造函數
|
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
public class linkedlist<e> extends abstractsequentiallist<e> implements list<e>, deque<e>, cloneable, java.io.serializable{ transient int size = 0; transient node<e> first; transient node<e> last; public linkedlist() { } public linkedlist(collection<? extends e> c) { this(); addall(c); } public boolean addall(collection<? extends e> c) { return addall(size, c); } public boolean addall(int index, collection<? extends e> c) { checkpositionindex(index); object[] a = c.toarray(); int numnew = a.length; if (numnew == 0) return false; node<e> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (object o : a) { @suppresswarnings("unchecked") e e = (e) o; node<e> newnode = new node<>(pred, e, null); if (pred == null) first = newnode; else pred.next = newnode; pred = newnode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numnew; modcount++; return true; } private static class node<e> { e item; node<e> next; node<e> prev; node(node<e> prev, e element, node<e> next) { this.item = element; this.next = next; this.prev = prev; } } node<e> node(int index) { // assert iselementindex(index); if (index < (size >> 1)) { 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; } } } |
首先我們知道常見的構造是linkedlist()和linkedlist(collection<? extends e> c)兩種，然后再來看看我們繼承的類和實現的接口
linkedlist 集成abstractsequentiallist抽象類，內部使用listiterator迭代器來實現重要的方法
linkedlist 實現 list 接口，能對它進行隊列操作。
linkedlist 實現 deque 接口，即能將linkedlist當作雙端隊列使用。
linkedlist 實現了cloneable接口，即覆蓋了函數clone()，能克隆。
linkedlist 實現java.io.serializable接口，這意味著linkedlist支持序列化，能通過序列化去傳輸。
可以看到，相對于arraylist，linkedlist多實現了deque接口而少實現了randomaccess接口，且linkedlist繼承的是abstractsequentiallist類，而arraylist繼承的是abstractlist類。那么我們現在有一個疑問，這些多實現或少實現的接口和類會對我們linkedlist的特點產生影響嗎？這里我們先將這個疑問放在心里，我們先走正常的流程，先把linkedlist的源碼看完（主要是要解釋這些東西看deque的源碼，還要去看collections里面的邏輯，我怕扯遠了）
第5-7行：定義記錄元素數量size，因為我們之前說過linkedlist是個雙向鏈表，所以這里定義了鏈表鏈表頭節點first和鏈表尾節點last
第60-70行：定義一個節點node類，next表示此節點的后置節點，prev表示側節點的前置節點，element表示元素值
第22行：檢查當前的下標是否越界，因為是在構造函數中所以我們這邊的index為0，且size也為0
第24-29行：將集合c轉化為數組a，并獲取集合的長度；定義節點pred、succ，pred用來記錄前置節點，succ用來記錄后置節點
第70-89行：node()方法是獲取linkedlist中第index個元素，且根據index處于前半段還是后半段 進行一個折半，以提升查詢效率
第30-36行：如果index==size，則將元素追加到集合的尾部，pred = last將前置節點pred指向之前結合的尾節點，如果index！=size表明是插入集合，通過node(index)獲取當前要插入index位置的節點，且pred = succ.prev表示將前置節點指向于當前要插入節點位置的前置節點
第38-46行：鏈表批量增加，是靠for循環遍歷原數組，依次執行插入節點操作，第40行以前置節點 和 元素值e，構建new一個新節點；第41行如果前置節點是空，說明是頭結點，且將成員變量first指向當前節點，如果不是頭節點，則將上一個節點的尾節點指向當前新建的節點；第45行將當前的節點為前置節點了，為下次添加節點做準備。這些走完基本上我們的新節點也都創建出來了，可能這塊代碼有點繞，大家多看看
第48-53行：循環結束后，判斷如果后置節點是null， 說明此時是在隊尾添加的，設置一下隊列尾節點last，如果不是在隊尾，則更新之前插入位置節點的前節點和當前要插入節點的尾節點
第55-56行：修改當前集合數量、修改modcount記錄值
ok,雖然說是分析的構造函數的源碼，但是把node(int index)、addall(int index, collection<? extends e> c)方法也都看了，所以來小結一下：鏈表批量增加，是靠for循環遍歷原數組，依次執行插入節點操作；通過下標index來獲取節點node是采用的折半法來提升效率的
2.2 增加元素
常見的方法有以下三種
|
1
2
3
|
linkedlist.add(e e)linkedlist.add(int index, e element)linkedlist.addall(collection<? extends e> c) |
來看看具體的源碼
|
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
|
public boolean add(e e) { linklast(e); return true; } void linklast(e e) { final node<e> l = last; final node<e> newnode = new node<>(l, e, null); last = newnode; if (l == null) first = newnode; else l.next = newnode; size++; modcount++;} public void add(int index, e element) { checkpositionindex(index); if (index == size) linklast(element); else linkbefore(element, node(index)); } void linkbefore(e e, node<e> succ) { // assert succ != null; final node<e> pred = succ.prev; final node<e> newnode = new node<>(pred, e, succ); succ.prev = newnode; if (pred == null) first = newnode; else pred.next = newnode; size++; modcount++; } public boolean addall(collection<? extends e> c) { return addall(size, c); } |
第2、6-16行：創建一個newnode它的prev指向之前隊尾節點last，并記錄元素值e，之前的隊尾節點last的next指向當前節點，size自增，modcount自增
第18-20，27-38行：首先去檢查下標是否越界，然后判斷如果加入的位置剛好位于隊尾就和我們add（e element）的邏輯一樣了，如果不是則需要通過 node(index)函數定位出當前位于index下標的node，再通過linkbefore()函數創建出newnode將其插入到原先index位置
第40-42行：就是我們在構造函數中看過的批量加入元素的方法
ok，添加元素也很簡單，如果是在隊尾進行添加的話只需要創建一個新node將其前置節點指向之前的last，如果是在隊中添加節點，首選拆散原先的index-1、index、index+1之間的聯系，新建節點插入進去即可。
2.3 刪除元素
常見方法有以下這幾個方法
|
1
2
3
|
linkedlist.remove(int index)linkedlist.remove(object o)linkedlist.remove(collection<?> c) |
源碼如下
|
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
58
59
60
61
62
|
public e remove(int index) { checkelementindex(index); return unlink(node(index)); } unlink(node<e> x) { // assert x != null; final e element = x.item; final node<e> next = x.next; final node<e> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modcount++; return element; } public boolean remove(object o) { if (o == null) { for (node<e> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (node<e> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public boolean removeall(collection<?> c) { objects.requirenonnull(c); boolean modified = false; iterator<?> it = iterator(); while (it.hasnext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; } |
第1-4，6-30行：首先根據index通過方法值node(index)來確定出集合中的下標是index的node，咋們主要看unlink()方法，代碼感覺很多，其實只是將當前要刪除的節點node的頭結點的尾節點指向node的尾節點、將node的尾結點的頭節點指向node的頭節點，可能有點繞（哈哈），看一下代碼基本上就可以理解了，然后將下標為index的node置空，供gc回收
第32-49行：首先判斷一下當前要刪除的元素o是否為空，然后進行for循環定位出當前元素值等于o的節點node，然后再走的邏輯就是上面我們看到過的unlink()方法，也很簡單，比remove(int index) 多了一步
第51-62行：這一塊因為涉及到迭代器iterator，而我們linkedlist使用的是listitr，這個后面我們將迭代器的時候一起講，不過大致的邏輯是都可以看懂的，和我們的arraylist的迭代器方法的含義一樣的，可以先那樣理解
ok，小結一下， 按下標刪，也是先根據index找到node，然后去鏈表上unlink掉這個node。 按元素刪，會先去遍歷鏈表尋找是否有該node，考慮到允許null值，所以會遍歷兩遍，然后再去unlink它。
2.5 修改元素
|
1
2
3
4
5
6
7
|
public e set(int index, e element) { checkelementindex(index); node<e> x = node(index); e oldval = x.item; x.item = element; return oldval; } |
只有這一種方法，首先檢查下標是否越界，然后根據下標獲取當前node，然后修改節點中元素值item，超級簡單
2.6 查找元素
|
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
|
public e get(int index) { checkelementindex(index);//判斷是否越界 [0,size) return node(index).item; //調用node()方法 取出 node節點，} public int indexof(object o) { int index = 0; if (o == null) { for (node<e> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (node<e> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } public int lastindexof(object o) { int index = size; if (o == null) { for (node<e> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (node<e> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } |
獲取元素的源碼也很簡單，主要是通過node(index)方法獲取節點，然后獲取元素值，indexof和lastindexof方法的區別在于一個是從頭向尾開始遍歷，一個是從尾向頭開始遍歷
2.7 迭代器
|
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
public iterator<e> iterator() { return listiterator(); } public listiterator<e> listiterator() { return listiterator(0); } public listiterator<e> listiterator(final int index) { rangecheckforadd(index); return new listitr(index); } private class listitr extends itr implements listiterator<e> { listitr(int index) { cursor = index; } public boolean hasprevious() { return cursor != 0; } public e previous() { checkforcomodification(); try { int i = cursor - 1; e previous = get(i); lastret = cursor = i; return previous; } catch (indexoutofboundsexception e) { checkforcomodification(); throw new nosuchelementexception(); } } public int nextindex() { return cursor; } public int previousindex() { return cursor-1; } public void set(e e) { if (lastret < 0) throw new illegalstateexception(); checkforcomodification(); try { abstractlist.this.set(lastret, e); expectedmodcount = modcount; } catch (indexoutofboundsexception ex) { throw new concurrentmodificationexception(); } } public void add(e e) { checkforcomodification(); try { int i = cursor; abstractlist.this.add(i, e); lastret = -1; cursor = i + 1; expectedmodcount = modcount; } catch (indexoutofboundsexception ex) { throw new concurrentmodificationexception(); } } } |
可以看到，其實最后使用的迭代器是使用的listiterator類，且集成自itr，而itr類就是我們昨天arraylist內部使用的類，hasnext()方法和我們之前的一樣，判斷不等于size大小，然后next()獲取元素主要也是e next = get(i);這行代碼，這樣就又走到我們之前的獲取元素的源碼當中，獲得元素值。
ok，這樣我們上面的基本方法都看完了，再來看看我們上面遺留的問題，首先來看deque接口有什么作用，我們來一起看看
deque 是 double ended queue (雙端隊列) 的縮寫,讀音和 deck 一樣，蛋殼。
deque 繼承自 queue,直接實現了它的有 linkedlist, araydeque, concurrentlinkeddeque 等。
deque 支持容量受限的雙端隊列，也支持大小不固定的。一般雙端隊列大小不確定。
deque 接口定義了一些從頭部和尾部訪問元素的方法。比如分別在頭部、尾部進行插入、刪除、獲取元素。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public interface deque<e> extends queue<e> { void addfirst(e e);//插入頭部，異常會報錯 boolean offerfirst(e e);//插入頭部，異常不報錯 e getfirst();//獲取頭部，異常會報錯 e peekfirst();//獲取頭部，異常不報錯 e removefirst();//移除頭部，異常會報錯 e pollfirst();//移除頭部，異常不報錯 void addlast(e e);//插入尾部，異常會報錯 boolean offerlast(e e);//插入尾部，異常不報錯 e getlast();//獲取尾部，異常會報錯 e peeklast();//獲取尾部，異常不報錯 e removelast();//移除尾部，異常會報錯 e polllast();//移除尾部，異常不報錯} |
deque也就是一個接口，上面是接口里面的方法，然后了解deque就必須了解queue
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public interface queue<e> extends collection<e> { //往隊列插入元素，如果出現異常會拋出異常 boolean add(e e); //往隊列插入元素，如果出現異常則返回false boolean offer(e e); //移除隊列元素，如果出現異常會拋出異常 e remove(); //移除隊列元素，如果出現異常則返回null e poll(); //獲取隊列頭部元素，如果出現異常會拋出異常 e element(); //獲取隊列頭部元素，如果出現異常則返回null e peek();} |
然后我們知道linkedlist實現了deque接口，也就是說可以使用linkedlist實現棧和隊列的功能，讓寫寫看
|
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
|
package com.ysten.leakcanarytest; import java.util.collection;import java.util.linkedlist; /** * desc : 實現棧 * time : 2018/10/31 0031 19:07 * * @author : wangjitao */public class stack<t>{ private linkedlist<t> stack; //無參構造函數 public stack() { stack=new linkedlist<t>(); } //構造一個包含指定collection中所有元素的棧 public stack(collection<? extends t> c) { stack=new linkedlist<t>(c); } //入棧 public void push(t t) { stack.addfirst(t); } //出棧 public t pull() { return stack.remove(); } //棧是否為空 boolean isempty() { return stack.isempty(); } //打印棧元素 public void show() { for(object o:stack) system.out.println(o); }} |
測試功能
|
1
2
3
4
5
6
7
8
|
public static void main(string[] args){ stack<string> stringstack = new stack<>(); stringstack.push("1"); stringstack.push("2"); stringstack.push("3"); stringstack.push("4"); stringstack. show(); } |
打印結果如下：
4
3
2
1
隊列的實現類似的，大家可以下來自己寫一下，然后繼續我們的問題，實現deque接口和實現randomaccess接口有什么區別，我們上面看了deque接口，實現deque接口可以擁有雙向鏈表功能，那我們再來看看randomaccess接口
|
1
2
|
public interface randomaccess {} |
發現什么都沒有，原來randomaccess接口是一個標志接口（marker），然而實現這個接口有什么作用呢？
答案是只要list集合實現這個接口，就能支持快速隨機訪問，然而又有人問，快速隨機訪問是什么東西？有什么作用？
google是這樣定義的：給可以提供隨機訪問的list實現去標識一下，這樣使用這個list的程序在遍歷這種類型的list的時候可以有更高效率。僅此而已。
這時候看一下我們collections類中的binarysearch方法
|
1
2
3
4
5
6
|
int binarysearch(list<? extends comparable<? super t>> list, t key) { if (list instanceof randomaccess || list.size()<binarysearch_threshold) return collections.indexedbinarysearch(list, key); else return collections.iteratorbinarysearch(list, key); } |
可以看到這時候去判斷了如果當前集合實現了randomaccess接口就會走collections.indexedbinarysearch方法，那么我們來看一下collections.indexedbinarysearch()方法和collections.iteratorbinarysearch()的區別是什么呢？
|
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
|
int indexedbinarysearch(list<? extends comparable<? super t>> list, t key) { int low = 0; int high = list.size()-1; while (low <= high) { int mid = (low + high) >>> 1; comparable<? super t> midval = list.get(mid); int cmp = midval.compareto(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } int iteratorbinarysearch(list<? extends comparable<? super t>> list, t key) { int low = 0; int high = list.size()-1; listiterator<? extends comparable<? super t>> i = list.listiterator(); while (low <= high) { int mid = (low + high) >>> 1; comparable<? super t> midval = get(i, mid); int cmp = midval.compareto(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } |
通過查看源代碼，發現實現randomaccess接口的list集合采用一般的for循環遍歷，而未實現這接口則采用迭代器
，那現在讓我們以linkedlist為例子看一下，通過for循環、迭代器、removefirst和removelast來遍歷的效率（之前忘記寫這一塊了，順便一塊先寫了對于linkedlist那種訪問效率要高一些）
迭代器遍歷
|
1
2
3
4
5
6
7
8
9
10
11
12
|
linkedlist linkedlist = new linkedlist();for(int i = 0; i < 100000; i++){ linkedlist.add(i);}// 迭代器遍歷 long start = system.currenttimemillis(); iterator iterator = linkedlist.iterator(); while(iterator.hasnext()){ iterator.next(); } long end = system.currenttimemillis(); system.out.println("iterator："+ (end - start) +"ms"); |
打印結果：iterator：28ms
for循環get遍歷
|
1
2
3
4
5
6
7
|
// 順序遍歷(隨機遍歷) long start = system.currenttimemillis(); for(int i = 0; i < linkedlist.size(); i++){ linkedlist.get(i);}long end = system.currenttimemillis();system.out.println("for ："+ (end - start) +"ms"); |
打印結果 for ：6295ms
使用增強for循環
|
1
2
3
4
|
long start = system.currenttimemillis();for(object i : linkedlist);long end = system.currenttimemillis();system.out.println("增強for ："+ (end - start) +"ms"); |
輸出結果 增強for ：6ms
removefirst來遍歷
|
1
2
3
4
5
6
|
long start = system.currenttimemillis();while(linkedlist.size() != 0){ linkedlist.removefirst();}long end = system.currenttimemillis();system.out.println("removefirst ："+ (end - start) +"ms"); |
輸出結果 removefirst ：3ms
綜上結果可以看到，遍歷linkedlist時，使用removefirst()或removelast()效率最高，而for循環get()效率最低，應避免使用這種方式進行。應當注意的是，使用removefirst()或removelast()遍歷時，會刪除原始數據，若只單純的讀取，應當選用迭代器方式或增強for循環方式。
ok，上述的都是只針對linkedlist而言測試的，然后我們接著上面的randomaccess接口來講，看看通過對比arraylist的for循環和迭代器遍歷看看訪問效率
arraylist的for循環
|
1
2
3
4
5
6
|
long start = system.currenttimemillis();for (int i = 0; i < arraylist.size(); i++) { arraylist.get(i);} long end = system.currenttimemillis(); system.out.println("for ："+ (end - start) +"ms"); |
輸出結果 for ：3ms
arraylist的迭代遍歷
|
1
2
3
4
5
6
7
|
long start = system.currenttimemillis();iterator iterable = arraylist.iterator() ;while (iterable.hasnext()){ iterable.next();} long end = system.currenttimemillis(); system.out.println("for ："+ (end - start) +"ms"); |
輸出結果 for ：6ms
所以讓我們來綜上對比一下
arraylist
普通for循環：3ms
迭代器：6ms
linkedlist
普通for循環：6295ms
迭代器：28ms
從上面數據可以看出，arraylist用for循環遍歷比iterator迭代器遍歷快，linkedlist用iterator迭代器遍歷比for循環遍歷快,所以對于不同的list實現類，遍歷的方式有所不用，randomaccess接口這個空架子的存在，是為了能夠更好地判斷集合是否arraylist或者linkedlist，從而能夠更好選擇更優的遍歷方式，提高性能！
（在這里突然想起在去年跳槽的時候，有家公司的面試官問我，list集合的哪一種遍歷方式要快一些，然后我說我沒有每個去試過，結果那位大佬說的是for循環遍歷最快，還叫我下去試試，現在想想，只有在集合是arraylist的時候for循環才最快，對于linkedlist來說for循環反而是最慢的，那位大佬，你欠我一聲對不起（手動斜眼微笑））
3，上面把我們該看的點都看了，那么我們再來總結總結：
linkedlist 是雙向列表，鏈表批量增加，是靠for循環遍歷原數組，依次執行插入節點操作。
arraylist基于數組， linkedlist基于雙向鏈表，對于隨機訪問， arraylist比較占優勢，但linkedlist插入、刪除元素比較快，因為只要調整指針的指向。針對特定位置需要遍歷時，所以linkedlist在隨機訪問元素的話比較慢。
linkedlist沒有實現自己的 iterator，使用的是 listiterator。
linkedlist需要更多的內存，因為 arraylist的每個索引的位置是實際的數據，而 linkedlist中的每個節點中存儲的是實際的數據和前后節點的位置。
linkedlist也是非線程安全的，只有在單線程下才可以使用。為了防止非同步訪問，collections類里面提供了synchronizedlist()方法。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
原文鏈接：https://www.cnblogs.com/wjtaigwh/p/9883828.html
