快捷導(dǎo)航

使用python實(shí)現(xiàn)鏈表操作

更新時(shí)間：2018年01月26日 16:36:11 作者：黑加侖妞

鏈表是計(jì)算機(jī)科學(xué)里面應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。這篇文章主要介紹了使用python實(shí)現(xiàn)鏈表操作,需要的朋友可以參考下

一、概念梳理

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

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

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

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

圖一、單鏈表

圖2:雙鏈表

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

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

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

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

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

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

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

Listing1:The ListNode class

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

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

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

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

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

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

下面一一講解這些方法

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

Listing3:The SingleLinkedList class(part one)

(3)、添加節(jié)點(diǎn)

通過(guò)add_list_item()添加列表元素。先檢測(cè)是不是ListNode的實(shí)例，如果不是，就新建一個(gè)節(jié)點(diǎn)。如果列表還是空的話(huà)，就把該節(jié)點(diǎn)當(dāng)作頭節(jié)點(diǎn)，如果不是空，就將當(dāng)前節(jié)點(diǎn)指向下一個(gè)元素（也就是剛新添加的節(jié)點(diǎn)）。把新節(jié)點(diǎn)添加到列表當(dāng)中

Listing4:The SinglelinkedList class(part two)