Python数据结构指南：双向链表（Doubly Linked List）

另一种可以通过来回遍历的链表。这种类型的链表称为双向链表。以下是双向链表的属性。

• 双向链表包含第一个和最后一个链接元素。
• 每个链接都有一个数据字段和两个名为 next 和 prev 的链接字段。
• 每个链接都使用下一个链接链接到下一个链接。
• 每个链接都使用前一个链接链接到前一个链接。
• 最后一个链接通过将链接留空来标记列表的结尾。

创建双向链表

我们使用类 Node 来创建双向链表。使用与单链表相同的过程，但除了节点中包含的数据之外，头指针和后续指针也用在适当的部分中，为每个节点创建两个链接。 ？在双向链表中。该程序使用了一种名为 insert() 的方法，该方法在双向链表头部的第三个位置插入一个新节点。 ？ 。看下面代码的实现 -

# Create the node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
# Create the doubly linked list class
class doubly_linked_list:

    def __init__(self):
        self.head = None

# Define the push method to add elements at the begining
    def push(self, NewVal):
        NewNode = Node(NewVal)
        NewNode.next = self.head
        if self.head is not None:
            self.head.prev = NewNode
        self.head = NewNode

# Define the append method to add elements at the end
    def append(self, NewVal):

        NewNode = Node(NewVal)
        NewNode.next = None
        if self.head is None:
            NewNode.prev = None
            self.head = NewNode
            return
        last = self.head
        while (last.next is not None):
            last = last.next
        last.next = NewNode
        NewNode.prev = last
        return

# Define the method to print
    def listprint(self, node):
        while (node is not None):
            print(node.data),
            last = node
            node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.append(9)
dllist.push(8)
dllist.push(62)
dllist.append(45)
dllist.listprint(dllist.head)

运行上面的示例代码，得到以下结果 -

62
8
12
9
45

注意：元素9和操作的位置。