快捷導(dǎo)航

python雙向循環(huán)鏈表實(shí)例詳解

更新時(shí)間：2022年05月25日 11:35:24 作者：python-行者

這篇文章主要為大家詳細(xì)介紹了python雙向循環(huán)鏈表實(shí)例，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

使用python實(shí)現(xiàn)雙向循環(huán)鏈表，供大家參考，具體內(nèi)容如下

雙向循環(huán)鏈表：將所有的數(shù)據(jù)存放到節(jié)點(diǎn)中，每一個(gè)節(jié)點(diǎn)相連接，首尾鏈接，
每一個(gè)節(jié)點(diǎn)中有一個(gè)數(shù)據(jù)存儲(chǔ)區(qū)，和兩個(gè)鏈接區(qū)，一個(gè)鏈接前一個(gè)節(jié)點(diǎn)，一個(gè)鏈接下一個(gè)節(jié)點(diǎn)

雙向鏈表操作

1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節(jié)點(diǎn)
8、查找節(jié)點(diǎn)是否存在

代碼實(shí)現(xiàn)

# Functions ?函數(shù)聲明
class Node():
? ? """實(shí)例化節(jié)點(diǎn)類"""
? ? def __init__(self, item):
? ? ? ? self.item = item
? ? ? ? self.prev = None
? ? ? ? self.next = None

class Linklist():
? ? """
? ? 存放節(jié)點(diǎn)類
? ? """
? ? def __init__(self):
? ? ? ? self.head = None

? ? # 1. 鏈表是否為空
? ? def is_empty(self):
? ? ? ? return self.head == None

? ? # 2. 鏈表的長度
? ? def length(self):
? ? ? ? """
? ? ? ? 返回鏈表中所有數(shù)據(jù)的個(gè)數(shù)
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表，使用計(jì)數(shù)器自增一
? ? ? ? 空鏈表

? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return 0
? ? ? ? else:
? ? ? ? ? ? # 不為空
? ? ? ? ? ? # 定義計(jì)數(shù)
? ? ? ? ? ? count = 1
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? return count
? ? ? ? ? ? pass

? ? # 3. 遍歷鏈表
? ? def travel(self):
? ? ? ? """
? ? ? ? 遍歷鏈表
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表，每次輸出節(jié)點(diǎn)的數(shù)據(jù)
? ? ? ? 空鏈表
? ? ? ? 只有頭節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? 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):
? ? ? ? """
? ? ? ? 頭節(jié)點(diǎn)添加
? ? ? ? 實(shí)例化節(jié)點(diǎn)，
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? node.next = node
? ? ? ? ? ? node.prev = node
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? # 鏈表不為空的情況
? ? ? ? ? ? # 只有一個(gè)節(jié)點(diǎn)的情況
? ? ? ? ? ? # 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):
? ? ? ? """
? ? ? ? 鏈表尾部添加數(shù)據(jù)
? ? ? ? 實(shí)例化節(jié)點(diǎn)，實(shí)例化游標(biāo)，指向尾部節(jié)點(diǎn)，修改指向
? ? ? ? 鏈表為空
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況
? ? ? ? ? ? # 指針指向最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? 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):
? ? ? ? """
? ? ? ? 指定位置添加數(shù)據(jù)
? ? ? ? 實(shí)例化節(jié)點(diǎn)， 實(shí)例化游標(biāo)
? ? ? ? 移動(dòng)游標(biāo)到索引位置，更改指向
? ? ? ? 輸入索引大小判斷
? ? ? ? 鏈表是否為空
? ? ? ? """
? ? ? ? # 實(shí)例化節(jié)點(diǎn)
? ? ? ? node = Node(item)
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? if index <= 0:
? ? ? ? ? ? self.add(item)
? ? ? ? elif index > (self.length()-1):
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? # 中間添加數(shù)據(jù)
? ? ? ? ? ? # 聲明計(jì)數(shù)
? ? ? ? ? ? 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. 鏈表刪除節(jié)點(diǎn)
? ? def remove(self, item):
? ? ? ? """
? ? ? ? 刪除數(shù)據(jù)
? ? ? ? 實(shí)例化游標(biāo)，遍歷鏈表，查找有沒有改數(shù)據(jù)
? ? ? ? 有，對改數(shù)據(jù)兩側(cè)的節(jié)點(diǎn)進(jìn)行指向修改
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況下
? ? ? ? ? ? # 如果刪除的是頭節(jié)點(diǎn)
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? # 如果只有一個(gè)頭節(jié)點(diǎn)
? ? ? ? ? ? ? ? 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
? ? ? ? ? ? ? ? # 如果是最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? cur.prev.next = self.head
? ? ? ? ? ? ? ? ? ? self.head.prev = cur.prev

? ? # 8. 查找節(jié)點(diǎn)是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查詢指定的數(shù)據(jù)是否存在
? ? ? ? 實(shí)例化游標(biāo)
? ? ? ? 遍歷所有的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)中判斷數(shù)據(jù)是否相等，相等，返回True
? ? ? ? """
? ? ? ? # 實(shí)例化游標(biāo)
? ? ? ? cur = self.head
? ? ? ? # 判斷是否為空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不為空的情況
? ? ? ? ? ? # 遍歷所有的節(jié)點(diǎn)
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? pass

測試運(yùn)行

# 程序的入口
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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: