Python: elenco collegato avanzato

Abbiamo già visto la lista collegata nel capitolo precedente in cui è possibile solo andare avanti. In questo capitolo vediamo un altro tipo di lista concatenata in cui è possibile viaggiare sia avanti che indietro. Tale elenco collegato è chiamato Elenco doppio collegamento. Di seguito sono riportate le caratteristiche della lista doppiamente collegata.

  • La lista doppiamente collegata contiene un elemento di collegamento chiamato primo e ultimo.
  • Ogni collegamento contiene uno o più campi dati e due campi di collegamento denominati successivo e precedente.
  • Ogni collegamento è collegato al collegamento successivo utilizzando il collegamento successivo.
  • Ogni collegamento è collegato al collegamento precedente utilizzando il collegamento precedente.
  • L'ultimo collegamento porta un collegamento come nullo per contrassegnare la fine dell'elenco.

Creazione di una lista doppiamente collegata

Creiamo un elenco Doubly Linked utilizzando la classe Node. Ora utilizziamo lo stesso approccio utilizzato nell'Elenco collegato singolarmente, ma per l'assegnazione corretta verranno utilizzati i puntatori head e next per creare due collegamenti in ciascuno dei nodi oltre ai dati presenti nel nodo.

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)

Quando il codice sopra viene eseguito, produce il seguente risultato:

62 8 12

Inserimento in una lista doppiamente collegata

qui andremo a vedere come inserire un nodo nella Doubly Link List utilizzando il seguente programma. Il programma utilizza un metodo denominato insert che inserisce il nuovo nodo alla terza posizione dall'inizio della lista doppiamente concatenata.

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

Quando il codice sopra viene eseguito, produce il seguente risultato:

62  8  13  12

Aggiunta a una lista doppiamente collegata

L'aggiunta a una lista doppiamente collegata aggiungerà l'elemento alla fine.

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

Quando il codice sopra viene eseguito, produce il seguente risultato:

62 8 12 9 45

Notare la posizione degli elementi 9 e 45 per l'operazione di aggiunta.