怎么用Python实现双向链表

双向链表（Doubly Linked List）是一种常见的数据结构，它允许在链表中进行双向遍历。与单向链表不同，双向链表的每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针。这使得在双向链表中插入、删除和遍历操作更加灵活和高效。

本文将介绍如何使用Python实现一个简单的双向链表，并实现一些基本的操作，如插入、删除和遍历。

1. 双向链表的节点结构

首先，我们需要定义一个节点类（Node），它包含三个属性： - data：存储节点的数据。 - prev：指向前一个节点的指针。 - next：指向下一个节点的指针。

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

2. 双向链表的实现

接下来，我们定义一个双向链表类（DoublyLinkedList），它包含以下方法： - __init__：初始化链表。 - append：在链表末尾添加节点。 - prepend：在链表头部添加节点。 - insert_after：在指定节点后插入新节点。 - delete：删除指定节点。 - display：遍历并打印链表中的所有节点。

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            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 not self.head:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def insert_after(self, prev_node, data):
        if not prev_node:
            print("Previous node cannot be None")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        if prev_node.next:
            prev_node.next.prev = new_node
        prev_node.next = new_node
        new_node.prev = prev_node

    def delete(self, node):
        if not node:
            return
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

3. 使用双向链表

现在，我们可以使用上述定义的DoublyLinkedList类来创建一个双向链表，并进行一些操作。

# 创建一个双向链表
dll = DoublyLinkedList()

# 在链表末尾添加节点
dll.append(10)
dll.append(20)
dll.append(30)

# 在链表头部添加节点
dll.prepend(5)

# 在指定节点后插入新节点
second_node = dll.head.next
dll.insert_after(second_node, 15)

# 删除指定节点
dll.delete(second_node)

# 遍历并打印链表中的所有节点
dll.display()

输出结果

5 <-> 10 <-> 15 <-> 30 <-> None

4. 总结

通过以上步骤，我们实现了一个简单的双向链表，并实现了基本的插入、删除和遍历操作。双向链表由于其双向遍历的特性，在某些场景下比单向链表更加高效和灵活。希望本文能帮助你理解并掌握如何在Python中实现双向链表。