设计一个双向循环链表类,实现一个数据分别为0,1,2,3,4,5,6,7,8,9的双向循环链表,并删除其中数据为5和8的节点,分别在原来删除的位置插入数据为5.1和8.2的节点,并输出循环链表的双向遍历结果。用Python
时间: 2024-10-18 09:10:43 浏览: 12
python实现数据结构中双向循环链表操作的示例
首先,我们需要创建一个双向循环链表的节点类以及双向链表类,包括添加、删除和插入操作,以及遍历功能。下面是一个简单的实现:
```python
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
self.prev = None
class DoublyCircularLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
self.tail = new_node
new_node.next = new_node
new_node.prev = new_node
else:
new_node.next = self.head
new_node.prev = self.tail
self.head.prev = new_node
self.tail.next = new_node
self.tail = new_node
def delete(self, value):
current = self.head
while True:
if current.value == value:
if current == self.head and current == self.tail:
self.head = None
self.tail = None
elif current == self.head:
self.head = current.next
self.head.prev = self.tail
elif current == self.tail:
self.tail = current.prev
self.tail.next = self.head
else:
current.prev.next = current.next
current.next.prev = current.prev
break
current = current.next
if current == self.head:
break
def insert(self, old_value, new_value, position='end'):
current = self.head
index = 1
while current.value != old_value:
if position == 'start':
if current == self.tail:
return "Error: Insertion at the start is not possible since it's a circular list."
self.append(new_value)
break
current = current.next
index += 1
if position == 'end':
after_delete = current.prev
after_delete.next = new_node = Node(new_value)
new_node.prev = after_delete
new_node.next = current
current.prev = new_node
else:
index -= 1
after_delete = current if current.value == old_value else current.prev
new_node = Node(new_value)
new_node.next = current
new_node.prev = after_delete
after_delete.next = current.prev
current.prev = new_node
def traverse(self):
elements = []
current = self.head
while True:
elements.append(current.value)
current = current.next
if current == self.head:
break
return elements
# 使用这个类
dll = DoublyCircularLinkedList()
for i in range(10):
dll.append(i)
# 删除5和8
dll.delete(5)
dll.delete(8)
# 插入5.1和8.2
dll.insert(5, 5.1, position='start')
dll.insert(8, 8.2)
# 遍历并打印结果
print("Original list:", dll.traverse())
print("After operations:")
print(dll.traverse())
```
运行以上代码,你会得到原始链表和修改后的链表的遍历结果。
阅读全文