在双向链表中间插入新节点的Python程序

双向链表是一种链式数据结构，它的每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。与单向链表相比，双向链表可以从前向后或从后向前遍历，因此在某些场景下更为灵活。

在双向链表中添加节点的方法与单向链表类似，但是在插入节点时需要考虑更多的指针操作。本文将介绍在双向链表中间插入新节点的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
        self.tail = None

    def append(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
            self.tail = node
            return
        node.prev = self.tail
        self.tail.next = node
        self.tail = node

    def prepend(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
            self.tail = node
            return
        node.next = self.head
        self.head.prev = node
        self.head = node

    def print_list(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

    def insert_after_node(self, prev_node, data):
        if not prev_node:
            print("Previous node is not in the list")
            return
        node = Node(data)
        node.next = prev_node.next
        node.prev = prev_node
        if node.next:
            node.next.prev = node
        else:
            self.tail = node
        prev_node.next = node

上述代码中，包含四个方法：

• append()方法：在链表尾部添加新节点。
• prepend()方法：在链表头部添加新节点。
• print_list()方法：打印整个链表。
• insert_after_node()方法：在给定的节点后面插入新节点。

在双向链表中间插入新节点

在双向链表中间插入新节点与在单向链表中插入新节点类似，需要先找到要插入位置的前一个节点，然后操作指针链接，将新节点插入到链表中。

下面是示例代码：

doublyLinkedList = DoublyLinkedList()
doublyLinkedList.append(1)
doublyLinkedList.append(2)
doublyLinkedList.append(4)
doublyLinkedList.append(5)
doublyLinkedList.print_list()
node = doublyLinkedList.head.next.next # node的值为指向节点3的指针
doublyLinkedList.insert_after_node(node, 3)
doublyLinkedList.print_list()

在上面的代码中，首先定义一个双向链表，并向其中添加四个节点。然后找到要插入位置的前一个节点，即指向节点3的指针。接着调用insert_after_node()方法，在指向节点3的指针后面插入新节点3。最后打印整个链表，可以看到新节点已经成功插入链表中。

解释关键步骤

在上面的代码中，我们使用了insert_after_node()方法向链表中插入新节点，接下来我们来具体解释一下这个方法的关键步骤。

首先，在方法中判断要插入的位置是否合法，即前一个节点是否在链表中。如果不在，就打印提示信息并退出方法。

if not prev_node:
    print("Previous node is not in the list")
    return

然后，创建新的节点并指定它的值。

node = Node(data)

将新节点的指针链接到前一个节点的下一个节点，将前一个节点的下一个指针链接到新节点。同时，将新节点的前向指针链接到前一个节点。

node.next = prev_node.next
prev_node.next = node
node.prev = prev_node

如果新节点的下一个节点存在，则将它的前向指针链接到新节点。

if node.next:
    node.next.prev = node

如果新节点加入了链表尾部，则需要更新链表的尾节点。

else:
    self.tail = node

结论

以上就是在双向链表中间插入新节点的Python程序及解释。双向链表适用于需要频繁在链表中间添加或删除节点的场景。在插入新节点时，需要考虑更多的指针操作，但是通过定义好的节点和链表类，可以让插入节点的操作变得更为方便和简洁。