# 创建节点类
class Node():
# 定义构造方法
def __init__(self, item):
# item是存放数据区域
self.item = item
# prev是指向前一个结点的标识
self.prev =None
# next是指向后一个节点的标识
self.next =None
# 创建双向循环链表
class DoubcycLinkList():
# 定义构造方法
def __init__(self):
# head是链表的头结点
self.head =None
def is_empty(self):
"""判断链表是否为空"""
# 如果链表为空返回True, 否则返回False
return self.headis None
def length(self):
"""链表长度"""
# 判断链表是否为空，如果是返回0
if self.is_empty():
return 0
# 创建指针指向头节点
cur =self.head
# 创建计数器，默认是1
count =1
# 循环遍历链表，循环条件是指针的next是否指向头节点
while cur.next !=self.head:
# 计数器加1
count +=1
# 将指针后移
cur = cur.next
# 返回计数器的值
return count
def travel(self):
"""遍历整个链表"""
if self.is_empty():
return
cur =self.head
while cur.next !=self.head:
# 输出指针对应元素的值
print(cur.item, end=" ")
cur = cur.next
# 输出最后一个节点的值
print(cur.item)
def add(self, item):
"""在链表头部添加元素"""
# 实例化一个新节点
node = Node(item)
if self.is_empty():
# 将新节点赋值给头节点
self.head = node
# 新节点的next指向它自己
node.next = node
return
cur =self.head
# 新节点的next指向头节点
node.next =self.head
# 新节点的prev指向None
node.prev =None
# 如果链表有多个节点
if cur.next !=self.head:
while cur.next !=self.head:
cur = cur.next
cur.next = node
self.head = node
# 链表只有一个节点
else:
cur.next = node
cur.prev = node
self.head = node
def append(self, item):
"""在链表尾部添加元素"""
node = Node(item)
if self.is_empty():
# 将新节点赋值给头节点
self.head = node
# 将新节点的next指向node
node.next = node
# 将新节点的prev指向None
node.prev =None
return
cur =self.head
# 将新节点的next指向头节点
node.next =self.head
while cur.next !=self.head:
cur = cur.next
node.prev = cur
cur.next = node
def insert(self, pos, item):
"""在链表指定位置插入元素"""
# 如果在链表头部添加元素，使用头插法
if pos <=0:
self.add(item)
# 如果在链表尾部添加元素，使用尾插法
elif pos >self.length():
self.append(item)
else:
cur =self.head
count =0
node = Node(item)
while count < pos-1:
count +=1
cur = cur.next
node.next = cur.next
node.prev = cur
cur.next = node
cur.next.prev = node
def remove(self, item):
"""删除链表元素"""
# 如果链表为空，直接返回
if self.is_empty():
return
cur =self.head
# 如果第一个元素就是要删除的元素
if cur.item == item:
# 如果链表有多个节点
if cur.next !=self.head:
while cur.next !=self.head:
cur = cur.next
cur.next =self.head.next
self.head.next.prev =None
self.head =self.head.next
# 链表只有一个节点
else:
self.head =None
# 第一个元素不是要删除的元素
else:
while cur.next !=self.head:
if cur.item == item:
cur.next.prev = cur.prev
cur.prev.next = cur.next
return
cur = cur.next
if cur.item == item:
cur.prev.next = cur.next
else:
return
def search(self, item):
"""查找链表元素"""
if self.is_empty():
return False
cur =self.head
while cur.next !=self.head:
if cur.item == item:
return True
cur = cur.next
if cur.item == item:
return True
return False
if __name__ =='__main__':
d = DoubcycLinkList()
print(d.length())
print(d.remove(10))
print(d.search(10))
print("-"*50)
d.add(20)
d.add(10)
d.append(30)
d.append(40)
d.insert(0, 50)
d.insert(100, 60)
d.remove(50)
d.remove(60)
d.remove(20)
print(d.remove(60))
print(d.search(60))
print(d.length())
d.travel()
运行结果：
