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在追加操作中的位置。

Python數據結構

Python高級鏈表（雙向鏈表）