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