Python – Listas enlazadas

Una lista enlazada es una secuencia de elementos de datos, que están conectados entre sí a través de enlaces. Cada elemento de datos contiene una conexión con otro elemento de datos en forma de puntero. Python no tiene listas enlazadas 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 nodo y cómo recorrer los elementos de un nodo.En este capítulo vamos a estudiar los tipos de listas enlazadas conocidos como listas unidireccionales. En este tipo de estructura de datos sólo hay un enlace entre dos elementos de datos cualquiera. Creamos una lista de este tipo y creamos métodos adicionales para insertar, actualizar y eliminar elementos de la lista.

Creación de listas enlazadas

Una lista enlazada se crea utilizando la clase nodo que estudiamos en el último capítulo. Creamos un objeto Node y creamos otra clase para utilizar este objeto ode. Pasamos los valores apropiados a través del objeto node para apuntar a los siguientes elementos de datos. El siguiente programa crea la lista enlazada 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 = Noneclass SLinkedList: def __init__(self): self.headval = Nonelist1 = SLinkedList()list1.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist1.headval.nextval = e2# Link second Node to third nodee2.nextval = e3

Recorrer una lista enlazada

Las listas enlazadas pueden ser recorridas sólo en dirección forwrad empezando por 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.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist.headval.nextval = e2# Link second Node to third nodee2.nextval = e3list.listprint()

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

MonTueWed

Inserción en una lista enlazada

Insertar un elemento en la lista enlazada implica reasignar los punteros de los nodos existentes al nuevo nodo insertado. Dependiendo de si el nuevo elemento de datos se inserta al principio, a la mitad o al final de la lista enlazada, tenemos los siguientes escenarios.

Inserción al principio de la lista enlazada

Esto implica apuntar el siguiente puntero del nuevo nodo de datos a la cabeza actual de la lista enlazada. Así, la cabeza actual de la lista enlazada se convierte en el segundo elemento de datos y el nuevo nodo se convierte en la cabeza de la lista enlazada.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass 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 = NewNodelist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtBegining("Sun")list.listprint()

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

SunMonTueWed

Inserción al final de la lista enlazada

Esto implica apuntar el siguiente puntero del último nodo actual de la lista enlazada al nuevo nodo de datos. Así, el último nodo actual de la lista enlazada se convierte en el penúltimo nodo de datos y el nuevo nodo se convierte en el último nodo de la lista enlazada.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass 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.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtEnd("Thu")list.listprint()

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

MonTueWedThu

Inserción entre dos nodos de datos

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

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass 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.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Thu")list.headval.nextval = e2e2.nextval = e3list.Inbetween(list.headval.nextval,"Fri")list.listprint()

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

MonTueFriThu

Eliminar un elemento de una lista de favoritos

Podemos eliminar un nodo existente utilizando la clave de dicho nodo. En el siguiente programa localizamos el nodo anterior del nodo que se quiere eliminar.Luego apuntamos el siguiente puntero de este nodo al siguiente nodo del nodo que se quiere eliminar.

class Node: def __init__(self, data=None): self.data = data self.next = Noneclass 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.nextllist = SLinkedList()llist.Atbegining("Mon")llist.Atbegining("Tue")llist.Atbegining("Wed")llist.Atbegining("Thu")llist.RemoveNode("Tue")llist.LListprint()

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

ThuWedMon