对于一个带头节点的循环双链表,编写两个函数,分别实现在链表尾部插入节点以及删除节点的算法。
时间: 2024-12-14 08:23:23 浏览: 12
对于一个带头节点的循环双链表,我们需要维护两个指针,一个是当前节点,另一个是前一个节点,以便在操作过程中能够有效地遍历列表。以下是插入和删除节点的基本步骤:
1. **在链表尾部插入节点**:
- 初始化新节点 `new_node` 并设置其值、前驱 (`prev`) 和后继 (`next`) 指向头节点。
- 如果链表为空或只有一个节点,那么 `new_node.next = new_node.prev = head`,使其形成环。
- 否则,找到最后一个节点:当当前节点 (`current`) 的 `next` 等于头节点时,说明已经到达尾部。此时,`new_node.next = current.next`,`current.next.prev = new_node`。
```python
def insert_at_tail(head, value):
if not head:
new_node = Node(value)
new_node.next = new_node.prev = head
else:
current = head
while current.next != head:
current = current.next
new_node = Node(value)
new_node.next = head
current.next.prev = new_node
```
2. **从链表尾部删除节点**:
- 遍历到最后一个节点,并判断是否需要删除(即不是第一个节点)。
- 如果最后一个节点是要删除的节点,则简单地更新前一个节点的 `next` 指针指向头节点。
- 否则,找到倒数第二个节点,将它的 `next` 设置为头节点,然后让头节点的 `prev` 指向删除的节点。
```python
def delete_from_tail(head):
if not head or not head.next:
return head
last = head
prev_last = None
current = head
# Find the second to last node
while current.next != head:
prev_last = current
current = current.next
# Delete the tail node
if prev_last:
prev_last.next = head
elif head.prev: # If it's a circular list with more than one node
head.prev.next = head
else: # Only one node in the list
head.prev = head.next = None
```
阅读全文