在之前介紹SkipList的文章當中，有一些同學反饋說由於對鏈表缺少認知以及瞭解，所以直接啃算法有些過於困難。加上之前的文章當中介紹過了棧，所以這次繼續線性表這個話題，我們來一起討論一下
鏈表。鏈表是很多數據結構的基礎，它的最大特點是支持快速的刪除和插入，因此在很多數據頻繁變動的場景下使用廣泛。而且鏈表的可拓展性較強，所以它的應用非常廣泛，相關的拓展和改進版本也很多。今天我們和大家介紹的是雙端鏈表，也稱為雙向鏈表，它是尋常單向鏈表的改進版本，也是會經常使用的鏈表。
單向鏈表
鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(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++當中鏈表的編寫很麻煩，而且很容易有內存洩漏以及野指針問題。所以我當時儘可能地使用數組作為替代，並且甚至一度認為隨著內存價格的降低，總有一天我們可以拋棄鏈表這個結構。
直到後來我學習了操作系統之後，我找到了一個必須使用鏈表的理由。因為在操作系統當中，內存並不是連續的，大部分內存都是分散的。當我們創建一個數組的時候，我們其實是在向操作系統申請一塊連續的內存。我們申請的數組越大，這塊內存也就越大。顯然越大的內存越難申請到，因為內存大多被切分成了許多碎片，在資源不夠的情況下，操作系統需要做大量的工作才能將碎片收集起來。
而鏈表因為通過指針尋址，所以可以避免這個問題，鏈表當中的元素分散在內存各處，分攤了內存消耗的壓力。這也是在操作系統領域當中，鏈表大量使用的原因。
今天的文章就到這裡，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
