雙向循環連結清單是在雙向連結清單的基礎上發展的，雙向連結清單的最後一個節點指向起始節點，起始節點的上一個節點指向最後一個節點，就得到雙向循環連結清單。
雙向循環連結清單比雙向連結清單具有更多的優勢，節點的增加和删除有很多優化的地方，從起點開始不必循環完整個連結清單就可以增加或删除節點。
首先定義雙向連結清單的基本類和節點的基本類：
class Node:
def __init__(self, item):
self.item = item # 該節點值
self.next = None # 連接配接一下一個節點
self.prev = None # 上一個節點值
class DoubleCircularLinkedList:
"""雙向循環清單類"""
def __init__(self):
self._head = None
下面我們添加基本屬性方法的邏輯，注意判斷是否為最後一個節點的方式是：最後一個節點的下一個節點是否指向頭部指向的節點。
class Node:
def __init__(self, item):
self.item = item # 該節點值
self.next = None # 連接配接一下一個節點
self.prev = None # 上一個節點值
class DoubleCircularLinkedList:
"""雙向循環清單類"""
def __init__(self):
self._head = None
@property
def is_empty(self):
"""
判斷連結清單是否為空
:return:
"""
return not self._head
@property
def length(self):
"""
連結清單長度
:return:
"""
if self.is_empty:
return 0
else:
cur = self._head.next
n = 1
while cur != self._head:
cur = cur.next
n += 1
return n
@property
def ergodic(self):
"""
周遊連結清單
:return:
"""
if self.is_empty:
raise ValueError("ERROR NULL")
else:
cur = self._head.next
print(self._head.item)
while cur != self._head:
print(cur.item)
cur = cur.next
連結清單類的操作有幾個核心的地方，第一個是判斷是否為最後一個節點，通過連結清單的相關特性，如單向連結清單最後一個節點的next屬性為None、單向循環連結清單的最後一個節點的next屬性等于頭部節點；第二個是使用遊标來替代節點指向，這個在操作節點的時候需要有時還需要兩個遊标，但是對于雙向節點而言隻需要一個遊标，通過目前節點的屬性可以找到上下節點。
繼續給對象添加方法：頭部插入節點、尾部添加節點、任意位置插入節點。
class Node:
def __init__(self, item):
self.item = item # 該節點值
self.next = None # 連接配接一下一個節點
self.prev = None # 上一個節點值
class DoubleCircularLinkedList:
"""雙向循環清單類"""
def __init__(self):
self._head = None
@property
def is_empty(self):
"""
判斷連結清單是否為空
:return:
"""
return not self._head
@property
def length(self):
"""
連結清單長度
:return:
"""
if self.is_empty:
return 0
else:
cur = self._head.next
n = 1
while cur != self._head:
cur = cur.next
n += 1
return n
@property
def ergodic(self):
"""
周遊連結清單
:return:
"""
if self.is_empty:
raise ValueError("ERROR NULL")
else:
cur = self._head.next
print(self._head.item)
while cur != self._head:
print(cur.item)
cur = cur.next
def add(self, item):
"""
頭部添加節點
:return:
"""
node = Node(item)
if self.is_empty:
node.next = node
node.prev = node
self._head = node
else:
node.next = self._head
node.prev = self._head.prev
self._head.prev.next = node
self._head.prev = node
self._head = node
def append(self, item):
"""
尾部添加節點
:param item:
:return:
"""
if self.is_empty:
self.add(item)
else:
node = Node(item)
cur = self._head.next
while cur.next != self._head:
cur = cur.next
cur.next = node
node.prev = cur
node.next = self._head
self._head.prev = node
def insert(self, index, item):
"""
任意位置插入節點
:param item:
:return:
"""
if index == 0:
self.add(item)
elif index+1 >= self.length:
self.append(item)
else:
cur = self._head.next
n = 1
while cur.next != self._head:
if n == index:
break
cur = cur.next
n += 1
node = Node(item)
node.prev = cur.prev
cur.prev.next = node
node.next = cur
cur.prev = node
接着實作判斷節點是否存在以及删除指定節點。
class Node:
def __init__(self, item):
self.item = item # 該節點值
self.next = None # 連接配接一下一個節點
self.prev = None # 上一個節點值
class DoubleCircularLinkedList:
"""雙向循環清單類"""
def __init__(self):
self._head = None
@property
def is_empty(self):
"""
判斷連結清單是否為空
:return:
"""
return not self._head
@property
def length(self):
"""
連結清單長度
:return:
"""
if self.is_empty:
return 0
else:
cur = self._head.next
n = 1
while cur != self._head:
cur = cur.next
n += 1
return n
@property
def ergodic(self):
"""
周遊連結清單
:return:
"""
if self.is_empty:
raise ValueError("ERROR NULL")
else:
cur = self._head.next
print(self._head.item)
while cur != self._head:
print(cur.item)
cur = cur.next
def add(self, item):
"""
頭部添加節點
:return:
"""
node = Node(item)
if self.is_empty:
node.next = node
node.prev = node
self._head = node
else:
node.next = self._head
node.prev = self._head.prev
self._head.prev.next = node
self._head.prev = node
self._head = node
def append(self, item):
"""
尾部添加節點
:param item:
:return:
"""
if self.is_empty:
self.add(item)
else:
node = Node(item)
cur = self._head.next
while cur.next != self._head:
cur = cur.next
cur.next = node
node.prev = cur
node.next = self._head
self._head.prev = node
def insert(self, index, item):
"""
任意位置插入節點
:param item:
:return:
"""
if index == 0:
self.add(item)
elif index+1 >= self.length:
self.append(item)
else:
cur = self._head.next
n = 1
while cur.next != self._head:
if n == index:
break
cur = cur.next
n += 1
node = Node(item)
node.prev = cur.prev
cur.prev.next = node
node.next = cur
cur.prev = node
def search(self, item):
"""
查找節點是否存在
:return:
"""
if self.is_empty:
return False
else:
cur = self._head.next
if self._head.item == item:
return True
else:
while cur != self._head:
if cur.item == item:
return True
else:
cur = cur.next
return False
def delete(self, item):
"""
删除指定值的節點
:param item:
:return:
"""
if self.is_empty:
raise ValueError("ERROR NULL")
else:
if self._head.item == item:
if self.length == 1:
self._head = Node
else:
self._head.prev.next = self._head.next
self._head.next.prev = self._head.prev
self._head = self._head.next
cur = self._head.next
while cur != self._head:
if cur.item == item:
cur.prev.next = cur.next
cur.next.prev = cur.prev
cur = cur.next
隻以基本的思路實作基本的方法，對于雙向循環連結清單而言還有很多可以優化的地方，正向周遊和逆向周遊獲得結果的時間是不一樣的。
![TestLink導出用例轉換工具(XML2Excel)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)