建站
咨詢
售后
建站咨詢
新聞中心
成都創(chuàng)新互聯(lián)公司專注于企業(yè)全網營銷推廣、網站重做改版、雞西梨樹網站定制設計、自適應品牌網站建設、H5技術、商城網站定制開發(fā)、集團公司官網建設、外貿網站制作、高端網站制作、響應式網頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為雞西梨樹等各大城市提供網站開發(fā)制作服務。
一、概念梳理
鏈表是計算機科學里面應用應用最廣泛的數(shù)據結構之一。它是最簡單的數(shù)據結構之一，同時也是比較高階的數(shù)據結構（例如棧、環(huán)形緩沖和隊列）
簡單的說，一個列表就是單數(shù)據通過索引集合在一起。在C里面這叫做指針。比方說，一個數(shù)據元素可以由地址元素，地理元素、路由信息活著交易細節(jié)等等組成。但是鏈表里面的元素類型都是一樣的，是一種特殊的列表。
一個單獨的列表元素叫做一個節(jié)點。這些節(jié)點不像數(shù)組一樣都按順序存儲在內存當中，相反，你可以通過一個節(jié)點指向另外一個節(jié)點的指針在內存不同的地方找到這些元素。列表最后一項習慣用NIL表示，相當于python里面的None。
這里介紹兩種不同的列表——單鏈表和雙鏈表。雙鏈表中的某個節(jié)點只會指向列表中的下一個元素，但是在雙鏈表里面，當前節(jié)點同時也會指向前一個節(jié)點。所以雙鏈表會占用更多的內存，因為它需要額外的變量去存儲索引。
單鏈表可以從頭到尾順序查詢，但是反過來就不是那么容易了。然而，雙鏈表不管你是從哪個節(jié)點開始，從任意方向查詢都是一樣的。在單鏈表中增加和刪除節(jié)點只需要兩步，但是在雙鏈表里就需要四步了。
但是在python里面沒有提供像雙鏈表一樣的數(shù)據結構，所以我們可以自己創(chuàng)建一個這樣的數(shù)據結構。
二、如果使用python創(chuàng)建鏈表
（1）將節(jié)點定義成一個數(shù)據結構
首先我們將節(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():根據一個特殊值去查詢列表 remove_list_item_by_id()：根據節(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
然后我們就可以依據上面的定義新建一個雙鏈表類
添加新的節(jié)點跟單鏈表有所不同
移除雙鏈表中的節(jié)點
python實際運用
輸出結果：
（7）使用隊列實現(xiàn)雙向列表
python學習網，免費的在線學習python平臺，歡迎關注！
本文名稱：創(chuàng)新互聯(lián)Python教程：python怎么實現(xiàn)鏈表
文章地址：http://www.5511xx.com/article/dpsgeoc.html
