双向链表Python代码

双向链表（Doubly Linked List）是一种数据结构，其中每个节点都有两个指针，分别指向前一个节点和后一个节点。在Python中，我们可以使用类来实现双向链表。下面是一个简单的双向链表的实现示例：

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

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

    # 插入节点到链表头部
    def insert_at_start(self, data):
        new_node = Node(data)
        if self.head is not None:
            new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

    # 在链表尾部插入节点
    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is not None:
            cur_node = self.head
            while cur_node.next:
                cur_node = cur_node.next
            cur_node.next = new_node
            new_node.prev = cur_node
        else:
            self.head = new_node

    # 删除指定节点
    def delete_node(self, key):
        cur_node = self.head
        if cur_node and cur_node.data == key:
            self.head = cur_node.next
            if self.head:
                self.head.prev = None
            return

        prev_node = None
        while cur_node and cur_node.data != key:
            prev_node = cur_node
            cur_node = cur_node.next

        if cur_node is None:
            return

        prev_node.next = cur_node.next
        if cur_node.next:
            cur_node.next.prev = prev_node

    # 遍历并打印链表
    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data, end=" <-> ")
            cur_node = cur_node.next
        print("None")

# 使用示例
dll = DoublyLinkedList()
dll.insert_at_start(3)
dll.insert_at_start(1)
dll.insert_at_end(4)
dll.print_list()  # 输出: 1 <-> 3 <-> 4 <-> None
dll.delete_node(3)
dll.print_list()  # 输出: 1 <-> 4 <-> None