Python - Erweiterte verknüpfte Liste

Wir haben bereits in einem früheren Kapitel eine verknüpfte Liste gesehen, in der es nur möglich ist, vorwärts zu reisen. In diesem Kapitel sehen wir eine andere Art von verknüpfter Liste, in der es möglich ist, sowohl vorwärts als auch rückwärts zu reisen. Eine solche verknüpfte Liste wird als doppelt verknüpfte Liste bezeichnet. Es folgen die Merkmale einer doppelt verknüpften Liste.

Die doppelt verknüpfte Liste enthält ein Verknüpfungselement mit den Namen first und last.
Jede Verbindung enthält ein Datenfeld und zwei Verbindungsfelder, die als next und prev bezeichnet werden.
Jeder Link wird über seinen nächsten Link mit seinem nächsten Link verknüpft.
Jeder Link ist über seinen vorherigen Link mit seinem vorherigen Link verknüpft.
Der letzte Link enthält einen Link als null, um das Ende der Liste zu markieren.

Doppelt verknüpfte Liste erstellen

Wir erstellen eine doppelt verknüpfte Liste mithilfe der Node-Klasse. Jetzt verwenden wir den gleichen Ansatz wie in der einfach verknüpften Liste, aber der Kopf und die nächsten Zeiger werden für die ordnungsgemäße Zuweisung verwendet, um zusätzlich zu den im Knoten vorhandenen Daten zwei Verknüpfungen in jedem der Knoten zu erstellen.

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)

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

62 8 12

Einfügen in eine doppelt verknüpfte Liste

Hier erfahren Sie, wie Sie mit dem folgenden Programm einen Knoten in die Liste der doppelten Verknüpfungen einfügen. Das Programm verwendet ein Menthod namens insert, das den neuen Knoten an der dritten Position vom Kopf der doppelt verknüpften Liste einfügt.

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

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

62  8  13  12

Anhängen an eine doppelt verknüpfte Liste

Durch Anhängen an eine doppelt verknüpfte Liste wird das Element am Ende hinzugefügt.

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

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

62 8 12 9 45

Bitte beachten Sie die Position der Elemente 9 und 45 für die Append-Operation.