在双向链表的末尾插入新节点的Python程序

双向链表是一种常见的数据结构，它在处理链表数据时比单向链表更灵活。在双向链表中，每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。

在双向链表的末尾插入新节点是一个常见的操作，本文将介绍如何在Python中实现。

更多Python相关文章，请阅读：Python 教程

双向链表的Node类

首先，我们需要定义一个Node类，表示双向链表的节点。

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

上述代码定义了一个Node类，包含三个属性：data表示节点存储的数据，prev表示指向前一个节点的指针，next表示指向后一个节点的指针。在初始化时，这三个属性的值都为None。

双向链表的类

接下来，我们需要定义一个DoublyLinkedList类，代表双向链表。这个类包含以下几个方法：

构造方法：init

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

上述代码定义了一个DoublyLinkedList类，它包含一个属性head表示链表的头节点。在初始化时，这个属性的值为None，表示链表为空。

在末尾插入新节点：append

def append(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = new_node
        new_node.prev = cur

上述代码定义了一个方法append，用于在双向链表的末尾插入新节点。首先创建一个新节点new_node，并将它的数据设置为方法参数data的值。然后判断链表是否为空，如果是，则将新节点设置为头节点；否则，找到链表的最后一个节点，将新节点添加到其后面。需要注意的是，双向链表下一个节点的指针既可以指向下一个节点，也可以指向上一个节点，因此在添加新节点时需要同时设置前一个节点的next指针和新节点的prev指针。

示例代码

下面是一个完整的示例代码，演示了如何使用上述类在双向链表的末尾插入新节点。

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


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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = new_node
            new_node.prev = cur


if __name__ == '__main__':
    dll = DoublyLinkedList()
    dll.append(1)
    dll.append(2)
    dll.append(3)
    cur = dll.head
    while cur is not None:
        print(cur.data)
        cur = cur.next

上述代码创建了一个DoublyLinkedList对象dll，并向其中添加了三个节点，然后遍历整个链表，输出每个节点的数据。