上一篇《鏈表概念篇》中， 主要給小伙伴們講述了什么是鏈表？ 為什么鏈表是線性結(jié)構(gòu)驮履？ 鏈表的操作是什么？ 鏈表操作的過(guò)程與原理是什么廉嚼？相信認(rèn)真讀過(guò)的小伙伴們已經(jīng)明白的掌握了鏈表的相關(guān)概念玫镐。 那么下面來(lái)回顧一下
1. 什么是鏈表？
鏈表是一種鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu)前鹅， 兩個(gè)節(jié)點(diǎn)之間使用鏈?zhǔn)竭B接摘悴， 比如 單鏈表的A的next是B， B的next是C, C的next是D舰绘，可以標(biāo)識(shí)為A -> B -> C -> D蹂喻。 雙鏈表在單鏈表的基礎(chǔ)上添加了前指向pre, 如A的next是B，則必然B的pre是A捂寿， 理解為A是B的前驅(qū)口四， B是A的后繼。
2. 鏈表的操作流程
一般常用的操作也就是我們熟悉的增刪改查秦陋。其中查和改很簡(jiǎn)單蔓彩， 與數(shù)組不同的是，我們是通過(guò)頭節(jié)點(diǎn)驳概，不斷的遍歷相鄰的下個(gè)節(jié)點(diǎn)赤嚼，直到找到你想要的節(jié)點(diǎn)元素；既然找到了顺又，那么修改節(jié)點(diǎn)的值就簡(jiǎn)單的不能再簡(jiǎn)單了更卒。鏈表中稍微復(fù)雜些的操作就是增添與刪除節(jié)點(diǎn)。 上一篇中我也給小伙伴們列了相應(yīng)的步驟：
1） 首先找到相關(guān)的節(jié)點(diǎn)稚照，即目標(biāo)節(jié)點(diǎn)的前驅(qū)與后記
2） 斷開(kāi)原有的鏈接關(guān)系
3） 建立新的鏈接關(guān)系
如果還對(duì)鏈表的概念不清楚蹂空，建議回頭查看上一篇《鏈表 概念篇》
鏈表在數(shù)據(jù)結(jié)構(gòu)中算是比較重要的結(jié)構(gòu)之一俯萌，希望大家真的把與鏈表相關(guān)的知識(shí)弄明白。 那么接下來(lái)上枕，我們講解一下LinkedList的源碼咐熙。其實(shí)明白了常用操作的原理， 還是很好理解的辨萍。
LinkedList源碼解讀
首先棋恼，我們來(lái)看一下常用的操作
從上述可以看出，提供的常用接口分瘦，無(wú)非就是CRUD或者CRUD的變種蘸泻； 那么如果你掌握了CRUD琉苇，至于他們的變種就可以一通百通了嘲玫。如addFirst , addLast, add, addAll等都屬于增加吧。
下面主要來(lái)說(shuō)一下鏈表的增刪改查并扇。
1. 先來(lái)看一下最簡(jiǎn)單的 查
/**
* 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;
}
代碼很少去团，我們不妨來(lái)看一下最核心的地方
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, 從第一個(gè)節(jié)點(diǎn)開(kāi)始土陪； x =x.next, 不斷查找下一個(gè)節(jié)點(diǎn)； 判斷節(jié)點(diǎn)的值是否是我們傳入的值肴熏，如果是鬼雀，那么恭喜你，找到了蛙吏！同樣的步驟源哩，我們可以返回在整個(gè)鏈表的位置index, 也可以返回找到的節(jié)點(diǎn)， 當(dāng)前還可以返回目標(biāo)節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)鸦做。 這也就滿足了我們的查找與增刪操作時(shí)需要的目標(biāo)節(jié)點(diǎn)的前驅(qū)和后繼了吧励烦。
當(dāng)然，如果你經(jīng)常使用數(shù)據(jù)庫(kù)Cursor遍歷的話泼诱，你會(huì)發(fā)現(xiàn)真的很像坛掠。
2. 順帶著，我們看一下修改的操作
關(guān)于修改治筒，我真的不想說(shuō)了屉栓。當(dāng)我們成功找到了想要修改的節(jié)點(diǎn)后，你還不會(huì)修改節(jié)點(diǎn)的值么耸袜？
3. 鏈表的核心操作之插入一個(gè)元素
鏈表提供的插入Api主要有兩個(gè)友多， 那就是頭插法和尾插法。 當(dāng)然還有一些衍生的操作句灌，不過(guò)掌握了這兩種主要的核心方法夷陋，其他一搭眼欠拾，你就明白為什么了。
/**
* 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)插入到頭部藐窄。我們來(lái)想一下這個(gè)過(guò)程，現(xiàn)在已知一個(gè)鏈表酬土，如下
A -> B -> C -> D
可以看出荆忍，A是first,也即頭節(jié)點(diǎn)；如果我們想在頭部插入一個(gè)節(jié)點(diǎn)E撤缴， 那么按照我們總結(jié)的步驟
E->A->B->C->D
- 目標(biāo)節(jié)點(diǎn)是頭節(jié)點(diǎn)刹枉，因此沒(méi)有前驅(qū)，有一個(gè)后繼A屈呕，是當(dāng)前的first
- 插入頭部或尾部微宝，不涉及斷鏈問(wèn)題
- 建立新鏈接， E的next指向A虎眨， 如果是雙鏈表的話蟋软，當(dāng)然A的pre也指向E
再看代碼
- 先找到了相關(guān)節(jié)點(diǎn)first， 保存起來(lái)
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)是空，那么插入后碌冶，就只有一個(gè)節(jié)點(diǎn)newNode了湿痢，因此既是頭，也是尾扑庞。如果頭節(jié)點(diǎn)不是空譬重，這里A的前驅(qū)指向newNode，前面在newNode創(chuàng)建時(shí)嫩挤，已經(jīng)指定了后繼是f害幅。 這時(shí)候，一條新的鏈就創(chuàng)建起來(lái)了岂昭。
從以上來(lái)看以现， LinkedList是個(gè)雙鏈表，因?yàn)榇嬖趐re指針约啊。雙鏈表比單鏈表的高校在于： 單鏈表是單鏈邑遏，只能從頭到尾找；雙鏈表是雙鏈表恰矩，既可以從頭向后找记盒，也可以從尾向前找。
再來(lái)看尾插法外傅， 明白了頭插法纪吮，那么尾插法就手到擒來(lái)了俩檬，你只要畫一個(gè)圖，就可以照著寫出來(lái)碾盟。還是那個(gè)例子棚辽，ABCD插入E，這次是從尾部冰肴，那么
A -> B -> C->D
A->B->C->D->E
根據(jù)頭插法的分析屈藐，涉及的前驅(qū)只有D， 沒(méi)有后繼熙尉。
/**
* 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)幾乎是相同的联逻，這里不做解釋了。
頭插法和尾插法相對(duì)比較簡(jiǎn)單检痰， 因?yàn)橹簧婕耙粋€(gè)元素前驅(qū)或后繼包归， 那么來(lái)看一下中間插入是怎么做的？ 相比于以上兩種攀细，只是多了一層前驅(qū)或后繼的斷開(kāi)與重鏈箫踩。
/**
* 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)前面插入一個(gè)元素為e的新節(jié)點(diǎn)，linkAfter實(shí)現(xiàn)與之相似谭贪，這里重點(diǎn)說(shuō)一下這個(gè)， 你可以試著自己寫一下在后面插入的實(shí)現(xiàn)
當(dāng)前的狀況： succ.pre -> succ -> succ.next
插入后： succ.pre -> E -> succ -> succ.next
我們來(lái)分析一下：
- 還是找受影響的目標(biāo)節(jié)點(diǎn)E的前驅(qū)與后繼锦担，分別是succ.pre以及succ
- 看圖俭识，插入E，我們需要斷開(kāi)succ.pre與succ的鏈洞渔；因?yàn)椴迦牒筇酌模瑂ucc的前驅(qū)是E了，而不是以前的succ.pre
- 重新建立鏈磁椒， succ.pre與E之間堤瘤， E與succ之間
根據(jù)以上分析，我們來(lái)看源碼
1.找到并保存影響節(jié)點(diǎn) succ.pre
final Node<E> pred = succ.prev;
2. 斷開(kāi)并重建succ與E的鏈
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
這里你就奇怪了浆熔，為啥斷開(kāi)和建鏈?zhǔn)窃谝黄鸬哪兀?我們斷開(kāi)是通過(guò)設(shè)置next或pre為null來(lái)實(shí)現(xiàn)的本辐，便于理解； 但是之后會(huì)在next或pre上添加新的關(guān)系医增， 這里把兩個(gè)過(guò)程合并了慎皱。比如
我們應(yīng)該先斷開(kāi)pre與succ的鏈，那么我們應(yīng)該這么寫
pred.next = null; // 斷開(kāi)前驅(qū)的后繼關(guān)系
succ.pre = null; // 斷開(kāi)succ的前驅(qū)關(guān)系
然后建立新的鏈
succ.pre = E; // E就是newNode
E.next = succ;
E的鏈的建立是在構(gòu)造中叶骨，new Node(前驅(qū)茫多， 數(shù)據(jù)， 后繼)忽刽。別說(shuō)沒(méi)有鏈到succ哈天揖！
接下來(lái)我們把以下代碼合并為一個(gè)
succ.pre = null;
succ.pre = E;
我們直接合并成
succ.pre = E;
到這里夺欲，你明白了嗎？
好了今膊，插入的解析到此結(jié)束了洁闰；接下來(lái)解析刪除的代碼。其實(shí)明白了插入万细，刪除很容易理解扑眉，因?yàn)槎际菙噫満徒ㄦ湹倪^(guò)程
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;
}
還是先模擬一下過(guò)程，已知一個(gè)鏈表ABCD, 此時(shí)我想刪除C赖钞， 那么過(guò)程是：
A - B - C - D
A - B - D
- 首先找到目標(biāo)C以受影響的前驅(qū)B與后繼D腰素，并保存
- 斷開(kāi)C與B， C與D的關(guān)系
- 重新建立B與D的關(guān)系
看源碼
pre.next = next;
可能比較繞雪营， pre就是B弓千， next就是D， 此時(shí)是刪除C后献起，讓B的后繼指向D洋访。同時(shí)，
next.prev = prev;
D的前驅(qū)指向B谴餐。 鏈的斷開(kāi)與建立就有了姻政。
···
x.pre = null;
x.next = null;
···
這就斷開(kāi)C的所有鏈了，也就是說(shuō)C是一個(gè)獨(dú)立節(jié)點(diǎn)了岂嗓。
本篇的意義汁展，就是在理解理論的前提下，通過(guò)看系統(tǒng)的實(shí)現(xiàn)來(lái)驗(yàn)證理論厌殉，并加深印象食绿，以及知道理論是如何用代碼實(shí)現(xiàn)的。整個(gè)過(guò)程其實(shí)理解了理論后公罕，還是很容易看懂的器紧。
我一直在強(qiáng)調(diào)一個(gè)流程，至于斷開(kāi)與重建鏈的過(guò)程楼眷，并不一定是誰(shuí)先誰(shuí)后的铲汪；只是這樣解釋比較好理解；在代碼中我們也看到了摩桶，斷開(kāi)與重建的過(guò)程是同時(shí)進(jìn)行的桥状，當(dāng)然這要建立在你理解整個(gè)過(guò)程之后，因此建議你自己手寫一遍這個(gè)過(guò)程硝清，才能真正明白它究竟是怎么做的辅斟。
好了，通過(guò)這兩篇文章芦拿，相信你已經(jīng)理解了鏈表這種結(jié)構(gòu)了士飒。如果你覺(jué)得本文對(duì)你有幫助查邢，不妨點(diǎn)個(gè)贊，謝謝酵幕！
