鏈表是很多數據結構的基礎，它的最大特點是支持快速的刪除和插入，因此在很多數據頻繁變動的場景下使用廣泛。而且鏈表的可拓展性較強，所以它的應用非常廣泛，相關的拓展和改進版本也很多。今天我們和大家介紹的是雙端鏈表，也稱為雙向鏈表，它是尋常單向鏈表的改進版本，也是會經常使用的鏈表。

　　單向鏈表

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

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

　　上圖當中展示是單向鏈表，單向的意思是說每個節點只有一個指向后繼節點的指針，也就是說鏈表只有一個遍歷方向，因此稱為是單向鏈表。

　　鏈表的增刪

　　初學者在學習鏈表時可能會頭疼它的使用，相比于數組的直接訪問，鏈表需要通過移動指針來遍歷節點修改節點的內容來完成增刪，因此不如數組直觀。我一直想要找到一個很好的例子來比喻鏈表運行的機制，直到有一次看諜戰片，我發現間諜聯絡的系統就是以鏈表形式工作的。所以我決定以間諜系統來舉例，介紹一下鏈表的工作原理。

　　假設你是民國時期軍統的頭目，你負責一個諜報鏈路。為了安全，你和你的手下們是單向聯系的。也就是說只能你聯系你的一個手下，由這個手下再去聯絡其他人，最終把暗號交到目標的手上。假設你的代號是A，你的手下是B，B的手下是C，C來執行任務。這個機制一直運轉很好，直到有一天，B因為神秘原因轉移了地點，導致A和B聯絡的時間變長，為了解決這個問題，你決定新增一個人手D專門負責A和B之間的聯絡，加快聯絡速度。你應該怎么辦呢？

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

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

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

　　代碼如下：

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

　　來看圖：

　　雙向鏈表

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

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

　　和單向鏈表相比，由于我們多了一個指針，理解和實現起來會更加容易，因為之前需要通過順序關系以及臨時變量完成的內容現在可以通過前向指針很輕易地實現了。

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

　　總結

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

　   以上就是動力節點Java培訓機構小編介紹的“Java基礎學習：Java雙鏈表結構視頻”的內容，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為你服務。