Python雙鏈表原理與實現方法詳解

本文實例講述了Python雙鏈表原理與實現方法。分享給大家供大家參考，具體如下：

Python實現雙鏈表

文章目錄

• Python實現雙鏈表
  • 單鏈表與雙鏈表比較
  • 雙鏈表的實現
    • 定義鏈表節點
    • 初始化雙鏈表
    • 判斷鏈表是否為空
    • 雙鏈表尾部添加元素
    • 雙鏈表頭部添加節點：
    • 雙鏈表表頭刪除
    • 雙鏈表按位置插入
    • 雙鏈表刪除指定節點
    • 完整代碼

單鏈表與雙鏈表比較

• 雙鏈表比單鏈表多一個前驅指針位置，空間效率不占優勢
• 由于雙鏈表中的節點既可以向前也可以向后，相比單鏈表在查找方面效率更高（可使用二分法）

雙鏈表的實現

定義鏈表節點

• class Node(object):
    def __init__(self, value=None, prev=None, next=None):
      self.value = value	# 節點數據域
      self.prev = prev	# 節點前驅指針
      self.next = next	# 節點后繼指針
  

初始化雙鏈表

• 在雙鏈表類的構造方法中定義頭指針以及鏈表長度屬性

• class doubleLinked(object):
  
    def __init__(self):
      self.head = Node()	# 頭指針節點，用于確定鏈表第一個節點，不計入鏈表實際長度
      self.length = 0
  

判斷鏈表是否為空

• 通過實例屬性self.length是否為0判斷鏈表是否為空

• # 判斷鏈表是否為空
    def is_Empty(self):
      return self.length == 0
  

雙鏈表尾部添加元素

• 根據傳入的value值創建node節點對象

• 判斷是否為空，若為空則插入節點的前驅節點為head頭指針節點,head頭指針指向node

• 如果鏈表非空：

  • 通過while循環判斷當前節點的后繼節點是否為None，找到尾節點
  • 找到尾節點后，將尾節點指向待添加節點，待添加節點前驅節點域指向原偽節點
  • 長度+1

• # 尾部添加
    def append(self, value):
      node = Node(value)
      if self.length == 0:
        node.prev = self.head
        self.head.next = node
      else:
        curnode = self.head.next
        while curnode.next != None:
          curnode = curnode.next
        curnode.next = node
        node.prev = curnode
      self.length += 1
  

雙鏈表頭部添加節點：

• 調用類方法is_Empty()判斷是否為空，若為空則直接調用append()方法

• 當鏈表非空時

  • 首先創建待添加節點對象node
  • 設置中間變量存放原頭指針指向的節點
  • 將頭指針重新指向待添加節點
  • 新添加節點后驅指針域指向中間變量(即原第一個節點)
  • 中間變量前驅指針域指向新添加節點
  • 鏈表長度+1

• # 頭部添加
    def add(self, value):
      if self.is_Empty():
        self.append(value)
      node = Node(value)
      curnode = self.head.next
      self.head.next = node
      node.next = curnode
      curnode.prev = node
      self.length += 1
  

雙鏈表表頭刪除

• 老樣子，依舊要先判斷原鏈表是否為空，為空的時候返回False

• 鏈表不為空時：

  • 將頭指針指向的節點存放到中間變量curnode
  • 將頭指針指向的節點指向頭指針(也就是第一個節點現在變成了頭指針)
  • 新頭指針指向中間變量的后驅節點
  • 鏈表長度-1

• # 刪除表頭節點
    def remove(self):
      if self.is_Empty():
        return False
      curnode = self.head.next
      self.head = self.head.next
      self.head.next = curnode.next
      self.length -= 1
  

雙鏈表按位置插入

• 接收兩個位置參數，postion和value

• 創建待插入節點對象

• 變量curnode存放當前節點，變量i初始值為2(位置參數<2時，默認插入到第二個位置，>2時，通過while循環找到指定位置節點再進行插入)

• 找到指定位置后，待插入節點的后驅指針指向當前節點curnode的后繼節點，待插入節點的前驅節點為當前節點。

• 當前節點的原后驅節點的前驅指針域指向待插入節點，當前節點curnode的后驅節點變更為插入節點

• 鏈表長度+1

• # 插入到指定位置
    def insert(self, postion, value):
      node = Node(value)
      curnode = self.head.next
      i = 2
      while i < postion:
        i += 1
        curnode = curnode.next
      node.next = curnode.next
      node.prev = curnode
      curnode.next.prev = node
      curnode.next = node
      self.length += 1
  

雙鏈表刪除指定節點

• 依舊需要判斷是否為空，為空時返回False

• 鏈表不為空時：

  • 設置中間變量curnode存放當前節點
  • while循環找到相匹配的值的節點
  • 找到相應節點后，應刪除節點的前驅節點的后繼節點更改為應刪除節點的后繼節點；應刪除節點的后繼節點的前驅更改為應刪除節點的前驅；
  • 應刪除節點后繼指針指向自己
  • 鏈表長度-1

• # 刪除指定節點
    def delete(self, value):
      if self.is_Empty():
        return False
      curnode = self.head.next
      while curnode.value != value:
        curnode = curnode.next
      curnode.prev.next = curnode.next
      curnode.next.prev = curnode.prev
      curnode.next = curnode
      self.length -= 1
  

完整代碼

class Node(object):
  def __init__(self, value=None, prev=None, next=None):
    self.value = value
    self.prev = prev
    self.next = next


class doubleLinked(object):

  def __init__(self):
    self.head = Node()
    self.length = 0

  def __iter__(self):
    for node in self.iter_node():
      yield node.value

  # 對鏈表進行可迭代操作
  def iter_node(self):
    curnode = self.head.next
    while curnode.next != None:
      yield curnode
      curnode = curnode.next
    if curnode.next == None:
      yield curnode

  # 判斷鏈表是否為空
  def is_Empty(self):
    return self.length == 0

  # 尾部添加
  def append(self, value):
    node = Node(value)
    if self.length == 0:
      node.prev = self.head
      self.head.next = node
    else:
      curnode = self.head.next
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node
      node.prev = curnode
    self.length += 1

  # 頭部添加
  def add(self, value):
    if self.is_Empty():
      self.append(value)
    node = Node(value)
    curnode = self.head.next
    self.head.next = node
    node.next = curnode
    curnode.prev = node
    self.length += 1

  # 插入到指定位置
  def insert(self, postion, value):
    node = Node(value)
    curnode = self.head.next
    i = 2
    while i < postion:
      i += 1
      curnode = curnode.next
    node.next = curnode.next
    node.prev = curnode
    curnode.next.prev = node
    curnode.next = node
    self.length += 1
  # 刪除表頭節點
  def remove(self):
    if self.is_Empty():
      return False
    curnode = self.head.next
    self.head = self.head.next
    self.head.next = curnode.next
    self.length -= 1

  # 刪除指定節點
  def delete(self, value):
    if self.is_Empty():
      return False
    curnode = self.head.next
    while curnode.value != value:
      curnode = curnode.next
    curnode.prev.next = curnode.next
    curnode.next.prev = curnode.prev
    curnode.next = curnode
    self.length -= 1

# 測試
linkedlist = doubleLinked()
print(linkedlist.is_Empty())
linkedlist.append(1)
linkedlist.append(3)
linkedlist.append(5)
linkedlist.add(4)
linkedlist.add(2)
linkedlist.insert(3,10)
linkedlist.remove()
linkedlist.delete(3)
# 遍歷打印
i = 1
for node in linkedlist:
  print("第%d個鏈表節點的值: %d"%(i, node))
  i += 1

運行結果：

True
第1個鏈表節點的值: 4
第2個鏈表節點的值: 10
第3個鏈表節點的值: 1
第4個鏈表節點的值: 5

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》

希望本文所述對大家Python程序設計有所幫助。