Python高階連結串列（雙向連結串列）

在前面的章節中已經看到並學習了連結串列，但在前面只是進行介紹和入門。在本章中，我們看到另一種連結列表，可以向前和向後移動遍歷。這種連結串列稱為雙向連結串列。以下是雙向連結串列的特點。

雙向連結串列包含第一個和最後一個的連結元素。
每個連結都有一個資料欄位和兩個稱為next和prev的連結欄位。
每個連結都使用其下一個連結與其下一個連結連結。
每個連結都使用其上一個連結與之前的連結連結。
最後一個連結將連結作為空來標記列表的結尾。

建立雙向連結串列

我們使用Node類建立一個雙連結串列。使用與單連結串列中相同的方法，但是除了存在於節點中的資料之外，頭指標和下一個指標將用於正確分配以在每個節點中建立兩個連結。

參考以下程式碼的實現 -

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

class doubly_linked_list:

    def __init__(self):
        self.head = None

# Adding data elements        
    def push(self, NewVal):
        NewNode = Node(NewVal)
        NewNode.next = self.head
        if self.head is not None:
            self.head.prev = NewNode
        self.head = NewNode

# Print the Doubly Linked list        
    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.push(8)
dllist.push(62)
dllist.listprint(dllist.head)

執行上面範例程式碼，得到以下結果 -

62
8
12

插入雙連結串列中

在這裡將演示如何使用以下程式將節點插入到雙向連結列表中。該程式使用一個名為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 doubly_linked_list:

    def __init__(self):
        self.head = None

# Define the push method to add elements        
    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 insert method to insert the element        
    def insert(self, prev_node, NewVal):
        if prev_node is None:
            return
        NewNode = Node(NewVal)
        NewNode.next = prev_node.next
        prev_node.next = NewNode
        NewNode.prev = prev_node
        if NewNode.next is not None:
            NewNode.next.prev = NewNode

# Define the method to print the linked list 
    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.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)

執行上面範例程式碼，得到以下結果 -

附加到雙向連結串列

追加節點(元素)到雙向連結串列的最後位置。參考以下程式碼的實現 -

# 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)

執行上面範例程式碼，得到以下結果 -

注意:元素9和45在追加操作中的位置。