双向链表,创建一个空头结点,向这个头结点管理的链表中插入数据,打印链表中的数据,清空链表,保留头节点,删除一个节点
时间: 2024-10-25 12:12:21 浏览: 27
循环链表和双向链表
双向链表是一种特殊的线性数据结构,每个节点包含两个指针,分别指向前一个节点和后一个节点。这使得我们在添加或删除节点时,不需要像单链表那样只能从头或尾操作。
首先,我们创建一个空的双向链表,可以这样表示:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.prev = None
self.next = None
head = Node() # 创建一个空头结点
```
要向链表中插入数据,我们可以定义一个函数`insert`:
```python
def insert(data):
new_node = Node(data)
if not head.next:
head.next = new_node
new_node.prev = head
else:
last = head.next
last.next = new_node
new_node.prev = last
new_node.next = None
```
要打印链表中的数据,可以遍历链表并打印每个节点的数据:
```python
def print_list(head):
current = head
while current is not None:
print(current.data)
current = current.next
```
对于清空链表并保留头节点,可以在遍历过程中逐个断开链接:
```python
def clear_list(head):
current = head.next
while current is not None:
temp = current
current = current.next
temp.prev = None
temp.next = None
```
最后,删除特定节点需要找到该节点的前驱然后调整链接:
```python
def delete_node(key, head):
current = head
prev = None
while current is not None and current.data != key:
prev = current
current = current.next
if current is None:
return head
if prev is None: # 删除头结点
head = current.next
else:
prev.next = current.next
current.prev = None
return head
```
阅读全文