怎么在Python中實現雙向循環鏈表

怎么在Python中實現雙向循環鏈表？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

判斷空：is_empty()

如果頭指針head沒有指向則鏈表是空的 否則不是空的

在頭部添加元素: add(item)

1 新建一個節點 里面的值是item。

2 放入頭部：

2.1 如果鏈表是空的，node的next和prev都指向自己，然后head再指向node

在尾部添加元素: append(item)

1 創建一個新節點node 里面的值是item

2 放入尾部：

2.1 如果鏈表空，則執行頭部添加add就可以

2.2 鏈表非空：

2.2.1 node的next指向head

2.2.2 node的prev指向head的prev

2.2.3 head的prev元素的next指向node

2.2.4 head的prev指向改為node

2.2.5 head指向node  更換了頭部

指定位置添加元素： insert( pos , item )

1 新建一個節點node 里面的值是item

2 找到合適的位置插進去：

2.1 如果pos <= 0 還小，那就執行頭插方法 add()

2.2 如果pos >= 鏈表長度, 那就執行尾部插入 append()

2.3 如果pos位置在鏈表的中間：

2.3.1 定義一個臨時變量temp 按照傳入的pos找到要插入的位置的前一個元素

2.3.2 node的prev設為temp,node的next設為temp的next

2.3.3 temp的next指向的節點的prev改為node

2.3.4 temp的next改為node

得到鏈表長度： length()

1 我們設置一個臨時變量temp初始設為head ， 設置一個計數器count 初始為 0

2 令count自增1 然后temp改指向自己的下一個元素 一直到temp遇到None 為止，temp到了鏈表的最后一個元素

通過這樣的方式，統計出一共有多少個節點返回

遍歷鏈表數據： travelji()

1 設置一個臨時變量temp初始化設為head

2 temp 每次輸出自己指向元素的值，然后在指向自己的下一個元素，一直temp為None 說明到了列表的尾部

刪除鏈表元素： remove( item )

1 開啟temp臨時變量 初始化為head ，

2  temp不斷指向自己的下一個元素，每次指向一個元素都檢查當前值是不是item，如果找到item則刪除它返回True，如果沒找到就到尾部了就返回False

2.1 刪除過程：

2.1.1 temp的前一個元素的next改為temp的后一個元素

2.1.2 temp的后一個元素的prev改為前一個元素

查詢是否有元素：search()

設置一個臨時變量temp從head開始，不斷指向自己下一個，每次都檢查一下自己的值如果和item相同返回True結束

如果temp變成None 則到尾部了都沒找到 返回False

上代碼！

# -*- coding:utf-8 -*-
#!python3
#鏈表的節點
class Node(object):
 def __init__(self , item ):
  self.item = item #節點數值
  self.prev = None #用于指向前一個元素
  self.next = None #用于指向后一個元素
#雙向循環鏈表
class DoubleCircleLinkList(object):
 def __init__(self):
  self.__head = None #初始化的時候頭節點設為空、
 #判斷鏈表是否為空，head為None 的話則鏈表是空的
 def is_empty(self):
  return self.__head is None
 #頭部添加元素的方法
 def add(self,item):
  node = Node(item) #新建一個節點node 里面的值是item
  # 如果鏈表是空的，則node的next和prev都指向自己(因為是雙向循環)，head指向node
  if self.is_empty():
   self.__head = node
   node.next = node
   node.prev = node
  # 否則鏈表不空
  else:
   node.next = self.__head #node的next設為現在的head
   node.prev = self.__head.prev #node的prev 設為現在head的prev
   self.__head.prev.next = node #現在head的前一個元素的next設為node
   self.__head.prev = node #現在head的前驅 改為node
   self.__head = node #更改頭部指針
 #尾部添加元素方法
 def append(self , item):
  #如果當前鏈表是空的 那就調用頭部插入方法
  if self.is_empty():
   self.add(item)
  #否則鏈表不為空
  else :
   node = Node(item) #新建一個節點node
   #因為是雙向循環鏈表，所以head的prev其實就是鏈表的尾部
   node.next = self.__head #node的下一個設為頭
   node.prev = self.__head.prev #node的前驅設為現在頭部的前驅
   self.__head.prev.next = node #頭部前驅的后繼設為node
   self.__head.prev = node #頭部自己的前驅改為node
 #獲得鏈表長度 節點個數
 def length(self):
  #如果鏈表是空的 就返回0
  if self.is_empty():
   return 0
  #如果不是空的
  else:
   cur = self.__head #臨時變量cur表示當前位置 初始化設為頭head
   count = 1 #設一個計數器count，cur每指向一個節點，count就自增1 目前cur指向頭，所以count初始化為1
   #如果cur.next不是head，說明cur目前不是最后一個元素，那么count就1，再讓cur后移一位
   while cur.next is not self.__head:
    count += 1
    cur = cur.next
   #跳出循環說明所有元素都被累加了一次 返回count就是一共有多少個元素
   return count
 #遍歷鏈表的功能
 def travel(self):
  #如果當前自己是空的，那就不遍歷
  if self.is_empty():
   return
  #鏈表不空
  else :
   cur = self.__head #臨時變量cur表示當前位置，初始化為鏈表的頭部
   #只要cur的后繼不是頭說明cur不是最后一個節點，我們就輸出當前值，并讓cur后移一個節點
   while cur.next is not self.__head:
    print( cur.item,end=" " )
    cur = cur.next
   #當cur的后繼是head的時候跳出循環了，最后一個節點還沒有打印值 在這里打印出來
   print( cur.item )
 #置頂位置插入節點
 def insert(self, pos , item ):
  #如果位置<=0 則調用頭部插入方法
  if pos <= 0:
   self.add(item)
  #如果位置是最后一個或者更大 就調用尾部插入方法
  elif pos > self.length() - 1 :
   self.append(item)
  #否則插入位置就是鏈表中間
  else :
   index = 0 #設置計數器，用于標記我們后移了多少步
   cur = self.__head #cur標記當前所在位置
   #讓index每次自增1 ，cur后移，當index=pos-1的時候說明cur在要插入位置的前一個元素，這時候停下
   while index < pos - 1 :
    index += 1
    cur = cur.next
   #跳出循環，cur在要插入位置的前一個元素，將node插入到cur的后面
   node = Node(item) #新建一個節點
   node.next = cur.next #node的后繼設為cur的后繼
   node.prev = cur #node的前驅設為cur
   cur.next.prev = node #cur后繼的前驅改為node
   cur.next = node #cur后繼改為node
 #刪除節點操作
 def remove(self,item):
  #如果鏈表為空 直接不操作
  if self.is_empty():
   return
  #鏈表不為空
  else:
   cur = self.__head #臨時變量標記位置，從頭開始
   #如果頭結點就是 要刪除的元素
   if cur.item == item:
    #如果只有一個節點 鏈表就空了 head設為None
    if self.length() == 1:
     self.__head = None
    #如果多個元素
    else:
     self.__head = cur.next #頭指針指向cur的下一個
     cur.next.prev= cur.prev #cur后繼的前驅改為cur的前驅
     cur.prev.next = cur.next #cur前驅的后繼改為cur的后繼
   #否則 頭節點不是要刪除的節點 我們要向下遍歷
   else:
    cur = cur.next #把cur后移一個節點
    #循環讓cur后移一直到鏈表尾元素位置，期間如果找得到就刪除節點，找不到就跳出循環，
    while cur is not self.__head:
     #找到了元素cur就是要刪除的
     if cur.item == item:
      cur.prev.next = cur.next #cur的前驅的后繼改為cur的后繼
      cur.next.prev = cur.prev #cur的后繼的前驅改為cur的前驅
     cur = cur.next
 #搜索節點是否存在
 def search(self , item):
  #如果鏈表是空的一定不存在
  if self.is_empty():
   return False
  #否則鏈表不空
  else:
   cur = self.__head #設置臨時cur從頭開始
   # cur不斷后移，一直到尾節點為止
   while cur.next is not self.__head:
    #如果期間找到了就返回一個True 結束運行
    if cur.item == item:
     return True
    cur = cur.next
   # 從循環跳出來cur就指向了尾元素 看一下為元素是不是要找的 是就返回True
   if cur.item ==item:
    return True
   #所有元素都不是 就返回False 沒找到
   return False
if __name__ == "__main__":
 dlcl = DoubleCircleLinkList()
 print(dlcl.search(7))
 dlcl.travel()
 dlcl.remove(1)
 print(dlcl.length())
 print(dlcl.is_empty())
 dlcl.append(55)
 print(dlcl.search(55))
 dlcl.travel()
 dlcl.remove(55)
 dlcl.travel()
 print(dlcl.length())
 dlcl.add(3)
 print(dlcl.is_empty())
 dlcl.travel()
 dlcl.add(4)
 dlcl.add(5)
 dlcl.append(6)
 dlcl.insert(-10,1)
 dlcl.travel()
 print(dlcl.length())
 dlcl.remove(6)
 dlcl.travel()
 print(dlcl.search(7) )
 dlcl.append(55)
 dlcl.travel()

運行結果：

False
0
True
True
55
0
False
3
1 5 4 3 6
5
1 5 4 3
False
1 5 4 3 55

python可以做什么

Python是一種編程語言，內置了許多有效的工具，Python幾乎無所不能，該語言通俗易懂、容易入門、功能強大，在許多領域中都有廣泛的應用，例如最熱門的大數據分析，人工智能，Web開發等。

關于怎么在Python中實現雙向循環鏈表問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。