Python - Listas vinculadas

Una lista enlazada es una secuencia de elementos de datos, que están conectados entre sí mediante enlaces. 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 individualmente. 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 vinculada

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

Atravesar una lista vinculada

Las listas enlazadas individualmente se pueden recorrer solo en dirección hacia adelante 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.

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

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 de la lista vinculada

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.

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

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

Sun
Mon
Tue
Wed

Insertar al final de la lista vinculada

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.

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

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 medio. 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()

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

Mon
Tue
Fri
Thu

Eliminar un elemento de una lista de favoritos

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

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

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

Thu
Wed
Mon