迹忆客 专注技术分享

本文将演示使用 Python 编程语言创建双向链表。

在 Python 中创建双向链表

双向链表是指由称为节点的顺序链接的记录集组成的链接数据结构。 每个节点包含一个前一个指针、一个下一个指针和一个数据字段。

Previous 和 next 指针指向上一个和下一个节点。 第一个节点上的 previous 指针和最后一个节点上的 next 指针指向 None。

我们可以在双向链表中的给定节点前后插入一个新节点。 此外，我们可以向前和向后遍历双向链表。

但是，每个双向链表节点都需要额外的空间来存放前一个指针。

节点类创建如下。 指针和数据值默认为无。

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

然后，创建用于双向链表的类。 self.head 表示列表的头部，最初是 None 。

我们将使用 add_to_end 函数将新节点添加到双向链表的末尾。 首先，我们使用 new_node 变量创建一个 Node 类实例。

由于 new_node 将是列表的最后一个值，我们将其 next 指针设置为 None。 我们定义最后一个变量来查找我们将添加 new_node 的节点。

首先，这个变量是双向链表的头（对于第一个添加的节点，这个头将为 None）。

我们检查 if 块中的 self.head 是否为 None 。 如果是这样，列表中没有节点，现在列表的头部将是新添加的节点。

在 while 块中，我们检查最后一个变量的下一个指针以找到列表的最后一个值。 我们用 last.next 替换最后一个变量，直到我们得到 None。

当我们找到 last.next 值为 None 的节点时，我们结束列表。

我们将找到的最后一个节点值的 next 指针设置为指向 new_node。 最后，我们将 new_node 变量的前一个指针设置为最后一个变量。

因此，new_node 节点被添加到双向链表的末尾。

请参阅下面的代码。

class DoublyLinkedList:

    def __init__(self):
        self.head = None

    def add_to_end(self, new_node):

        new_node = Node(data = new_node)
        new_node.next = None
        last = self.head

        if self.head is None:
            new_node.previous = None
            self.head = new_node
            return

        while (last.next is not None):
            last = last.next

        last.next = new_node
        new_node.previous = last

我们可以使用 add_to_beginning 函数将节点添加到双向链表的开头。 这个过程更直接。

首先，我们将 new_node 变量的 next 指针设置为 self.head，将 previous 指针设置为 None。 所以 head 值，旧列表的第一个值，成为 new_node 指向的下一个值。

在 if 块中，如果列表为空，我们检查 self.head 值是否为 None。 如果定义了这个值或者有head对应的节点，我们就把这个节点的previous指针改成new_node。

最后，我们将 self.head 更改为 new_node。 因此，new_node 被添加到双向链表的开头。

请参阅下面的代码演示。

class DoublyLinkedList:

    def __init__(self):
        self.head = None

    def add_to_end(self, new_node):
        # previous function

    def add_to_beginning(self, new_node):

        new_node = Node(data = new_node)
        new_node.next = self.head
        new_node.previous = None

        if self.head is not None:
            self.head.previous = new_node

        self.head = new_node

在下面的示例中，首先创建了 doubly_linked_list 变量。 此变量是 DoublyLinkedList 类的一个实例。

然后我们分别在列表的末尾添加 1 和 3，在开头添加 5。 列表的最终状态是 5 -> 1 -> 3 -> None。

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)