使用python實現鏈表操作

一、概念梳理

鏈表是計算機科學里面應用應用最廣泛的數據結構之一。它是最簡單的數據結構之一，同時也是比較高階的數據結構（例如棧、環形緩沖和隊列）

簡單的說，一個列表就是單數據通過索引集合在一起。在C里面這叫做指針。比方說，一個數據元素可以由地址元素，地理元素、路由信息活著交易細節等等組成。但是鏈表里面的元素類型都是一樣的，是一種特殊的列表。

一個單獨的列表元素叫做一個節點。這些節點不像數組一樣都按順序存儲在內存當中，相反，你可以通過一個節點指向另外一個節點的指針在內存不同的地方找到這些元素。列表最后一項習慣用NIL表示，相當于python里面的None

這里介紹兩種不同的列表——單鏈表和雙鏈表。雙鏈表中的某個節點只會指向列表中的下一個元素，但是在雙鏈表里面，當前節點同時也會指向前一個節點。所以雙鏈表會占用更多的內存，因為它需要額外的變量去存儲索引

圖一、單鏈表

圖2:雙鏈表

單鏈表可以從頭到尾順序查詢，但是反過來就不是那么容易了。然而，雙鏈表不管你是從哪個節點開始，從任意方向查詢都是一樣的。在單鏈表中增加和刪除節點只需要兩步，但是在雙鏈表里就需要四步了。

但是在python里面沒有提供像雙鏈表一樣的數據結構，所以我們可以自己創建一個這樣的數據結構

二、如果使用python創建鏈表

（1）.將節點定義成一個數據結構

首先我們將節點類定義成ListNode，該類在初始化實例對象時，定義了兩個實例變量，其中data用來存儲節點的值，next用來存儲下一個節點的索引，下面詳細介紹一下一個節點要定義的方法和屬性

__init__()：初始化節點
self.data：存儲節點的值
self.next：存儲指向下一個節點的索引
has_value()：將當前節點值和其他的值比較

上面的方法和屬性涵蓋了一個節點應有的基本屬性和行為

Listing1:The ListNode class

上面創建了最簡單的節點類，下面初始化ListNode的對象

Listing2:初始化節點

上面創建了三個獨立的節點

（2）創建一個單鏈表類

現在我們定義一個名為SingleLinkedList的類去管理我們的節點，它包含了下面這些方法：

__init__()：初始化對象
list_length()：返回節點數量
output_list():輸出節點值
add_list_item():在列表末尾增加一個新的節點
unordered_search():根據一個特殊值去查詢列表
remove_list_item_by_id()：根據節點id移除節點

下面一一講解這些方法

__init__()定義了head和tail，都初始化為None

Listing3:The SingleLinkedList class(part one)

(3)、添加節點

通過add_list_item()添加列表元素。先檢測是不是ListNode的實例，如果不是，就新建一個節點。如果列表還是空的話，就把該節點當作頭節點，如果不是空，就將當前節點指向下一個元素（也就是剛新添加的節點）。把新節點添加到列表當中

Listing4:The SinglelinkedList class(part two)

list_length()方法計算節點數量，返回列表的長度。在一個循環當中循環列表，self.next依次指向下一個節點

Listing5:The SingleLinkedList class(part three)

output_list()用來輸出新的節點值

Listing6:The SingleLinkedList class(part four)

下面我們初始化SingleLinkedList的實例track，然后創建4個節點。

（4）查詢列表

查詢整個列表使用unordered_search()。它需要使用一個額外的參數幫助查詢。列表的頭是切入點。

(5)、從列表中移除一個元素

從列表中移除一個節點 時，指向該節點索引需要被移動到，被移除節點的下一個節點。被移除的節點會由python的垃圾回收機制清除

Listing10:Removing a node by node number

（6）、創建一個雙鏈表

創建雙鏈表其實就是在ListNode的基礎上，在創建一個previous的屬性

Listing11：Extended list node class

然后我們就可以依據上面的定義新建一個雙鏈表類

添加新的節點跟單鏈表有所不同

移除雙鏈表中的節點

python實際運用

輸出結果

（7）、使用隊列實現雙向列表