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