Python雙鏈表原理與實現(xiàn)方法詳解

更新時間：2020年02月22日 10:05:09 作者：授我以驢

這篇文章主要介紹了Python雙鏈表原理與實現(xiàn)方法,結(jié)合實例形式詳細(xì)分析了Python雙鏈表的概念、原理、用法及相關(guān)操作注意事項,需要的朋友可以參考下

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

Python實現(xiàn)雙鏈表

文章目錄

Python實現(xiàn)雙鏈表
- 單鏈表與雙鏈表比較
- 雙鏈表的實現(xiàn)

單鏈表與雙鏈表比較

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

雙鏈表的實現(xiàn)

定義鏈表節(jié)點

class Node(object):
  def __init__(self, value=None, prev=None, next=None):
    self.value = value	# 節(jié)點數(shù)據(jù)域
    self.prev = prev	# 節(jié)點前驅(qū)指針
    self.next = next	# 節(jié)點后繼指針

初始化雙鏈表

在雙鏈表類的構(gòu)造方法中定義頭指針以及鏈表長度屬性

class doubleLinked(object):

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

判斷鏈表是否為空

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

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

雙鏈表尾部添加元素

根據(jù)傳入的value值創(chuàng)建node節(jié)點對象
判斷是否為空，若為空則插入節(jié)點的前驅(qū)節(jié)點為head頭指針節(jié)點,head頭指針指向node
如果鏈表非空：
- 通過while循環(huán)判斷當(dāng)前節(jié)點的后繼節(jié)點是否為None，找到尾節(jié)點
- 找到尾節(jié)點后，將尾節(jié)點指向待添加節(jié)點，待添加節(jié)點前驅(qū)節(jié)點域指向原偽節(jié)點
- 長度+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

雙鏈表頭部添加節(jié)點：

調(diào)用類方法is_Empty()判斷是否為空，若為空則直接調(diào)用append()方法
當(dāng)鏈表非空時
- 首先創(chuàng)建待添加節(jié)點對象node
- 設(shè)置中間變量存放原頭指針指向的節(jié)點
- 將頭指針重新指向待添加節(jié)點
- 新添加節(jié)點后驅(qū)指針域指向中間變量(即原第一個節(jié)點)
- 中間變量前驅(qū)指針域指向新添加節(jié)點
- 鏈表長度+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
鏈表不為空時：
- 將頭指針指向的節(jié)點存放到中間變量curnode
- 將頭指針指向的節(jié)點指向頭指針(也就是第一個節(jié)點現(xiàn)在變成了頭指針)
- 新頭指針指向中間變量的后驅(qū)節(jié)點
- 鏈表長度-1

# 刪除表頭節(jié)點
  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

雙鏈表按位置插入

接收兩個位置參數(shù)，postion和value
創(chuàng)建待插入節(jié)點對象
變量curnode存放當(dāng)前節(jié)點，變量i初始值為2(位置參數(shù)<2時，默認(rèn)插入到第二個位置，>2時，通過while循環(huán)找到指定位置節(jié)點再進(jìn)行插入)
找到指定位置后，待插入節(jié)點的后驅(qū)指針指向當(dāng)前節(jié)點curnode的后繼節(jié)點，待插入節(jié)點的前驅(qū)節(jié)點為當(dāng)前節(jié)點。
當(dāng)前節(jié)點的原后驅(qū)節(jié)點的前驅(qū)指針域指向待插入節(jié)點，當(dāng)前節(jié)點curnode的后驅(qū)節(jié)點變更為插入節(jié)點
鏈表長度+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

雙鏈表刪除指定節(jié)點

依舊需要判斷是否為空，為空時返回False
鏈表不為空時：
- 設(shè)置中間變量curnode存放當(dāng)前節(jié)點
- while循環(huán)找到相匹配的值的節(jié)點
- 找到相應(yīng)節(jié)點后，應(yīng)刪除節(jié)點的前驅(qū)節(jié)點的后繼節(jié)點更改為應(yīng)刪除節(jié)點的后繼節(jié)點；應(yīng)刪除節(jié)點的后繼節(jié)點的前驅(qū)更改為應(yīng)刪除節(jié)點的前驅(qū)；
- 應(yīng)刪除節(jié)點后繼指針指向自己
- 鏈表長度-1

# 刪除指定節(jié)點
  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

  # 對鏈表進(jìn)行可迭代操作
  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
  # 刪除表頭節(jié)點
  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

  # 刪除指定節(jié)點
  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個鏈表節(jié)點的值: %d"%(i, node))
  i += 1

運(yùn)行結(jié)果：