python实现双向链表的定位插入和定位删除

双向链表是一种链表结构，每个节点同时存储指向前一个节点和后一个节点的指针。在Python中，可以使用类来表示双向链表节点，其中包含元素值和前后指针。下面是双向链表的定位插入和定位删除的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_position(self, data, position):
        new_node = Node(data)
        if position < 1:
            print("Invalid position")
            return
        if position == 1:
            new_node.next = self.head
            if self.head is not None:
                self.head.prev = new_node
            self.head = new_node
            return
        current_node = self.head
        for i in range(position - 2):
            if current_node is None:
                break
            current_node = current_node.next
        if current_node is None:
            print("Invalid position")
            return
        new_node.next = current_node.next
        current_node.next = new_node
        new_node.prev = current_node
        if new_node.next is not None:
            new_node.next.prev = new_node

    # 定位删除
    def delete_at_position(self, position):
        if position < 1 or self.head is None:
            print("Invalid position")
            return
        if position == 1:
            if self.head.next is not None:
                self.head.next.prev = None
            self.head = self.head.next
            return
        current_node = self.head
        for i in range(position - 2):
            if current_node.next is None:
                break
            current_node = current_node.next
        if current_node.next is None:
            print("Invalid position")
            return
        current_node.next = current_node.next.next
        if current_node.next is not None:
            current_node.next.prev = current_node

    # 打印链表
    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data, end=" ")
            current_node = current_node.next


# 测试
dll = DoublyLinkedList()
dll.insert_at_position(1, 1)
dll.insert_at_position(2, 2)
dll.insert_at_position(3, 3)
dll.insert_at_position(4, 4)
dll.print_list()  # 1 2 3 4
dll.delete_at_position(2)
dll.print_list()  # 1 3 4
dll.delete_at_position(4)
dll.print_list()  # 1 3
dll.insert_at_position(2, 2)
dll.print_list()  # 1 2 3

在上面的代码中，`DoublyLinkedList`类存储双向链表的头节点，有两个方法：`insert_at_position`和`delete_at_position`，用于定位插入和定位删除。`insert_at_position`方法接收两个参数：要插入的元素值和插入的位置。如果位置无效，则打印错误信息并返回。如果位置为1，则将新节点插入到头部。否则，遍历链表直到找到插入位置的前一个节点，然后将新节点插入到前一个节点后面。`delete_at_position`方法接收一个参数：要删除的位置。如果位置无效，则打印错误信息并返回。如果位置为1，则将头节点指向下一个节点。否则，遍历链表直到找到要删除的节点的前一个节点，然后将前一个节点的下一个指针指向要删除节点的下一个节点。`print_list`方法用于打印链表。在测试中，我们创建了一个双向链表并进行了一些插入和删除操作。