上一篇《鏈表概念篇》中， 主要給小伙伴們講述了什么是鏈表？ 為什么鏈表是線性結(jié)構(gòu)？ 鏈表的操作是什么？ 鏈表操作的過程與原理是什么？相信認(rèn)真讀過的小伙伴們已經(jīng)明白的掌握了鏈表的相關(guān)概念。 那么下面來回顧一下
1. 什么是鏈表？
鏈表是一種鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu)， 兩個節(jié)點(diǎn)之間使用鏈?zhǔn)竭B接， 比如 單鏈表的A的next是B， B的next是C, C的next是D，可以標(biāo)識為A -> B -> C -> D。 雙鏈表在單鏈表的基礎(chǔ)上添加了前指向pre, 如A的next是B，則必然B的pre是A， 理解為A是B的前驅(qū)， B是A的后繼。
2. 鏈表的操作流程
一般常用的操作也就是我們熟悉的增刪改查。其中查和改很簡單， 與數(shù)組不同的是，我們是通過頭節(jié)點(diǎn)，不斷的遍歷相鄰的下個節(jié)點(diǎn)，直到找到你想要的節(jié)點(diǎn)元素；既然找到了，那么修改節(jié)點(diǎn)的值就簡單的不能再簡單了。鏈表中稍微復(fù)雜些的操作就是增添與刪除節(jié)點(diǎn)。 上一篇中我也給小伙伴們列了相應(yīng)的步驟：
1） 首先找到相關(guān)的節(jié)點(diǎn)，即目標(biāo)節(jié)點(diǎn)的前驅(qū)與后記
2） 斷開原有的鏈接關(guān)系
3） 建立新的鏈接關(guān)系
如果還對鏈表的概念不清楚，建議回頭查看上一篇《鏈表 概念篇》
鏈表在數(shù)據(jù)結(jié)構(gòu)中算是比較重要的結(jié)構(gòu)之一，希望大家真的把與鏈表相關(guān)的知識弄明白。 那么接下來，我們講解一下LinkedList的源碼。其實(shí)明白了常用操作的原理， 還是很好理解的。
LinkedList源碼解讀
首先，我們來看一下常用的操作
從上述可以看出，提供的常用接口，無非就是CRUD或者CRUD的變種； 那么如果你掌握了CRUD，至于他們的變種就可以一通百通了。如addFirst , addLast, add, addAll等都屬于增加吧。
下面主要來說一下鏈表的增刪改查。
1. 先來看一下最簡單的 查
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
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;
}
代碼很少，我們不妨來看一下最核心的地方
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
for循環(huán)，但不是我們常用的for循環(huán)。 默認(rèn)初始化是x = first, 從第一個節(jié)點(diǎn)開始； x =x.next, 不斷查找下一個節(jié)點(diǎn)； 判斷節(jié)點(diǎn)的值是否是我們傳入的值，如果是，那么恭喜你，找到了！同樣的步驟，我們可以返回在整個鏈表的位置index, 也可以返回找到的節(jié)點(diǎn)， 當(dāng)前還可以返回目標(biāo)節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。 這也就滿足了我們的查找與增刪操作時需要的目標(biāo)節(jié)點(diǎn)的前驅(qū)和后繼了吧。
當(dāng)然，如果你經(jīng)常使用數(shù)據(jù)庫Cursor遍歷的話，你會發(fā)現(xiàn)真的很像。
2. 順帶著，我們看一下修改的操作
關(guān)于修改，我真的不想說了。當(dāng)我們成功找到了想要修改的節(jié)點(diǎn)后，你還不會修改節(jié)點(diǎn)的值么？
3. 鏈表的核心操作之插入一個元素
鏈表提供的插入Api主要有兩個， 那就是頭插法和尾插法。 當(dāng)然還有一些衍生的操作，不過掌握了這兩種主要的核心方法，其他一搭眼，你就明白為什么了。
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
頭插法，即將節(jié)點(diǎn)插入到頭部。我們來想一下這個過程，現(xiàn)在已知一個鏈表，如下
A -> B -> C -> D
可以看出，A是first,也即頭節(jié)點(diǎn)；如果我們想在頭部插入一個節(jié)點(diǎn)E， 那么按照我們總結(jié)的步驟
E->A->B->C->D
- 目標(biāo)節(jié)點(diǎn)是頭節(jié)點(diǎn)，因此沒有前驅(qū)，有一個后繼A，是當(dāng)前的first
- 插入頭部或尾部，不涉及斷鏈問題
- 建立新鏈接， E的next指向A， 如果是雙鏈表的話，當(dāng)然A的pre也指向E
再看代碼
- 先找到了相關(guān)節(jié)點(diǎn)first， 保存起來
final Node<E> f = first;
- 根據(jù)數(shù)據(jù)，生成新的目標(biāo)節(jié)點(diǎn);新節(jié)點(diǎn)的next是f也就是first
- 插入后，新節(jié)點(diǎn)就是first了
first = newNode;
- 如果頭節(jié)點(diǎn)是空，那么插入后，就只有一個節(jié)點(diǎn)newNode了，因此既是頭，也是尾。如果頭節(jié)點(diǎn)不是空，這里A的前驅(qū)指向newNode，前面在newNode創(chuàng)建時，已經(jīng)指定了后繼是f。 這時候，一條新的鏈就創(chuàng)建起來了。
從以上來看， LinkedList是個雙鏈表，因?yàn)榇嬖趐re指針。雙鏈表比單鏈表的高校在于： 單鏈表是單鏈，只能從頭到尾找；雙鏈表是雙鏈表，既可以從頭向后找，也可以從尾向前找。
再來看尾插法， 明白了頭插法，那么尾插法就手到擒來了，你只要畫一個圖，就可以照著寫出來。還是那個例子，ABCD插入E，這次是從尾部，那么
A -> B -> C->D
A->B->C->D->E
根據(jù)頭插法的分析，涉及的前驅(qū)只有D， 沒有后繼。
/**
* Links e as last element.
*/
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++;
}
與頭插法的實(shí)現(xiàn)幾乎是相同的，這里不做解釋了。
頭插法和尾插法相對比較簡單， 因?yàn)橹簧婕耙粋€元素前驅(qū)或后繼， 那么來看一下中間插入是怎么做的？ 相比于以上兩種，只是多了一層前驅(qū)或后繼的斷開與重鏈。
/**
* Inserts element e before non-null Node succ.
*/
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++;
}
上述代碼是在succ節(jié)點(diǎn)前面插入一個元素為e的新節(jié)點(diǎn)，linkAfter實(shí)現(xiàn)與之相似，這里重點(diǎn)說一下這個， 你可以試著自己寫一下在后面插入的實(shí)現(xiàn)
當(dāng)前的狀況： succ.pre -> succ -> succ.next
插入后： succ.pre -> E -> succ -> succ.next
我們來分析一下：
- 還是找受影響的目標(biāo)節(jié)點(diǎn)E的前驅(qū)與后繼，分別是succ.pre以及succ
- 看圖，插入E，我們需要斷開succ.pre與succ的鏈；因?yàn)椴迦牒?，succ的前驅(qū)是E了，而不是以前的succ.pre
- 重新建立鏈， succ.pre與E之間， E與succ之間
根據(jù)以上分析，我們來看源碼
1.找到并保存影響節(jié)點(diǎn) succ.pre
final Node<E> pred = succ.prev;
2. 斷開并重建succ與E的鏈
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
這里你就奇怪了，為啥斷開和建鏈?zhǔn)窃谝黄鸬哪兀?我們斷開是通過設(shè)置next或pre為null來實(shí)現(xiàn)的，便于理解； 但是之后會在next或pre上添加新的關(guān)系， 這里把兩個過程合并了。比如
我們應(yīng)該先斷開pre與succ的鏈，那么我們應(yīng)該這么寫
pred.next = null; // 斷開前驅(qū)的后繼關(guān)系
succ.pre = null; // 斷開succ的前驅(qū)關(guān)系
然后建立新的鏈
succ.pre = E; // E就是newNode
E.next = succ;
E的鏈的建立是在構(gòu)造中，new Node(前驅(qū)， 數(shù)據(jù)， 后繼)。別說沒有鏈到succ哈！
接下來我們把以下代碼合并為一個
succ.pre = null;
succ.pre = E;
我們直接合并成
succ.pre = E;
到這里，你明白了嗎？
好了，插入的解析到此結(jié)束了；接下來解析刪除的代碼。其實(shí)明白了插入，刪除很容易理解，因?yàn)槎际菙噫満徒ㄦ湹倪^程
E 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;
}
還是先模擬一下過程，已知一個鏈表ABCD, 此時我想刪除C， 那么過程是：
A - B - C - D
A - B - D
- 首先找到目標(biāo)C以受影響的前驅(qū)B與后繼D，并保存
- 斷開C與B， C與D的關(guān)系
- 重新建立B與D的關(guān)系
看源碼
pre.next = next;
可能比較繞， pre就是B， next就是D， 此時是刪除C后，讓B的后繼指向D。同時，
next.prev = prev;
D的前驅(qū)指向B。 鏈的斷開與建立就有了。
···
x.pre = null;
x.next = null;
···
這就斷開C的所有鏈了，也就是說C是一個獨(dú)立節(jié)點(diǎn)了。
本篇的意義，就是在理解理論的前提下，通過看系統(tǒng)的實(shí)現(xiàn)來驗(yàn)證理論，并加深印象，以及知道理論是如何用代碼實(shí)現(xiàn)的。整個過程其實(shí)理解了理論后，還是很容易看懂的。
我一直在強(qiáng)調(diào)一個流程，至于斷開與重建鏈的過程，并不一定是誰先誰后的；只是這樣解釋比較好理解；在代碼中我們也看到了，斷開與重建的過程是同時進(jìn)行的，當(dāng)然這要建立在你理解整個過程之后，因此建議你自己手寫一遍這個過程，才能真正明白它究竟是怎么做的。
好了，通過這兩篇文章，相信你已經(jīng)理解了鏈表這種結(jié)構(gòu)了。如果你覺得本文對你有幫助，不妨點(diǎn)個贊，謝謝！
