溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了python雙向鏈表原理與實現方法。分享給大家供大家參考，具體如下：
雙向鏈表
一種更復雜的鏈表是“雙向鏈表”或“雙面鏈表”。每個節點有兩個鏈接：一個指向前一個節點，當此節點為第一個節點時，指向空值；而另一個指向下一個節點，當此節點為最后一個節點時，指向空值。
操作
實現
class Node(object):
"""雙向鏈表節點"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList(object):
"""雙向鏈表"""
def __init__(self):
self.__head = None
def is_empty(self):
"""判斷鏈表是否為空"""
return self.__head == None
def length(self):
"""返回鏈表的長度"""
cur = self.__head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍歷鏈表"""
cur = self.__head
while cur != None:
print cur.item,
cur = cur.next
print ""
def add(self, item):
"""頭部插入元素"""
node = Node(item)
if self.is_empty():
# 如果是空鏈表，將_head指向node
self.__head = node
else:
# 將node的next指向_head的頭節點
node.next = self.__head
# 將_head的頭節點的prev指向node
self.__head.prev = node
# 將_head 指向node
self.__head = node
def append(self, item):
"""尾部插入元素"""
node = Node(item)
if self.is_empty():
# 如果是空鏈表，將_head指向node
self.__head = node
else:
# 移動到鏈表尾部
cur = self.__head
while cur.next != None:
cur = cur.next
# 將尾節點cur的next指向node
cur.next = node
# 將node的prev指向cur
node.prev = cur
def search(self, item):
"""查找元素是否存在"""
cur = self.__head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
指定位置插入節點
def insert(self, pos, item):
"""在指定位置添加節點"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self.__head
count = 0
# 移動到指定位置的前一個位置
while count < (pos-1):
count += 1
cur = cur.next
# 將node的prev指向cur
node.prev = cur
# 將node的next指向cur的下一個節點
node.next = cur.next
# 將cur的下一個節點的prev指向node
cur.next.prev = node
# 將cur的next指向node
cur.next = node
刪除元素
def remove(self, item):
"""刪除元素"""
cur = self.__head
while cur != None:
# 找到了要刪除的元素
if cur.item == item:
# 先判斷此結點是否是頭節點
# 頭節點
if cur == self.__head:
self.__head = cur.next
# 如果存在下一個結點，則設置下一個結點
if cur.next:
# 判斷鏈表是否只有一個結點
cur.next.prev = None
else:
cur.prev.next = cur.next
# 如果存在下一個結點，則設置下一個結點
if cur.next:
cur.next.prev = cur.prev
break
else:
cur = cur.next
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
