Python: lista vinculada avanzada

Ya hemos visto Linked List en el capítulo anterior en el que solo es posible viajar hacia adelante. En este capítulo vemos otro tipo de lista enlazada en la que es posible viajar tanto hacia adelante como hacia atrás. Esta lista enlazada se denomina Lista doblemente enlazada. A continuación se muestran las características de la lista doblemente enlazada.

  • La lista doblemente enlazada contiene un elemento de enlace llamado primero y último.
  • Cada enlace lleva un campo de datos y dos campos de enlace llamados siguiente y anterior.
  • Cada enlace está vinculado con su siguiente enlace utilizando su siguiente enlace.
  • Cada enlace está vinculado con su enlace anterior utilizando su enlace anterior.
  • El último enlace lleva un enlace como nulo para marcar el final de la lista.

Creando una lista doblemente enlazada

Creamos una lista Doblemente Vinculada usando la clase Node. Ahora usamos el mismo enfoque que se usó en la Lista de enlaces sencillos, pero el encabezado y los punteros siguientes se utilizarán para la asignación adecuada para crear dos enlaces en cada uno de los nodos además de los datos presentes en el 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)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

62 8 12

Insertar en una lista doblemente vinculada

aquí vamos a ver cómo insertar un nodo en la lista de enlaces dobles usando el siguiente programa. El programa usa un menthod llamado insert que inserta el nuevo nodo en la tercera posición del encabezado de la lista doblemente enlazada.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

62  8  13  12

Agregar a una lista doblemente enlazada

Agregar a una lista doblemente enlazada agregará el elemento al final.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

62 8 12 9 45

Tenga en cuenta la posición de los elementos 9 y 45 para la operación de adición.