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

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

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

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

Python實(shí)現(xiàn)雙鏈表

文章目錄

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

單鏈表與雙鏈表比較

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

雙鏈表的實(shí)現(xiàn)

定義鏈表節(jié)點(diǎn)

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

初始化雙鏈表

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

class doubleLinked(object):

  def __init__(self):
    self.head = Node()	# 頭指針節(jié)點(diǎn)，用于確定鏈表第一個(gè)節(jié)點(diǎn)，不計(jì)入鏈表實(shí)際長(zhǎng)度
    self.length = 0

判斷鏈表是否為空

通過(guò)實(shí)例屬性self.length是否為0判斷鏈表是否為空

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

雙鏈表尾部添加元素

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

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

雙鏈表表頭刪除

老樣子，依舊要先判斷原鏈表是否為空，為空的時(shí)候返回False
鏈表不為空時(shí)：
- 將頭指針指向的節(jié)點(diǎn)存放到中間變量curnode
- 將頭指針指向的節(jié)點(diǎn)指向頭指針(也就是第一個(gè)節(jié)點(diǎn)現(xiàn)在變成了頭指針)
- 新頭指針指向中間變量的后驅(qū)節(jié)點(diǎn)
- 鏈表長(zhǎng)度-1

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

雙鏈表按位置插入

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

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

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

  # 對(duì)鏈表進(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é)點(diǎn)
  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é)點(diǎn)
  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

# 測(cè)試
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個(gè)鏈表節(jié)點(diǎn)的值: %d"%(i, node))
  i += 1

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