python实现数据结构的双链表

在Python中，我们可以手动创建一个简单的双链表数据结构，它包含两个节点，每个节点都有一个值、指向前一个节点的引用（称为prev）和指向后一个节点的引用（称为next）。以下是基本的实现：

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

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

    # 插入节点到链表头部
    def insert_at_beginning(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 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 delete(self, key):
        current = self.head
        while current:
            if current.data == key:
                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 True
            current = current.next
        return False

    # 遍历链表并打印节点值
    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# 示例
dll = DoublyLinkedList()
dll.insert_at_beginning(1)
dll.append(2)
dll.traverse()  # 输出: 1 <-> 2 <-> None