鏈表是很多數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，它的最大特點(diǎn)是支持快速的刪除和插入，因此在很多數(shù)據(jù)頻繁變動(dòng)的場(chǎng)景下使用廣泛。而且鏈表的可拓展性較強(qiáng)，所以它的應(yīng)用非常廣泛，相關(guān)的拓展和改進(jìn)版本也很多。今天我們和大家介紹的是雙端鏈表，也稱為雙向鏈表，它是尋常單向鏈表的改進(jìn)版本，也是會(huì)經(jīng)常使用的鏈表。

　　單向鏈表

　　鏈表（Linkedlist）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。以上是維基百科當(dāng)中的定義，我們可以明白兩點(diǎn)，首先鏈表由多個(gè)節(jié)點(diǎn)組成的，每個(gè)節(jié)點(diǎn)存儲(chǔ)了下一個(gè)節(jié)點(diǎn)的位置。其次，鏈表的各個(gè)節(jié)點(diǎn)不是順序存儲(chǔ)的。

　　我們看一下下圖可以加深一下了解：

　　上圖當(dāng)中展示是單向鏈表，單向的意思是說(shuō)每個(gè)節(jié)點(diǎn)只有一個(gè)指向后繼節(jié)點(diǎn)的指針，也就是說(shuō)鏈表只有一個(gè)遍歷方向，因此稱為是單向鏈表。

　　鏈表的增刪

　　初學(xué)者在學(xué)習(xí)鏈表時(shí)可能會(huì)頭疼它的使用，相比于數(shù)組的直接訪問(wèn)，鏈表需要通過(guò)移動(dòng)指針來(lái)遍歷節(jié)點(diǎn)修改節(jié)點(diǎn)的內(nèi)容來(lái)完成增刪，因此不如數(shù)組直觀。我一直想要找到一個(gè)很好的例子來(lái)比喻鏈表運(yùn)行的機(jī)制，直到有一次看諜戰(zhàn)片，我發(fā)現(xiàn)間諜聯(lián)絡(luò)的系統(tǒng)就是以鏈表形式工作的。所以我決定以間諜系統(tǒng)來(lái)舉例，介紹一下鏈表的工作原理。

　　假設(shè)你是民國(guó)時(shí)期軍統(tǒng)的頭目，你負(fù)責(zé)一個(gè)諜報(bào)鏈路。為了安全，你和你的手下們是單向聯(lián)系的。也就是說(shuō)只能你聯(lián)系你的一個(gè)手下，由這個(gè)手下再去聯(lián)絡(luò)其他人，最終把暗號(hào)交到目標(biāo)的手上。假設(shè)你的代號(hào)是A，你的手下是B，B的手下是C，C來(lái)執(zhí)行任務(wù)。這個(gè)機(jī)制一直運(yùn)轉(zhuǎn)很好，直到有一天，B因?yàn)樯衩卦蜣D(zhuǎn)移了地點(diǎn)，導(dǎo)致A和B聯(lián)絡(luò)的時(shí)間變長(zhǎng)，為了解決這個(gè)問(wèn)題，你決定新增一個(gè)人手D專門負(fù)責(zé)A和B之間的聯(lián)絡(luò)，加快聯(lián)絡(luò)速度。你應(yīng)該怎么辦呢？

　　由于身份限制，以及安全原因，你是不知道B的具體信息的。你只能將消息給到A，讓A去聯(lián)絡(luò)新人D，并且告訴他B的聯(lián)絡(luò)方法。還有一點(diǎn)需要注意，A必須等到D成功找到了B之后再切斷和B的聯(lián)系。否則一旦D出現(xiàn)什么意外，這整條鏈路就斷了。

　　我們把整個(gè)圖畫(huà)出來(lái)如下：

　　先讓D和B取得聯(lián)系，之后斷開(kāi)A和B的聯(lián)系。但是有一個(gè)問(wèn)題，由于A的后繼只有一個(gè)，A如果指向D，那么B的位置就會(huì)丟失。所以我們需要先用一個(gè)臨時(shí)變量cur存儲(chǔ)下來(lái)B的位置，然后再讓D指向這個(gè)cur。不過(guò)在Python當(dāng)中，我們可以不用這么麻煩，利用Python的多變量賦值的方法，我們可以一行代碼搞定。

　　代碼如下：

　　假如過(guò)了一段時(shí)間，B又回到了原處，我們不需要D了，要?jiǎng)h除這個(gè)節(jié)點(diǎn)該怎么辦？很簡(jiǎn)單，直接讓D將B的最新的聯(lián)絡(luò)方式給A就可以了。也就是說(shuō)讓A跨過(guò)D指向B即可。

　　來(lái)看圖：

　　雙向鏈表

　　理解了單向鏈表，雙向鏈表也就很簡(jiǎn)單了。雙向的意思也很明顯，每個(gè)節(jié)點(diǎn)除了記錄后繼節(jié)點(diǎn)的位置之外，還會(huì)記錄源頭節(jié)點(diǎn)的位置。有了雙向指針之后不僅是獲取來(lái)源節(jié)點(diǎn)方便而已，并且也可以很方便地對(duì)整個(gè)鏈表進(jìn)行倒敘遍歷和頭部插入。

　　還記得我們之前Python專題當(dāng)中介紹過(guò)的deque這個(gè)庫(kù)嗎？通過(guò)deque我們可以實(shí)現(xiàn)一個(gè)雙向增刪元素的隊(duì)列，結(jié)合雙向鏈表的定義，很容易發(fā)現(xiàn)deque其實(shí)就是保留了一部分api的雙向鏈表。換句話說(shuō)deque是基于雙向鏈表實(shí)現(xiàn)的，就和棧是基于list實(shí)現(xiàn)的一樣。

　　和單向鏈表相比，由于我們多了一個(gè)指針，理解和實(shí)現(xiàn)起來(lái)會(huì)更加容易，因?yàn)橹靶枰ㄟ^(guò)順序關(guān)系以及臨時(shí)變量完成的內(nèi)容現(xiàn)在可以通過(guò)前向指針很輕易地實(shí)現(xiàn)了。

　　下面附上雙向鏈表增刪的代碼：

　　總結(jié)

　　雙向鏈表本身并不復(fù)雜，也沒(méi)有太多變化的花樣，和之前介紹的SkipList相比要簡(jiǎn)單許多。我相信即使是初學(xué)者，只要自己動(dòng)手實(shí)現(xiàn)一遍，也足夠掌握。在我初學(xué)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我非常抗拒使用鏈表，除了覺(jué)得尋址很麻煩，需要遍歷整個(gè)鏈表耗時(shí)很大之外。另一個(gè)根本的原因是在C++當(dāng)中鏈表的編寫(xiě)很麻煩，而且很容易有內(nèi)存泄漏以及野指針問(wèn)題。所以我當(dāng)時(shí)盡可能地使用數(shù)組作為替代，并且甚至一度認(rèn)為隨著內(nèi)存價(jià)格的降低，總有一天我們可以拋棄鏈表這個(gè)結(jié)構(gòu)。

　   以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java基礎(chǔ)學(xué)習(xí)：Java雙鏈表結(jié)構(gòu)視頻”的內(nèi)容，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。