定义
双向循环链表是在双向链表的基础上发展的，双向链表的最后一个节点指向起始节点，起始节点的上一个节点指向最后一个节点，就得到双向循环链表。
优势
向循环链表比双向链表具有更多的优势，节点的增加和删除有很多优化的地方，从起点开始不必循环完整个链表就可以增加或删除节点。
python实现双向循环链表
头部插入节点
代码实现
def add(self, value):
"""
头插法
"""
node = Node(value)
if self.is_empty():
node.next = node
node.prev = node
self._head = node
else:
# 新节点的next指向head
node.next = self._head
# 新节点的prev指向head的prev
node.prev = self._head.prev
# head节点的prev的next的节点指向node
self._head.prev.next = node
# 头部节点的prev指向node
self._head.prev = node
# 头部指针指向node
self._head = node
尾部插入节点
代码实现
def append(self, value):
"""
尾插法
"""
if self.is_empty():
self.add(value)
else:
node = Node(value)
# node的next指向head
node.next = self._head
# node的prev指向head的prev
node.prev = self._head.prev
# head的prev节点的next指向node
self._head.prev.next = node
# head的prev指向node
self._head.prev = node
指定位置插入节点
代码实现
def insert(self, value, index):
"""
指定位置插入节点
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
# 移动到指定位置的前一个节点
while count < (index - 1):
count += 1
cur = cur.next
# 新节点pre指向上一个节点
node.prev = cur
# 新节点的next指向下一个节点
node.next = cur.next
# 下一个节点的prev指向node
cur.next.prev = node
# 上一个节点next指向新节点
cur.next = node
删除节点
代码实现
def remove(self, value):
"""
删除节点
"""
if self.is_empty():
return
else:
cur = self._head
# 如果第一个节点就是要删除的节点
if cur.item == value:
# 如果只有一个元素
if self.length() == 1:
self._head = None
else:
# 将头结点的下一个节点的prev指向头结点的prev
cur.next.prev = cur.prev
# 头结点的prev的next指向头结点的下一个节点
cur.prev.next = cur.next
# 头指针指向头结点的下一个节点
self._head = cur.next
else:
# 后移一个节点
cur = cur.next
# 循环cur 找到删除的元素 找不到break
while cur is not self._head:
if cur.item == value:
# cur的next的prev指向cur的prev
cur.next.prev = cur.prev
# cur的prev的next指向cur的next
cur.prev.next = cur.next
cur = cur.next
完整代码
class Node(object):
"""
双向循环链表节点实现
"""
def __init__(self, item):
self.prev = None
self.item = item
self.next = None
class DoubleCircleLinkList(object):
"""
双向循环链表实现
"""
def __init__(self):
self._head = None
def is_empty(self):
"""
判断双向循环链表是否为空
"""
return self._head is None
def length(self):
"""
双向循环链表长度
"""
if self.is_empty():
return 0
else:
# cur用来移动遍历节点
cur = self._head
# count为计数
count = 1
while cur.next is not self._head:
count += 1
cur = cur.next
return count
def traverse(self):
"""
遍历双向循环链表
:return:
"""
if self.is_empty():
return
else:
cur = self._head.next
# print(cur.next)
# print(self._head)
while cur != self._head:
print(cur.item, end=" ")
cur = cur.next
print("")
def add(self, value):
"""
头插法
"""
node = Node(value)
if self.is_empty():
node.next = node
node.prev = node
self._head = node
else:
# 新节点的next指向head
node.next = self._head
# 新节点的prev指向head的prev
node.prev = self._head.prev
# head节点的prev的next的节点指向node
self._head.prev.next = node
# 头部节点的prev指向node
self._head.prev = node
# 头部指针指向node
self._head = node
def append(self, value):
"""
尾插法
"""
if self.is_empty():
self.add(value)
else:
node = Node(value)
# node的next指向head
node.next = self._head
# node的prev指向head的prev
node.prev = self._head.prev
# head的prev节点的next指向node
self._head.prev.next = node
# head的prev指向node
self._head.prev = node
def insert(self, value, index):
"""
指定位置插入节点
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
# 移动到指定位置的前一个节点
while count < (index - 1):
count += 1
cur = cur.next
# 新节点pre指向上一个节点
node.prev = cur
# 新节点的next指向下一个节点
node.next = cur.next
# 下一个节点的prev指向node
cur.next.prev = node
# 上一个节点next指向新节点
cur.next = node
def remove(self, value):
"""
删除节点
"""
if self.is_empty():
return
else:
cur = self._head
# 如果第一个节点就是要删除的节点
if cur.item == value:
# 如果只有一个元素
if self.length() == 1:
self._head = None
else:
# 将头结点的下一个节点的prev指向头结点的prev
cur.next.prev = cur.prev
# 头结点的prev的next指向头结点的下一个节点
cur.prev.next = cur.next
# 头指针指向头结点的下一个节点
self._head = cur.next
else:
# 后移一个节点
cur = cur.next
# 循环cur 找到删除的元素 找不到break
while cur is not self._head:
if cur.item == value:
# cur的next的prev指向cur的prev
cur.next.prev = cur.prev
# cur的prev的next指向cur的next
cur.prev.next = cur.next
cur = cur.next
def search(self, item):
"""
查找元素是否存在
"""
if self.is_empty():
return False
else:
cur = self._head
while cur.next is not self._head:
if cur.item == item:
return True
cur = cur.next
if cur.item == item:
return True
return False
if __name__ == '__main__':
double_circle_link_list = DoubleCircleLinkList()
print("当前链表是否为空：", double_circle_link_list.is_empty())
print("当前链表长度为：", double_circle_link_list.length())
double_circle_link_list.append(99)
print("当前链表是否为空：", double_circle_link_list.is_empty())
print("当前链表长度为：", double_circle_link_list.length())
double_circle_link_list.append(23)
double_circle_link_list.append(89)
double_circle_link_list.append("python")
double_circle_link_list.append(12.66)
double_circle_link_list.add(27)
double_circle_link_list.insert(4, 0)
double_circle_link_list.remove(27)
double_circle_link_list.traverse()
print(double_circle_link_list.search(23))
结果
当前链表是否为空： True
当前链表长度为： 0
当前链表是否为空： False
当前链表长度为： 1
99 23 89 python 12.66
True
