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

　　單向鏈表

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

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

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

　　鏈表的增刪

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

　　假設(shè)你是民國時期軍統(tǒng)的頭目，你負(fù)責(zé)一個諜報鏈路。為了安全，你和你的手下們是單向聯(lián)系的。也就是說只能你聯(lián)系你的一個手下，由這個手下再去聯(lián)絡(luò)其他人，最終把暗號交到目標(biāo)的手上。假設(shè)你的代號是A，你的手下是B，B的手下是C，C來執(zhí)行任務(wù)。這個機(jī)制一直運(yùn)轉(zhuǎn)很好，直到有一天，B因?yàn)樯衩卦蜣D(zhuǎn)移了地點(diǎn)，導(dǎo)致A和B聯(lián)絡(luò)的時間變長，為了解決這個問題，你決定新增一個人手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)什么意外，這整條鏈路就斷了。

　　我們把整個圖畫出來如下：

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

　　代碼如下：

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

　　來看圖：

　　雙向鏈表

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

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

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

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

　　總結(jié)

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

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