數據結構——動手實戰雙向鏈表
- 2020 年 3 月 5 日
- 筆記
本文始發於個人公眾號：TechFlow，原創不易，求個關注
在之前介紹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的多變數賦值的方法，我們可以一行程式碼搞定。
程式碼如下：
def add(pos, new_node): new_node.next, pos.next = pos.next, new_node假如過了一段時間，B又回到了原處，我們不需要D了，要刪除這個節點該怎麼辦？很簡單，直接讓D將B的最新的聯絡方式給A就可以了。也就是說讓A跨過D指向B即可。
來看圖：
def delete(pos): pos.next = pos.next.next雙向鏈表
理解了單向鏈表，雙向鏈表也就很簡單了。雙向的意思也很明顯，每個節點除了記錄後繼節點的位置之外，還會記錄源頭節點的位置。有了雙向指針之後不僅是獲取來源節點方便而已，並且也可以很方便地對整個鏈表進行倒敘遍歷和頭部插入。
還記得我們之前Python專題當中介紹過的deque這個庫嗎？通過deque我們可以實現一個雙向增刪元素的隊列，結合雙向鏈表的定義，很容易發現deque其實就是保留了一部分api的雙向鏈表。換句話說deque是基於雙向鏈表實現的，就和棧是基於list實現的一樣。
和單向鏈表相比，由於我們多了一個指針，理解和實現起來會更加容易，因為之前需要通過順序關係以及臨時變數完成的內容現在可以通過前向指針很輕易地實現了。
下面附上雙向鏈表增刪的程式碼：
def add(pos, new_node): pos.next, new_node.next = new_node, pos.next new_node.pre, new_node.next.pre = pos, new_node def delete(pos): pos.next = pos.next.next # 這個時候pos.next已經更新 pos.next.pre = pos總結
雙向鏈表本身並不複雜，也沒有太多變化的花樣，和之前介紹的SkipList相比要簡單許多。我相信即使是初學者，只要自己動手實現一遍，也足夠掌握。在我初學數據結構的時候，我非常抗拒使用鏈表，除了覺得定址很麻煩，需要遍歷整個鏈表耗時很大之外。另一個根本的原因是在C++當中鏈表的編寫很麻煩，而且很容易有記憶體泄漏以及野指針問題。所以我當時儘可能地使用數組作為替代，並且甚至一度認為隨著記憶體價格的降低，總有一天我們可以拋棄鏈表這個結構。
直到後來我學習了作業系統之後，我找到了一個必須使用鏈表的理由。因為在作業系統當中，記憶體並不是連續的，大部分記憶體都是分散的。當我們創建一個數組的時候，我們其實是在想作業系統申請一塊連續的記憶體。我們申請的數組越大，這塊記憶體也就越大。顯然越大的記憶體越難申請到，因為記憶體大多被切分成了許多碎片，在資源不夠的情況下，作業系統需要做大量的工作才能將碎片搜集起來。
而鏈表因為通過指針定址，所以可以避免這個問題，鏈表當中的元素分散在記憶體各處，分攤了記憶體消耗的壓力。這也是在作業系統領域當中，鏈表大量使用的原因。
最後，由於篇幅限制，我們沒有放上全部的程式碼，想要獲取完整雙向鏈表程式碼的同學，可以關注我的公眾號，回復「雙向鏈表」獲取。
今天的文章就到這裡，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
