python 双向循环链表实现_python实现双向循环链表基本结构及其基本方法
雙向循環鏈表是在雙向鏈表的基礎上發展的，雙向鏈表的最后一個節點指向起始節點，起始節點的上一個節點指向最后一個節點，就得到雙向循環鏈表。
雙向循環鏈表比雙向鏈表具有更多的優勢，節點的增加和刪除有很多優化的地方，從起點開始不必循環完整個鏈表就可以增加或刪除節點。
首先定義雙向鏈表的基本類和節點的基本類：
image
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
只以基本的思路實現基本的方法，對于雙向循環鏈表而言還有很多可以優化的地方，正向遍歷和逆向遍歷獲得結果的時間是不一樣的。
image
總結
以上是生活随笔為你收集整理的python 双向循环链表实现_python实现双向循环链表基本结构及其基本方法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： FastDFS的介绍
- 下一篇： 动易php,动易数据转成dedecms的