Python实现双向链表：从基础到应用
一、引言
双向链表是一种比单向链表更复杂的数据结构，每个节点除了包含数据和指向下一个节点的指针外，还包含一个指向前一个节点的指针。这种结构使得我们可以从链表的任何节点开始，向前或向后遍历链表。
目录
一、引言
二、节点定义
三、链表实现
四、链表操作
五、应用示例
下面是一个使用双向链表类的示例：
输出结果为：
总结
二、节点定义
- 首先，我们需要定义一个双向链表的节点类（Node），它包含数据成员、指向前一个节点的指针和指向下一个节点的指针。
class Node: def __init__(self, data=None): self.data = data self.prev = None self.next = None三、链表实现
- 接下来，我们定义一个双向链表类（DoublyLinkedList），它包含头节点、尾节点和一系列操作链表的方法。
class DoublyLinkedList: 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 else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node def prepend(self, value): new_node = Node(value) if not self.head: self.head = new_node self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node def delete(self, value): current = self.head while current: if current.data == 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 = None elif current == self.tail: self.tail = current.prev self.tail.next = None else: current.prev.next = current.next current.next.prev = current.prev return True current = current.next return False def print_list(self): current = self.head while current: print(current.data, end=" ") current = current.next print()四、链表操作
- 在双向链表类中，我们实现了几个基本操作：
append（在尾部添加新节点）、prepend（在头部添加新节点）、delete（删除指定值的节点）和print_list（打印链表中的所有元素）。
五、应用示例
-
下面是一个使用双向链表类的示例：
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(3)
doubly_linked_list.append(2)
doubly_linked_list.prepend(1)
doubly_linked_list.prepend(0) print("链表中的元素为：", end=" ")
doubly_linked_list.print_list() doubly_linked_list.delete(2) print("删除元素2后的链表为：", end=" ")
doubly_linked_list.print_list()-
输出结果为：
链表中的元素为： 0 1 3 2
删除元素2后的链表为： 0 1 3总结
双向链表是一种功能强大的数据结构，它允许我们在两个方向上遍历链表，提供了更多的操作灵活性。在实际应用中，双向链表常用于实现双向队列、双向栈等数据结构，以及需要高效插入、删除和遍历操作的场景。