写一个Python双链表,每段代码加上注释
时间: 2023-11-21 14:55:53 浏览: 100
双向链表是一种线性数据结构,每个节点有两个指针,一个指向前一个节点,一个指向后一个节点。下面是一个Python实现双向链表的示例代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def prepend(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def insert_after_node(self, prev_node, data):
if not prev_node:
return
new_node = Node(data)
new_node.next = prev_node.next
prev_node.next = new_node
new_node.prev = prev_node
if new_node.next:
new_node.next.prev = new_node
def delete_node(self, key):
current = self.head
while current:
if current.data == key and current == self.head:
if not current.next:
current = None
self.head = None
return
else:
nxt = current.next
current.next = None
nxt.prev = None
current = None
self.head = nxt
return
elif current.data == key:
if current.next:
nxt = current.next
prev = current.prev
prev.next = nxt
nxt.prev = prev
current.next = None
current.prev = None
current = None
return
else:
prev = current.prev
prev.next = None
current.prev = None
current = None
return
current = current.next
def print_list(self):
current = self.head
while current:
print(current.data)
current = current.next
```
上述代码定义了两个类:`Node` 和 `DoublyLinkedList`。`Node` 类表示链表中的一个节点,包含三个属性:`data`,`prev`,`next`。`DoublyLinkedList` 类表示整个双向链表,包含一个属性 `head`,表示链表的头节点。
`DoublyLinkedList` 类中有几个方法:
- `append(data)` 方法:在链表末尾插入一个新节点。
- `prepend(data)` 方法:在链表头部插入一个新节点。
- `insert_after_node(prev_node, data)` 方法:在指定节点 `prev_node` 后面插入一个新节点。
- `delete_node(key)` 方法:删除指定数据 `key` 的节点。
- `print_list()` 方法:打印整个链表。
以上就是一个简单的Python双向链表实现。
阅读全文