用Python實現鏈表

鏈表是每個程序員都應該知道的基本數據結構。這篇文章介紹如何用Python以函數式編程的形式實現鏈表。

構建鏈表

我們的鏈表由兩個基礎組件構建而成：Nil和Cons。Nil代表空列表，或者其他列表的葉子節點。Cons操作在鏈表的最前端插入一個新節點。

我們構建的鏈表使用嵌套的二元元組。例如，一個鏈表[1, 2, 3]由表達式cons(1, cons(2, cons(3, Nil)))表示，這個表示等價於嵌套元組(1, (2, (3, Nil)))

我們為什麼使用這個結構？

首先，cons操作在函數式編程領域有著深遠的歷史。從 Lisp 的 cons cells 到 ML 和 Scala 的::操作符，cons操作隨處可見。你可以把它當作一個動詞使用。

其次，元組用來定義簡單數據結構很方便。像我們這樣定義一個簡單的鏈表，實際上沒有必要單獨為它寫一個類。當然，我也希望能讓這篇介紹保持簡潔。

第三，元組在Python中是不可變元素，保證了它被創建後不會被修改。不可變性非常重要，它能幫助你寫出簡單、並且線程安全的代碼。我喜歡John Carmack的一篇文章，他論述了函數式編程和不可變性的關係。

把元組的構建過程抽象出來，使我們能夠更靈活地控制鏈表的Python表現形式。例如，除了用元組表示這個二元結構，我們還可以使用Python中lambda匿名函數來表示。

為了給複雜的列表操作寫簡單的測試，我要引入幫助函數lst。它允許我們定義一個更複雜的列表結構，而不需要反覆嵌套cons操作。

基本操作

所有的鏈表操作都可以歸結為三個基本的操作：head, tail 和 is_empty。

• head返回鏈表中的第一個節點

• tail返回除了第一個節點的整個鏈表

• is_empty在鏈表中沒有節點時返回True

一會兒你就會看到，這三個操作足以執行一些簡單的排序演算法了，比如插入排序法。

長度和合併

長度操作返回鏈表節點的數量。為了算出鏈表的長度，我們需要遍歷整個鏈表（假設鏈表有n個節點）。所以這個演算法的時間複雜度是O(n)。

concat把兩個鏈表合併在一起。concat(xs, ys)的結果是一個全新的鏈表，這個鏈表包含了xs鏈表的全部節點，然後在後面接上ys鏈表的全部節點。這個功能就是一個簡單的合併邏輯。

last, init 和 鏈表反轉

基本操作 head, tail 都有對應的反向操作 last, init。last 是返回非空鏈表的最後一個節點，init 是返回除了最後一個節點的整個鏈表。

這兩種操作的時間複雜度都是O(n)。因此如果你會頻繁地使用last或者init操作，那麼把列表反轉過來會更好。下面reverse函數實現了簡單的反轉功能，不過它的時間複雜度是O(n²)

掐頭去尾

接下來的兩個操作take和drop是基礎操作head和tail的泛化。take(2, xs)表示返回鏈表的頭兩個節點，而drop(3, xs)表示返回除了最後3個節點的整個鏈表。

獲取節點

在鏈表上隨機獲取節點並不高效，時間複雜度在O(n)。獲取節點的操作我們稱之為apply，它可以由head和drop操作組合完成。

更複雜的例子

我們用最簡單的head，tail 和 is_empty操作來執行一個簡單的排序演算法：插入排序。

下面的to_string方法把整個列錶轉換為一個字元串，字元串的格式類似於Python的列表。這個功能對於調試很有幫助。

補充說明

這篇文章講解了使用Python實現一個鏈表的全部操作。但是這個代碼示例有其局限性，最好不要在生產環境中使用。如果你的鏈表太大，會超出Python的遞歸層次限制。（CPython沒有優化尾遞歸的情況）

英文原文：https://dbader.org/blog/functional-linked-lists-in-python

譯者：詩書塞外

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！