一、概念梳理

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

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

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

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

圖一、單鏈表

圖2:雙鏈表

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

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

二、如果使用python創(chuàng)建鏈表

（1）.將節(jié)點定義成一個數(shù)據(jù)結構

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

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

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

Listing1:The ListNode class

上面創(chuàng)建了最簡單的節(jié)點類，下面初始化ListNode的對象

Listing2:初始化節(jié)點

上面創(chuàng)建了三個獨立的節(jié)點

（2）創(chuàng)建一個單鏈表類

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

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

下面一一講解這些方法

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

Listing3:The SingleLinkedList class(part one)

(3)、添加節(jié)點

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

Listing4:The SinglelinkedList class(part two)

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

Listing5:The SingleLinkedList class(part three)

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

Listing6:The SingleLinkedList class(part four)

下面我們初始化SingleLinkedList的實例track，然后創(chuàng)建4個節(jié)點。

（4）查詢列表

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

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

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

Listing10:Removing a node by node number

（6）、創(chuàng)建一個雙鏈表

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

Listing11：Extended list node class

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

添加新的節(jié)點跟單鏈表有所不同

移除雙鏈表中的節(jié)點

python實際運用

輸出結果

（7）、使用隊列實現(xiàn)雙向列表

最新評論