Saltar al contenido

Python – Listas vinculadas

septiembre 23, 2021

Una lista vinculada es una secuencia de elementos de datos, que están conectados entre sí mediante vínculos. Cada elemento de datos contiene una conexión a otro elemento de datos en forma de puntero. Python no tiene listas vinculadas en su biblioteca estándar. Implementamos el concepto de listas enlazadas usando el concepto de nodos como se discutió en el capítulo anterior.

Ya hemos visto cómo creamos una clase de nodo y cómo atravesar los elementos de un nodo. En este capítulo vamos a estudiar los tipos de listas enlazadas conocidas como listas enlazadas simples. En este tipo de estructura de datos, solo hay un vínculo entre dos elementos de datos. Creamos dicha lista y creamos métodos adicionales para insertar, actualizar y eliminar elementos de la lista.

Creación de lista enlazada

Se crea una lista vinculada utilizando la clase de nodo que estudiamos en el último capítulo. Creamos un objeto Node y creamos otra clase para usar este objeto Ode. Pasamos los valores apropiados a través del objeto de nodo para apuntar a los siguientes elementos de datos. El siguiente programa crea la lista vinculada con tres elementos de datos. En la siguiente sección veremos cómo recorrer la lista enlazada.

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Atravesando una lista vinculada

Las listas enlazadas individualmente se pueden recorrer solo en la dirección de avance comenzando desde el primer elemento de datos. Simplemente imprimimos el valor del siguiente elemento de datos asignando el puntero del siguiente nodo al elemento de datos actual.

Ejemplo

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None

   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

Producción

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

Mon
Tue
Wed

Inserción en una lista vinculada

Insertar un elemento en la lista vinculada implica reasignar los punteros de los nodos existentes al nodo recién insertado. Dependiendo de si el nuevo elemento de datos se inserta al principio, en el medio o al final de la lista vinculada, tenemos los siguientes escenarios.

Insertar al principio

Esto implica apuntar el siguiente puntero del nuevo nodo de datos al encabezado actual de la lista vinculada. Entonces, el encabezado actual de la lista vinculada se convierte en el segundo elemento de datos y el nuevo nodo se convierte en el encabezado de la lista vinculada.

Ejemplo

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval
   def AtBegining(self,newdata):
      NewNode = Node(newdata)

# Update the new nodes next val to existing node
   NewNode.nextval = self.headval
   self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")
list.listprint()

Producción

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

Sun
Mon
Tue
Wed

Insertar al final

Esto implica apuntar el siguiente puntero del último nodo actual de la lista vinculada al nuevo nodo de datos. Entonces, el último nodo actual de la lista vinculada se convierte en el segundo último nodo de datos y el nuevo nodo se convierte en el último nodo de la lista vinculada.

Ejemplo

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None
class SLinkedList:
   def __init__(self):
      self.headval = None
# Function to add newnode
   def AtEnd(self, newdata):
      NewNode = Node(newdata)
      if self.headval is None:
         self.headval = NewNode
         return
      laste = self.headval
      while(laste.nextval):
         laste = laste.nextval
      laste.nextval=NewNode
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

Producción

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

Mon
Tue
Wed
Thu

Insertar entre dos nodos de datos

Esto implica cambiar el puntero de un nodo específico para que apunte al nuevo nodo. Eso es posible pasando tanto el nodo nuevo como el nodo existente, después de lo cual se insertará el nuevo nodo. Entonces definimos una clase adicional que cambiará el siguiente puntero del nuevo nodo al siguiente puntero del nodo intermedio. Luego, asigne el nuevo nodo al siguiente puntero del nodo del medio.

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None
class SLinkedList:
   def __init__(self):
      self.headval = None

# Function to add node
   def Inbetween(self,middle_node,newdata):
      if middle_node is None:
         print("The mentioned node is absent")
         return

      NewNode = Node(newdata)
      NewNode.nextval = middle_node.nextval
      middle_node.nextval = NewNode

# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

Producción

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

Mon
Tue
Fri
Thu

Eliminar un artículo

Podemos eliminar un nodo existente usando la clave para ese nodo. En el programa a continuación, ubicamos el nodo anterior del nodo que se va a eliminar y, a continuación, apunte el siguiente puntero de este nodo al siguiente nodo del nodo que se eliminará.

Ejemplo

class Node:
   def __init__(self, data=None):
      self.data = data
      self.next = None
class SLinkedList:
   def __init__(self):
      self.head = None

   def Atbegining(self, data_in):
      NewNode = Node(data_in)
      NewNode.next = self.head
      self.head = NewNode

# Function to remove node
   def RemoveNode(self, Removekey):
      HeadVal = self.head
         
      if (HeadVal is not None):
         if (HeadVal.data == Removekey):
            self.head = HeadVal.next
            HeadVal = None
            return
      while (HeadVal is not None):
         if HeadVal.data == Removekey:
            break
         prev = HeadVal
         HeadVal = HeadVal.next

      if (HeadVal == None):
         return

      prev.next = HeadVal.next
         HeadVal = None

   def LListprint(self):
      printval = self.head
      while (printval):
         print(printval.data),
         printval = printval.next

llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

Producción

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

Thu
Wed
Mon
close