Python單向鏈表和雙向鏈表原理與用法實例詳解
本文實例講述了Python單向鏈表和雙向鏈表原理與用法。分享給大家供大家參考，具體如下：
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，鏈表在循環(huán)遍歷的時候效率不高，但是在插入和刪除時優(yōu)勢比較大。
鏈表由一個個節(jié)點組成。
單向鏈表的節(jié)點分為兩個部分：存儲的對象和對下一個節(jié)點的引用。注意是指向下一個節(jié)點。
而雙向鏈表區(qū)別于單向鏈表的是它是由三個部分組成：存儲的對象、對下一個節(jié)點的引用、對上一個節(jié)點的引用，可以實現(xiàn)雙向遍歷。
單向列表的結(jié)構(gòu)如下圖：
head是頭節(jié)點，tail是尾節(jié)點，每個節(jié)點由Data存儲對象和Next對下一個節(jié)點引用組成
下面說一下單向鏈表插入和刪除的過程。
插入一個新節(jié)點：
原理：前一個節(jié)點的Next指向當前新節(jié)點，新節(jié)點的Next指向要插入節(jié)點位置的后一個節(jié)點。
注意：在實際應(yīng)用時需要考慮插入位置是頭結(jié)點和尾節(jié)點的情況。
刪除一個節(jié)點：
原理：找到要刪除節(jié)點的上一個節(jié)點，直接上一個節(jié)點的Next指向刪除位置的下一個節(jié)點。
注意：在實際應(yīng)用中需要考慮到刪除的節(jié)點是否是頭節(jié)點或尾節(jié)點，需要考慮到鏈表的長度。
下面附上一個用python寫的單鏈表的例子。
class Node:
next = None
data = None
def __init__(self,nodeData):
self.data = nodeData
class List:
head = None
size = 0
def __init__(self):
self.size = 0
self.head = None
#遍歷鏈表
def a(self):
print("avx")
def printlist(self):
p=self.head
while(p is not None):
print(p.data)
p=p.next
print("——————————————————————————————————————")
def insertlink(self, a, newdata):
newnode = Node(newdata)
if self.size == 0:
print("The link is none")
self.head = newnode
self.size = self.size+1
else:
p = self.head
while(p is not None )and (p.data != a):
p = p.next
if p.next is None:
p.next = newnode
self.size = self.size + 1
else:
newnode.next = p.next
p.next = newnode
self.size = self.size + 1
#刪除鏈表中的節(jié)點
def deldata(self,a):
if self.size == 0:
print("The link is none")
elif self.size ==1:
self.head = None
self.size = self.size -1
else:
p = self.head
while(p is not None )and (p.data != a):
q = p
p = p.next
if p is None:
print("Can't find a")
elif p == self.head:
self.head = p.next
elif p.data ==a and p.next is not None:
q.next = q.next.next
self.size = self.size - 1
else:
q.next = None
self.size = self.size - 1
#修改鏈表中的指定節(jié)點
def updatelink(self,a,b):
p = self.head
print(p.data)
while(p is not None ) and (p.data!=a):
p = p.next
if p is None:
print("Can't find a")
else:
p.data = b
if __name__=="__main__":
p = List()
p.insertlink(1,1)
p.insertlink(1,2)
p.insertlink(1,3)
p.insertlink(1,4)
print("_________________________---insertlink")
p.printlist()
print("_________________________--chalink")
p.updatelink(2,5)
p.printlist()
print("___________________________-----dellink")
p.deldata(5)
p.printlist()
運行結(jié)果：
The link is none
_________________________---insertlink
1
4
3
2
——————————————————————————————————————
_________________________--chalink
1
1
4
3
5
——————————————————————————————————————
___________________________-----dellink
1
4
3
——————————————————————————————————————
雙向鏈表的結(jié)構(gòu)如下圖：
head是頭節(jié)點，tail是尾節(jié)點，每個節(jié)點由Data存儲對象，Next對下一個節(jié)點的引用和Pre對上一個節(jié)點的引用組成。可以實現(xiàn)雙向的遍歷
下面說一下雙向鏈表的插入和刪除
插入一個新節(jié)點：
原理：
找到要插入的節(jié)點位置，新節(jié)點的Next指向插入位置的下一個節(jié)點，插入位置的下一個節(jié)點的Pre指向新節(jié)點。
插入位置節(jié)點的左側(cè)Next指向新節(jié)點，新節(jié)點的Pre指向左側(cè)的節(jié)點。
刪除一個節(jié)點：
說明：
找到要刪除的節(jié)點的上一個節(jié)點
直接把上一個節(jié)點的Next指向要刪除節(jié)點的下一個節(jié)點
并把要刪除節(jié)點的下一個節(jié)點的Pre指向要上出節(jié)點的上一個節(jié)點即可
雙向鏈表的代碼：
class Node():
data = None
nextnode = None
prenode = None
def __init__(self, data):
self.data = data
class PersonChan():
size = 0
head = None
tail = None
def __init__(self):
self.head = None
self.tail = None
self.size = 0
#增加節(jié)點
def add_node(self, a):
newnode = Node(a)
if(self.head == None):
self.head = newnode
self.head.prenode = None
self.tail = newnode
self.tail.prenode = None
self.tail.nextnode = None
self.size = self.size+1
else:
temp = self.head
while temp.nextnode is not None:#返回尾節(jié)點tail
temp = temp.nextnode
temp.nextnode = newnode
self.tail = newnode
self.tail.prenode = temp
self.tail.nextnode = None
self.size = self.size+1
#在查找到的a后面增加節(jié)點
def ins_node(self,a,b):
newnode = Node(b)
if self.head ==None:
self.head = newnode
self.tail = newnode
print("Insert success:",newnode.data)
self.size = self.size +1
else:
temp = self.head
while(temp is not None)&(temp.data != a):
temp = temp.nextnode
if temp.nextnode == None:
temp.nextnode = newnode
self.tail = newnode
self.tail.prenode = temp
self.tail.nextnode = None
temp = None
print("Insert success:",newnode.data)
self.size = self.size+1
else:
newnode.prenode = temp
newnode.nextnode = temp.nextnode
temp.nextnode = newnode
print("Insert success:",newnode.data)
self.size = self.size+1
#刪除節(jié)點
def del_node(self,a):
if self.head == None:
pass
elif self.head.data == a:
if self.size ==1:
self.head = None
self.tail = None
self.size = self.size-1
else:
self.head = self.head.nextnode
self.size = self.size -1
else:
temp = self.head.nextnode
while (temp is not None) and (temp.data != a):
temp = temp.nextnode
p = temp.prenode
if temp != None:
if temp.nextnode == None:
self.tail = p
self.tail.nextnod = None
else:
p.nextnode = temp.nextnode
temp = None
self.size = self.size -1
print("Delete is success:",a)
def listall(self):#正序排列
if self.size == 0:
print("No data in the list")
else:
temp = self.head
while(temp is not None):
print(temp.data)
temp = temp.nextnode
def lista(self):#倒序排列
if self.size == 0:
print("No data in the list")
temp = self.tail
while(temp is not None):
print(temp.data)
temp = temp.prenode
if __name__ == '__main__':
link = PersonChan()
link.add_node(1)
link.add_node(2)
link.add_node(3)
link.add_node(4)
link.listall()
print("The list's size is:",link.size)
link.lista()
運行結(jié)果：
1
2
3
4
("The list's size is:", 4)
4
3
2
1
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
在本篇文章里小編給大家整理了一篇關(guān)于Python的信號庫Blinker用法詳解內(nèi)容，有興趣的朋友們可以學習下。2020-12-12
這篇文章主要介紹了Python pytest裝飾器總結(jié),本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
這篇文章主要為大家詳細介紹了python爬取基于m3u8協(xié)議的ts文件并合并，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-04-04
Python腳本實現(xiàn)datax全量同步mysql到hive
這篇文章主要和大家分享一下mysql全量同步到hive自動生成json文件的python腳本,文中的示例代碼講解詳細,有需要的小伙伴可以參加一下2024-10-10
本文主要介紹了Python給對象數(shù)組排序的方法實現(xiàn),可以使用sorted()函數(shù)或list.sort()方法來對對象數(shù)組按照第二個值進行排序,具有一定的參考價值,感興趣的可以了解一下2025-03-03
三個Python常用的數(shù)據(jù)清洗處理方式總結(jié)
這篇文章主要為大家詳細介紹了python數(shù)據(jù)處理過程中三個主要的數(shù)據(jù)清洗說明，分別是缺失值/空格/重復(fù)值的數(shù)據(jù)清洗，感興趣的小伙伴可以了解一下2022-12-12
Pycharm創(chuàng)建文件時自動生成文件頭注釋(自定義設(shè)置作者日期)
這篇文章主要介紹了Pycharm創(chuàng)建文件時自動生成文件頭注釋(自定義設(shè)置作者日期)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11![python_array[0][0]與array[0,0]的區(qū)別詳解](http://img.jbzj.com/images/xgimg/bcimg7.png)
python_array[0][0]與array[0,0]的區(qū)別詳解
今天小編就為大家分享一篇python_array[0][0]與array[0,0]的區(qū)別詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02
Python使用正則表達式獲取網(wǎng)頁中所需要的信息
這篇文章主要介紹了Python使用正則獲取網(wǎng)頁中所需要的信息的相關(guān)資料,需要的朋友可以參考下2018-01-01
python字符串加密解密的三種方法分享(base64 win32com)
這篇文章主要介紹了python字符串加密解密的三種方法,包括用base64、使用win32com.client、自己寫的加密解密算法三種方法，大家參考使用吧2014-01-01