掌握Python中的双向链表（从零开始构建你的第一个双向链表）

第一步：定义节点类

我们首先需要创建一个表示链表节点的类。这个类将包含数据、前驱和后继指针。

class Node:    def __init__(self, data):        self.data = data      # 存储数据        self.prev = None      # 指向前一个节点        self.next = None      # 指向后一个节点  

第二步：定义双向链表类

接下来，我们创建一个 DoublyLinkedList 类，用于管理整个链表。我们将实现以下基本功能：

• 在链表头部插入节点
• 在链表尾部插入节点
• 删除指定值的节点
• 正向和反向遍历链表

class DoublyLinkedList:    def __init__(self):        self.head = None   # 链表头        self.tail = None   # 链表尾    def append(self, data):        """在链表尾部添加新节点"""        new_node = Node(data)        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, data):        """在链表头部添加新节点"""        new_node = Node(data)        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, data):        """删除第一个匹配data值的节点"""        current = self.head        while current:            if current.data == data:                if current.prev:                    current.prev.next = current.next                else:                    self.head = current.next                if current.next:                    current.next.prev = current.prev                else:                    self.tail = current.prev                return  # 删除后直接返回            current = current.next    def display_forward(self):        """正向打印链表"""        elements = []        current = self.head        while current:            elements.append(current.data)            current = current.next        return elements    def display_backward(self):        """反向打印链表"""        elements = []        current = self.tail        while current:            elements.append(current.data)            current = current.prev        return elements  

第三步：测试你的双向链表

现在，让我们用一些简单的代码来测试我们刚刚实现的双向链表：

# 创建双向链表实例dll = DoublyLinkedList()# 添加元素dll.append(1)dll.append(2)dll.prepend(0)print("正向遍历:", dll.display_forward())   # 输出: [0, 1, 2]print("反向遍历:", dll.display_backward()) # 输出: [2, 1, 0]# 删除元素dll.delete(1)print("删除1后正向遍历:", dll.display_forward())  # 输出: [0, 2]  

为什么学习双向链表很重要？

掌握双向链表实现不仅有助于理解更复杂的数据结构（如LRU缓存、跳表等），还能提升你在算法面试中的表现。此外，在某些场景下，双向链表比数组或其他结构更节省内存或提高效率。

总结

通过本教程，你已经学会了如何在 Python 中从零开始构建一个双向链表。我们涵盖了节点定义、链表操作（插入、删除、遍历）以及简单的测试方法。希望这份数据结构教程能帮助你打下坚实的基础。继续练习不同的链表操作，你会越来越熟练！

提示：你可以尝试扩展这个类，加入查找节点、获取长度、清空链表等功能，进一步巩固所学知识。