python實現雙鏈表
本文實例為大傢分享瞭python實現雙鏈表的具體代碼，供大傢參考，具體內容如下
實現雙鏈表需要註意的地方
1、如何插入元素，考慮特殊情況：頭節點位置，尾節點位置；一般情況：中間位置
2、如何刪除元素，考慮特殊情況：頭結點位置，尾節點位置；一般情況：中間位置
代碼實現
1.構造節點的類和鏈表類
class Node: def __init__(self, data): self.data = data self.next = None self.previous = None class DoubleLinkList: '''雙鏈表''' def __init__(self, node=None): self._head = node
以下方法均在鏈表類中實現
2. 判斷鏈表是否為空
def is_empty(self): return self._head is None
3. 輸出鏈表的長度
def length(self): count = 0 if self.is_empty(): return count else: current = self._head while current is not None: count += 1 current = current.next return count
4. 遍歷鏈表
def travel(self):
current = self._head
while current is not None:
print("{0}".format(current.data), end=" ")
current = current.next
print("")
5.頭插法增加新元素
def add(self, item): node = Node(item) # 如果鏈表為空，讓頭指針指向當前節點 if self.is_empty(): self._head = node # 註意插入的順序， else: node.next = self._head self._head.previous = node self._head = node
6. 尾插法增加新元素
def append(self, item): node = Node(item) # 如果鏈表為空，則直接讓頭指針指向該節點 if self.is_empty(): self._head = node # 需要找到尾節點，然後讓尾節點的與新的節點進行連接 else: current = self._head while current.next is not None: current = current.next current.next = node node.previous = current
7. 查找元素是否存在鏈表中
def search(self, item): current = self._head found = False while current is not None and not found: if current.data == item: found = True else: current = current.next return found
8. 在某個位置中插入元素
def insert(self, item, pos): # 特殊位置，在第一個位置的時候，頭插法 if pos <= 0: self.add(item) # 在尾部的時候，使用尾插法 elif pos > self.length() - 1: self.append(item) # 中間位置 else: node = Node(item) current = self._head count = 0 while count < pos - 1: current = current.next count += 1 # 找到瞭要插入位置的前驅之後，進行如下操作 node.previous = current node.next = current.next current.next.previous = node current.next = node
# 換一個順序也可以進行 def insert2(self, item, pos): if pos <= 0: self.add(item) elif pos > self.length() - 1: self.append(item) else: node = Node(item) current = self._head count = 0 while count < pos: current = current.next count += 1 node.next = current node.previous = current.previous current.previous.next = node current.previous = node
9. 刪除元素
def remove(self, item):
current = self._head
if self.is_empty():
return
elif current.data == item:
# 第一個節點就是目標節點，那麼需要將下一個節點的前驅改為None 然後再將head指向下一個節點
current.next.previous = None
self._head = current.next
else:
# 找到要刪除的元素節點
while current is not None and current.data != item:
current = current.next
if current is None:
print("not found {0}".format(item))
# 如果尾節點是目標節點，讓前驅節點指向None
elif current.next is None:
current.previous.next = None
# 中間位置，因為是雙鏈表，可以用前驅指針操作
else:
current.previous.next = current.next
current.next.previous = current.previous
# 第二種寫法 def remove2(self, item): """刪除元素""" if self.is_empty(): return else: cur = self._head if cur.data == item: # 如果首節點的元素即是要刪除的元素 if cur.next is None: # 如果鏈表隻有這一個節點 self._head = None else: # 將第二個節點的prev設置為None cur.next.prev = None # 將_head指向第二個節點 self._head = cur.next return while cur is not None: if cur.data == item: # 將cur的前一個節點的next指向cur的後一個節點 cur.prev.next = cur.next # 將cur的後一個節點的prev指向cur的前一個節點 cur.next.prev = cur.prev break cur = cur.next
10. 演示
my_list = DoubleLinkList()
print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))
print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))
print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))
print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))
print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))
print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))
print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。