在前面的章節(jié)中已經(jīng)看到并學(xué)習(xí)了鏈表，但在前面只是進(jìn)行介紹和入門。 在本章中，我們看到另一種鏈接列表，可以向前和向后移動遍歷。 這種鏈表稱為雙向鏈表。 以下是雙向鏈表的特點(diǎn)。

• 雙向鏈表包含第一個和最后一個的鏈接元素。
• 每個鏈接都有一個數(shù)據(jù)字段和兩個稱為next和prev的鏈接字段。
• 每個鏈接都使用其下一個鏈接與其下一個鏈接鏈接。
• 每個鏈接都使用其上一個鏈接與之前的鏈接鏈接。
• 最后一個鏈接將鏈接作為空來標(biāo)記列表的結(jié)尾。

創(chuàng)建雙向鏈表

我們使用Node類創(chuàng)建一個雙鏈表。 使用與單鏈表中相同的方法，但是除了存在于節(jié)點(diǎn)中的數(shù)據(jù)之外，頭指針和下一個指針將用于正確分配以在每個節(jié)點(diǎn)中創(chuàng)建兩個鏈接。

參考以下代碼的實(shí)現(xiàn) -

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)

執(zhí)行上面示例代碼，得到以下結(jié)果 -

62
8
12

插入雙鏈表中

在這里將演示如何使用以下程序?qū)⒐?jié)點(diǎn)插入到雙向鏈接列表中。 該程序使用一個名為insert()的方法，它將新節(jié)點(diǎn)插入到雙向鏈表頭部的第三個位置。

參考以下代碼的實(shí)現(xiàn) -

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

執(zhí)行上面示例代碼，得到以下結(jié)果 -

62
8
13
12

附加到雙向鏈表

追加節(jié)點(diǎn)(元素)到雙向鏈表的最后位置。參考以下代碼的實(shí)現(xiàn) -

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

執(zhí)行上面示例代碼，得到以下結(jié)果 -

62
8
12
9
45

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