python雙向循環鏈表實例詳解
使用python實現雙向循環鏈表，供大傢參考，具體內容如下
雙向循環鏈表： 將所有的數據存放到節點中，每一個節點相連接，首尾鏈接，
每一個節點中有一個數據存儲區，和兩個鏈接區，一個鏈接前一個節點，一個鏈接下一個節點
雙向鏈表操作
1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節點
8、查找節點是否存在
代碼實現
# Functions 函數聲明 class Node(): """實例化節點類""" def __init__(self, item): self.item = item self.prev = None self.next = None class Linklist(): """ 存放節點類 """ def __init__(self): self.head = None # 1. 鏈表是否為空 def is_empty(self): return self.head == None # 2. 鏈表的長度 def length(self): """ 返回鏈表中所有數據的個數 實例化遊標，遍歷鏈表，使用計數器自增一 空鏈表 """ # 實例化遊標 cur = self.head # 判斷是否為空 if self.is_empty(): return 0 else: # 不為空 # 定義計數 count = 1 while cur.next != self.head: count+=1 cur = cur.next return count pass # 3. 遍歷鏈表 def travel(self): """ 遍歷鏈表 實例化遊標，遍歷鏈表，每次輸出節點的數據 空鏈表 隻有頭節點 """ # 實例化遊標 cur = self.head # 判斷是否為空 if self.is_empty(): return None else: # 不為空的情況 while cur.next != self.head: print(cur.item, end=' ') cur = cur.next print(cur.item) pass # 4. 鏈表頭部添加元素 def add(self, item): """ 頭節點添加 實例化節點， """ # 實例化節點 node = Node(item) # 實例化遊標 cur = self.head # 判斷是否為空 if self.is_empty(): node.next = node node.prev = node self.head = node else: # 鏈表不為空的情況 # 隻有一個節點的情況 # node.next = self.head node.next = cur node.prev = cur if cur.next == self.head: # print(cur.item) cur.prev = node cur.next = node self.head = node elif cur.next != self.head: pro = self.head while cur.next != self.head: cur = cur.next pro.prev = node cur.next = node self.head = node pass # 5. 鏈表尾部添加元素 def append(self, item): """ 鏈表尾部添加數據 實例化節點，實例化遊標，指向尾部節點，修改指向 鏈表為空 """ # 實例化節點 node = Node(item) # 實例化遊標 cur = self.head if self.is_empty(): self.add(item) else: # 不為空的情況 # 指針指向最後一個節點 self.head.prev = node node.next = self.head while cur.next != self.head: cur = cur.next node.prev = cur cur.next = node pass # 6. 鏈表指定位置添加元素 def insert(self, index, item): """ 指定位置添加數據 實例化節點， 實例化遊標 移動遊標到索引位置，更改指向 輸入索引大小判斷 鏈表是否為空 """ # 實例化節點 node = Node(item) # 實例化遊標 cur = self.head if index <= 0: self.add(item) elif index > (self.length()-1): self.append(item) else: # 中間添加數據 # 聲明計數 count = 0 print(index) while count < index-1: count+=1 cur = cur.next # print(cur.item) node.next = cur.next node.prev = cur cur.next.prev = node cur.next = node pass # 7. 鏈表刪除節點 def remove(self, item): """ 刪除數據 實例化遊標，遍歷鏈表，查找有沒有改數據 有，對改數據兩側的節點進行指向修改 """ # 實例化遊標 cur = self.head # 判斷是否為空 if self.is_empty(): return None else: # 不為空的情況下 # 如果刪除的是頭節點 if cur.item == item: # 如果隻有一個頭節點 if cur.next == self.head: self.head = None else: # self.head = cur.next pro = cur.next while cur.next != self.head: cur = cur.next cur.next = pro pro.prev = cur self.head = pro pass else: while cur.next != self.head: if cur.item == item: # print(cur.item) pro = cur.prev nex = cur.next pro.next = cur.next nex.prev = pro return True else: cur = cur.next # 如果是最後一個節點 if cur.item == item: cur.prev.next = self.head self.head.prev = cur.prev # 8. 查找節點是否存在 def search(self, item): """ 查詢指定的數據是否存在 實例化遊標 遍歷所有的節點。每個節點中判斷數據是否相等，相等，返回True """ # 實例化遊標 cur = self.head # 判斷是否為空 if self.is_empty(): return None else: # 不為空的情況 # 遍歷所有的節點 while cur.next != self.head: if cur.item == item: return True else: cur = cur.next if cur.item == item: return True pass
測試運行
# 程序的入口 if __name__ == "__main__": a = Linklist() a .add(400) a .add(300) a .add(200) a .add(100) a.append(10) a.append(11) a.add(1) a.insert(30, 12) # 1 100 200 300 400 10 11 12 a.remove(1) # 100 200 300 400 10 11 12 a.remove(12) # 100 200 300 400 10 11 a.remove(400) # # 100 200 300 10 11 a.remove(4000) print(a.search(100)) # True print(a.search(11)) # True print(a.search(111)) # None print(a.is_empty()) # False a.travel() # 100 200 300 10 11 print(a.length()) # 5 pass
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。