实现三个函数,要实现能够对双向循环列表的插入,删除,以及返回指定第i个元素的地址。
时间: 2024-09-20 15:15:15 浏览: 13
在Python中,我们可以创建一个双向循环链表的节点类,然后提供相应的插入、删除和获取元素功能。这里是一个简化的示例:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
# 插入元素
def insert_at(self, index, data):
if index < 0 or index > self.size:
return "Index out of range"
new_node = Node(data)
if self.size == 0: # 链表为空
self.head = new_node
self.tail = new_node
elif index == 0: # 插入到头部
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
else: # 插入到中间或尾部
current = self.head
for _ in range(index - 1):
current = current.next
new_node.next = current.next
new_node.prev = current
current.next.prev = new_node
current.next = new_node
self.size += 1
return f"Inserted at index {index}: {data}"
# 删除元素
def delete_at(self, index):
if index < 0 or index >= self.size:
return "Index out of range"
if self.size == 1: # 只有一个元素
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = None
self.tail.next = None
elif index == 0: # 删除头部
temp = self.head.next
self.head.next = None
self.head.prev = None
self.head = temp
else: # 删除中间或尾部
current = self.head
for _ in range(index - 1):
current = current.next
temp = current.next
current.next = temp.next
if temp.next is not None:
temp.next.prev = current
else:
self.tail = current
self.size -= 1
return f"Deleted at index {index}"
# 获取指定位置的元素
def get_at(self, index):
if index < 0 or index >= self.size:
return "Index out of range"
current = self.head
for _ in range(index):
current = current.next
return current.data
# 示例使用
dll = DoublyLinkedList()
dll.insert_at(0, 'A')
dll.insert_at(1, 'B')
dll.insert_at(2, 'C')
print(dll.get_at(1)) # 输出:B
```
在这个例子中,`insert_at()`、`delete_at()` 和 `get_at()` 分别实现了双向循环链表的插入、删除和获取操作。请注意,这个实现假设了索引从0开始计数。