注：源碼系列文章主要是對(duì)某付費(fèi)專欄的總結(jié)記錄剔交。如有侵權(quán)词爬，請(qǐng)聯(lián)系刪除料祠。
LinkedList 適用于集合元素先入先出和先入后出的場(chǎng)景骆捧，在隊(duì)列源碼中被頻繁使用，面試也經(jīng)常被問到髓绽。
1 整體架構(gòu)
LinkedList 底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)雙向鏈表敛苇，整體結(jié)構(gòu)如下圖所示：
上圖代表了一個(gè)雙向鏈表結(jié)構(gòu)，鏈表中的每個(gè)節(jié)點(diǎn)都可以向前或向后追溯顺呕，幾個(gè)概念如下：
- 鏈表每個(gè)節(jié)點(diǎn)叫做 Node枫攀，Node 有 prev 代表前一個(gè)節(jié)點(diǎn)，next 代表后一個(gè)節(jié)點(diǎn)株茶；
- first 是雙向鏈表的頭節(jié)點(diǎn)来涨，它的前一個(gè)節(jié)點(diǎn)是 null；
- last 是雙向鏈表的尾節(jié)點(diǎn)启盛，它的后一個(gè)節(jié)點(diǎn)是 null蹦掐；
- 當(dāng)鏈表中沒有數(shù)據(jù)時(shí)，first 和 last 是同一個(gè)節(jié)點(diǎn)僵闯，前后指向都是 null卧抗；
- 因?yàn)槭莻€(gè)雙向鏈表，只要機(jī)器內(nèi)存足夠強(qiáng)大鳖粟，是沒有大小限制的社裆。
鏈表中的元素叫做 Node，Node 的組成部分：
private static class Node<E> {
E item; // 節(jié)點(diǎn)值
Node<E> next; // 指向下一個(gè)節(jié)點(diǎn)
Node<E> prev; // 指向前一個(gè)節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2 源碼解析
2.1 新增
追加節(jié)點(diǎn)時(shí)向图，我們可以選擇追加到鏈表頭部泳秀，還是追加到鏈表尾部，add 方法默認(rèn)是從尾部開始追加张漂，addFirst 方法是從頭部開始追加晶默，我們分別來看下兩種不同的追加方式：
2.1.1 從尾部增加（add/addLast）
/**
* Links e as last element.
*/
void linkLast(E e) {
// 將尾節(jié)點(diǎn)暫存
final Node<E> l = last;
// 初始化新的節(jié)點(diǎn)谨娜。l: 新節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)航攒。e: 當(dāng)前新增節(jié)點(diǎn)值。null: 當(dāng)前新增節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是 null
final Node<E> newNode = new Node<>(l, e, null);
// 為尾節(jié)點(diǎn)賦值為當(dāng)前新增的節(jié)點(diǎn)
last = newNode;
// 如果尾節(jié)點(diǎn)為空(即鏈表為空)
if (l == null)
// 則為頭節(jié)點(diǎn)賦值為當(dāng)前新增節(jié)點(diǎn)也就是尾節(jié)點(diǎn)
first = newNode;
// 否則把原尾節(jié)點(diǎn) l 的下一個(gè)節(jié)點(diǎn)指向當(dāng)前新增節(jié)點(diǎn)
else
l.next = newNode;
// 大小和版本增加
size++;
modCount++;
}
2.1.2 從頭部追加（addFirst）
/**
* Links e as first element.
*/
private void linkFirst(E e) {
// 將頭節(jié)點(diǎn)暫存
final Node<E> f = first;
// 初始化新的節(jié)點(diǎn)
final Node<E> newNode = new Node<>(null, e, f);
// 為頭節(jié)點(diǎn)賦值為當(dāng)前新增節(jié)點(diǎn)
first = newNode;
// 如果原頭節(jié)點(diǎn) f 為空(即鏈表為空)
if (f == null)
// 則為尾節(jié)點(diǎn)賦值為當(dāng)前新增節(jié)點(diǎn)也就是頭節(jié)點(diǎn)
last = newNode;
// 否則把原頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向當(dāng)前新增節(jié)點(diǎn)
else
f.prev = newNode;
// 大小和版本增加
size++;
modCount++;
}
頭部追加節(jié)點(diǎn)和尾部追加節(jié)點(diǎn)非常類似趴梢，只是前者是移動(dòng)頭部節(jié)點(diǎn)的 prev 指向漠畜，后者是移動(dòng)尾部節(jié)點(diǎn)的 next 指向。
2.2 節(jié)點(diǎn)刪除
節(jié)點(diǎn)刪除和節(jié)點(diǎn)追加類似坞靶，我們可以選擇從頭部刪除憔狞，也可以選擇從尾部刪除，刪除操作會(huì)把節(jié)點(diǎn)的值彰阴，前后指向節(jié)點(diǎn)都置為 null瘾敢，幫助 GC 進(jìn)行回收。
2.2.1 從頭部刪除
// 從頭部刪除節(jié)點(diǎn) f 是鏈表頭部
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 拿出頭節(jié)點(diǎn)的值
final E element = f.item;
// 拿出頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
final Node<E> next = f.next;
// 賦值頭節(jié)點(diǎn)的值和頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為 null，幫助 GC 回收
f.item = null;
f.next = null; // help GC
// 原頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) next 為新的頭節(jié)點(diǎn)
first = next;
// 如果 next 為 null簇抵，表明鏈表為空
if (next == null)
last = null;
else
// 鏈表不為空庆杜，設(shè)置新的頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為 null
next.prev = null;
// 大小和版本更改
size--;
modCount++;
// 返回被刪除節(jié)點(diǎn)的值
return element;
}
2.2.2 從尾部刪除
// 從尾部刪除節(jié)點(diǎn) l 是鏈表尾部
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 拿出尾節(jié)點(diǎn)的值
final E element = l.item;
// 拿出尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
final Node<E> prev = l.prev;
// 賦值尾節(jié)點(diǎn)的值和尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為 null，幫助 GC 回收
l.item = null;
l.prev = null; // help GC
// 原尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) prev 為新的尾節(jié)點(diǎn)
last = prev;
// 如果 prev 為 null碟摆，表明鏈表為空
if (prev == null)
first = null;
else
// 鏈表為不空晃财，設(shè)置新的尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為 null
prev.next = null;
// 大小和版本更改
size--;
modCount++;
// 返回被刪除節(jié)點(diǎn)的值
return element;
}
從源碼中我們可以了解到，鏈表結(jié)構(gòu)的節(jié)點(diǎn)新增典蜕、刪除都非常簡單断盛，僅僅把前后節(jié)點(diǎn)的指向修改而已，所以 LinkedList 新增和刪除速度很快愉舔。
2.3 節(jié)點(diǎn)查詢
鏈表查詢某一個(gè)節(jié)點(diǎn)是比較慢的钢猛，需要挨個(gè)循環(huán)查找才行，源碼如下：
// 根據(jù)鏈表索引位置查詢節(jié)點(diǎn)
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果 index 處于隊(duì)列的前半部分轩缤，則從頭開始查找厢洞，size >> 1 是 size 除以 2 的意思
if (index < (size >> 1)) {
Node<E> x = first;
// for 循環(huán)到 index 的前一個(gè) node 停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
}
// 如果 index 處于隊(duì)列的后半部分，則從尾部開始查找
else {
Node<E> x = last;
// for 循環(huán)到 index 的后一個(gè) node 停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
從源碼中我們發(fā)現(xiàn)典奉，LinkedList 并沒有采用從頭循環(huán)到尾的做法躺翻，而是采取了簡單二分法，首先看看 index 是在鏈表的前半部分卫玖，還是后半部分公你。如果是前半部分，就從頭開始尋找假瞬，反之亦然陕靠。通過這種方式，使循環(huán)的次數(shù)至少降低了一半脱茉，提高了查找的性能剪芥，這種思想值得我們借鑒。
2.4 方法對(duì)比
LinkedList 實(shí)現(xiàn)了 Queue 接口琴许，在新增税肪、刪除、查詢等方面增加了很多新的方法榜田，這些方法平時(shí)特別容易混淆益兄，在鏈表為空的情況下，返回值也不太一樣箭券，如下：
|方法含義|返回異常|返回特殊值|底層實(shí)現(xiàn)|
|----|----|----|----|----|
|新增(尾部)|add(e)|offer(e)|底層實(shí)現(xiàn)相同|
|刪除(頭節(jié)點(diǎn))|remove()|poll()|鏈表為空時(shí)净捅，remove 會(huì)拋出異常，poll 返回 null|
|查找(頭節(jié)點(diǎn))|element()|peek()|鏈表為空時(shí)辩块，element 會(huì)拋出異常蛔六，peek 返回 null|
PS：Queue 接口注釋建議 add 方法操作失敗時(shí)拋出異常荆永，但 LinkedList 實(shí)現(xiàn)的 add 方法一直返回 true。
LinkedList 也實(shí)現(xiàn) Deque 接口国章，對(duì)新增屁魏、刪除和查找都提供從頭開始，還是從尾開始兩種方向的方法捉腥，比如 remove 方法氓拼，Deque 提供了 removeFirst 和 removeLast 兩種方向的使用方法，但當(dāng)鏈表為空時(shí)的表現(xiàn)都和 remove 方法一樣抵碟，都會(huì)拋出異常桃漾。
2.5 迭代器
因?yàn)?LinkedList 要實(shí)現(xiàn)雙向的迭代訪問，所以我們使用 Iterator 接口肯定不行拟逮，因?yàn)?Iterator 只支持從頭到尾的訪問撬统。Java 新增了一個(gè)迭代接口，叫做：ListIterator敦迄，這個(gè)接口提供了向前和向后的迭代方法恋追，如下：
| 迭代順序 | 相關(guān)方法 |
|---|---|
| 從頭到尾迭代 |
hasNext, next, nextIndex
|
| 從尾到頭迭代 |
hasProvious, previous, previousIndex
|
LinkedList 實(shí)現(xiàn)了 ListIterator 接口，源碼如圖：
// 雙向迭代器
private class ListItr implements ListIterator<E> {
// 按照命名罚屋，意思為上一次執(zhí)行 next() 或者 previous() 方法返回的節(jié)點(diǎn)
private Node<E> lastReturned;
// 下一個(gè)節(jié)點(diǎn)
private Node<E> next;
// 下一個(gè)節(jié)點(diǎn)的位置
private int nextIndex;
// 期望版本號(hào)
private int expectedModCount = modCount;
........
}
從頭到尾方向的迭代
// 判斷有沒有下一個(gè)元素
public boolean hasNext() {
// 下一個(gè)節(jié)點(diǎn)的索引小于鏈表的大小苦囱，就有
return nextIndex < size;
}
// 取下一個(gè)元素
public E next() {
// 檢查版本號(hào)有無變化
checkForComodification();
// 再次檢查是否還有下一個(gè)元素
if (!hasNext())
throw new NoSuchElementException();
// 賦值 lastReturned，首次執(zhí)行 next() 方法時(shí) 賦值為 null
lastReturned = next;
// next 是下一個(gè)節(jié)點(diǎn)脾猛，
next = next.next;
// 索引變化
nextIndex++;
return lastReturned.item;
}
從尾到頭方向的迭代
// 判斷是否還有上一個(gè)節(jié)點(diǎn)撕彤，我們知道最小索引為 0, 如果 nextIndex 大于0則表示還有上一個(gè)元素
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
// 檢查版本號(hào)有無變化
checkForComodification();
// 再次檢查是否還有上一個(gè)元素
if (!hasPrevious())
throw new NoSuchElementException();
// 如果 next 為null， 則表示當(dāng)前是從尾到頭的第一次迭代猛拴，則賦值 next 為 last羹铅，
// 否則賦值 next 為 next 的前一個(gè)元素 prev
lastReturned = next = (next == null) ? last : next.prev;
// 索引變化
nextIndex--;
return lastReturned.item;
}
迭代器刪除
LinkedList 在刪除元素時(shí)，也推薦通過迭代器進(jìn)行刪除愉昆，源碼如下：
public void remove() {
// 檢查版本號(hào)有無變化
checkForComodification();
// 首先 lastReturned 是本次迭代的值
// 如果 lastReturned 為 null职员，表示未執(zhí)行 next() 或 pervious() 方法，那刪除直接報(bào)錯(cuò)
// 如果 lastReturned 不為 null 則繼續(xù)執(zhí)行
if (lastReturned == null)
throw new IllegalStateException();
// 將本次迭代要?jiǎng)h除的元素 lastReturned 的下一個(gè)元素緩存
Node<E> lastNext = lastReturned.next;
// 刪除 lastReturned
unlink(lastReturned);
// 如果是從尾到頭的第一次迭代跛溉，則 lastReturned = next = last. 參考上面方法 previous()
if (next == lastReturned)
// 這個(gè)時(shí)候 lastReturned 是尾節(jié)點(diǎn)焊切，lastNext 是 null，所以 next 也是 null倒谷，這樣在執(zhí)行 previous() 方法判斷 next 是否為null 時(shí)蛛蒙，發(fā)現(xiàn) next 是null糙箍，就會(huì)把尾結(jié)點(diǎn) last 賦值給 next
next = lastNext;
else
// 反之索引遞減
nextIndex--;
lastReturned = null;
expectedModCount++;
}
總結(jié)
LinkedList 適用于要求有順序渤愁、并且會(huì)按照順序進(jìn)行迭代的場(chǎng)景，主要是依賴于底層的鏈表結(jié)構(gòu)深夯。
------------------------------------- END -------------------------------------
