創(chuàng)新互聯(lián)www.cdcxhl.cn八線動(dòng)態(tài)BGP香港云服務(wù)器提供商，新人活動(dòng)買多久送多久，劃算不套路！

從網(wǎng)站建設(shè)到定制行業(yè)解決方案，為提供網(wǎng)站制作、成都網(wǎng)站建設(shè)服務(wù)體系，各種行業(yè)企業(yè)客戶提供網(wǎng)站建設(shè)解決方案，助力業(yè)務(wù)快速發(fā)展。創(chuàng)新互聯(lián)將不斷加快創(chuàng)新步伐，提供優(yōu)質(zhì)的建站服務(wù)。

這篇文章將為大家詳細(xì)講解有關(guān)python實(shí)現(xiàn)鏈表的方法，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

=

一、概念梳理

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

一個(gè)單獨(dú)的列表元素叫做一個(gè)節(jié)點(diǎn)。這些節(jié)點(diǎn)不像數(shù)組一樣都按順序存儲(chǔ)在內(nèi)存當(dāng)中，相反，你可以通過一個(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ǔ)索引。

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

但是在python里面沒有提供像雙鏈表一樣的數(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)類定義成ListNode，該類在初始化實(shí)例對(duì)象時(shí)，定義了兩個(gè)實(shí)例變量，其中data用來存儲(chǔ)節(jié)點(diǎn)的值，next用來存儲(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)類，下面初始化ListNode的對(duì)象

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

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

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

現(xiàn)在我們定義一個(gè)名為SingleLinkedList的類去管理我們的節(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è)特殊值去查詢列表
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)

通過add_list_item()添加列表元素。先檢測(cè)是不是ListNode的實(shí)例，如果不是，就新建一個(gè)節(jié)點(diǎn)。如果列表還是空的話，就把該節(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)

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

Listing5:The SingleLinkedList class(part three)

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

Listing6:The SingleLinkedList class(part four)

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

（4）查詢列表

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

（5）從列表中移除一個(gè)元素

從列表中移除一個(gè)節(jié)點(diǎn) 時(shí)，指向該節(jié)點(diǎn)索引需要被移動(dòng)到，被移除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。被移除的節(jié)點(diǎn)會(huì)由python的垃圾回收機(jī)制清除

Listing10:Removing a node by node number

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

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

Listing11：Extended list node class

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

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

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

python實(shí)際運(yùn)用

輸出結(jié)果：

（7）使用隊(duì)列實(shí)現(xiàn)雙向列表

關(guān)于python實(shí)現(xiàn)鏈表的方法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

文章題目：python實(shí)現(xiàn)鏈表的方法-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://weahome.cn/article/gsosp.html