Python - 高階連結串列

我們已經在前面的章節中看到了連結串列，其中只能向前遍歷。本章我們將介紹另一種型別的連結串列，它可以向前和向後遍歷。這種連結串列稱為雙向連結串列。以下是雙向連結串列的特點。

雙向連結串列包含一個名為 first 和 last 的連結元素。
每個連結都包含一個或多個數據欄位和兩個連結欄位，分別稱為 next 和 prev。
每個連結都使用其 next 連結與其下一個連結連結。
每個連結都使用其 prev 連結與其前一個連結連結。
最後一個連結使用 null 連結來標記列表的結尾。

建立雙向連結串列

我們使用 Node 類來建立一個雙向連結串列。現在我們使用與單向連結串列中相同的方法，但是 head 和 next 指標將用於正確賦值，以便在每個節點中建立兩個連結，此外還有節點中存在的資料。

示例

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)

輸出

執行上述程式碼後，將產生以下結果：

62  8  13  12

追加到雙向連結串列

追加到雙向連結串列將把元素新增到末尾。

示例

# 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 和 45 的位置。

列印頁面