Python - zaawansowana lista połączona

Widzieliśmy już listę połączoną we wcześniejszym rozdziale, w którym można podróżować tylko do przodu. W tym rozdziale widzimy inny typ połączonej listy, w której można podróżować zarówno do przodu, jak i do tyłu. Taka lista połączona jest nazywana listą podwójnie połączoną. Poniżej przedstawiono funkcje podwójnie połączonej listy.

Lista podwójnie połączona zawiera element łącza o nazwie pierwszy i ostatni.
Każde łącze zawiera pole (a) danych i dwa pola łącza o nazwach next i prev.
Każde łącze jest połączone z kolejnym łączem za pomocą następnego łącza.
Każde łącze jest połączone z poprzednim łączem za pomocą poprzedniego łącza.
Ostatni link niesie link jako pusty, aby oznaczyć koniec listy.

Tworzenie listy podwójnie połączonej

Tworzymy listę podwójnie połączoną za pomocą klasy Node. Teraz używamy tego samego podejścia, co w przypadku listy pojedynczo połączonej, ale nagłówek i następne wskaźniki zostaną użyte do prawidłowego przypisania, aby utworzyć dwa łącza w każdym z węzłów oprócz danych obecnych w węźle.

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)

Wykonanie powyższego kodu daje następujący wynik -

62 8 12

Wstawianie do listy podwójnie połączonej

tutaj zobaczymy, jak wstawić węzeł do listy podwójnych łączy za pomocą następującego programu. Program używa metody o nazwie insert, która wstawia nowy węzeł na trzeciej pozycji od początku podwójnie połączonej listy.

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

Wykonanie powyższego kodu daje następujący wynik -

62  8  13  12

Dołączanie do listy podwójnie połączonej

Dołączenie do podwójnie połączonej listy spowoduje dodanie elementu na końcu.

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

Wykonanie powyższego kodu daje następujący wynik -

62 8 12 9 45

Proszę zwrócić uwagę na położenie elementów 9 i 45 podczas operacji dołączania.