一、概念梳理

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

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

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

這里介紹兩種不同的列表——單鏈表和雙鏈表。雙鏈表中的某個節(jié)點(diǎn)只會指向列表中的下一個元素，但是在雙鏈表里面，當(dāng)前節(jié)點(diǎn)同時也會指向前一個節(jié)點(diǎn)。所以雙鏈表會占用更多的內(nèi)存，因?yàn)樗枰~外的變量去存儲索引

圖一、單鏈表

圖2:雙鏈表

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

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

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

（1）.將節(jié)點(diǎn)定義成一個數(shù)據(jù)結(jié)構(gòu)

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

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

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

Listing1:The ListNode class

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

Listing2:初始化節(jié)點(diǎn)

上面創(chuàng)建了三個獨(dú)立的節(jié)點(diǎn)

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

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

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