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

总结

        双向链表是一种功能强大的数据结构，它允许我们在两个方向上遍历链表，提供了更多的操作灵活性。在实际应用中，双向链表常用于实现双向队列、双向栈等数据结构，以及需要高效插入、删除和遍历操作的场景。