Operaciones Básicas de una Lista Enlazada, #2

Hey, ha pasado tiempo desde que escribí la primera parte. En esta secuela vamos a escribir algunos métodos que son muy útiles para las listas enlazadas, así que metámonos de lleno en el tema.

Prepend

El método prepend, como dice el nombre, añade un nodo al inicio de la lista enlazada. Es muy útil para cambiar el valor del head, y también para implementar pilas y colas.

La lógica del método prepend es la siguiente:

• Crea un nuevo nodo.

• Revisa si la lista enlazada está vacía. Si lo está, el nuevo nodo se convierte en el head y el tail de la lista.

• Pon la referencia next del nuevo nodo apuntando al head actual de la lista.

• Cambia la referencia del head de la lista para que apunte al nuevo nodo.

Y ya, eso es todo, sencillo ¿no? Entonces el código es:

class LinkedList:

    #   previous code

    def prepend(self, value) -> bool:
        """
        Append to the the beginning of the ll a new node
        """
        new_node = Node(value=value)
        if self.length  == 0:
            self.head   =   new_node
            self.tail   =   new_node
            self.length =  1
        else:
            #Refers the new node to the LL
            new_node.next   = self.head
            #Set the head to the new node
            self.head       = new_node
            self.length     +=  1
        return True

Pop first

Este método nos permite eliminar el primer nodo de una lista enlazada y devolverlo. Para lograrlo tenemos que seguir estos pasos:

• Revisa si la lista enlazada está vacía. Si lo está, devuelve None.

• Si no está vacía, referencia el head (el nodo) en una variable temp.

• Cambia el head para que referencie al siguiente nodo al que apuntaba el head actual.

• El nodo que referenciaba la variable temp se pone en None.

• Devuelve el valor de temp.

Es un método muy simple, el código es:

class LinkedList:

    #   previous code

    def pop_firs(self) -> any:
        """
        Delete from the ll the first element and return it

        Return
            None:   If the lenght of the ll is 0
            Any:    The value of the node
        """
        if self.length == 0:
            return None
        else:
            temp = self.head
            self.head = self.head.next
            temp.next = None
            self.length -= 1
            if self.length == 0:
                self.tail = None
            return temp.value

Get

Este método devuelve la referencia a un nodo según un índice de la lista enlazada que se le pasa. El código es muy simple. Revisa estos pasos y juzga por ti mismo:

• Primero, revisa si el índice pasado al método es válido.

• Si no lo es, devuelve None.

• Si es válido, recorre la lista enlazada hasta el índice del nodo.

• Devuelve la referencia al nodo.

El código es:

class LinkedList:

    #   previous code
    def get(self, index) -> any:
        """
        Return the node according to the index pass to the function

        Return:
            None:   If the index its out of range or is less than 0
            Any:    The value of the node
        """
        if index < 0 or index > self.length:
            return None
        else:
            temp = self.head
            # The underscore is use to
            for _ in range(index):
                temp = temp.next
            return temp

Set value

Para implementar este método, cambiamos el valor de un nodo según el índice pasado como argumento. Usamos el método get descrito en el punto anterior. El pseudocódigo es el siguiente:

• Usa el método get para obtener el nodo en la lista enlazada, 😅.

• Si get devuelve None, no hagas ningún cambio.

• Si get devuelve una referencia, cambia el atributo value del nodo por el nuevo valor pasado como argumento al método.

El código es:

class LinkedList:

    #   previous code

    def set_value(self, index, value) -> bool:
        """
        Change the value of a node according to the index pass to the function.

        Return
            True:   If the change was succesful
            False:  If the index it's out of range or less than 0
        """
        temp = self.get(index=index)

        if temp:
            temp.value = value
            return True
        return False

Insert

Este método es un poco más complicado que los otros tres descritos en los puntos anteriores. El método insert consiste en añadir un nuevo nodo en el índice pasado como argumento a la función. Para este método usamos algo del conocimiento aprendido en los métodos anteriores, en concreto la lógica del método get, y usamos variables para guardar las referencias.

La lógica del método insert es la siguiente:

• Revisa si el índice pasado como argumento es válido.

• Si no es válido, devuelve false.

• Si es válido:

• Si el índice pasado como argumento es igual a 0, podemos usar insert 🤌.

• Si el índice pasado como argumento es igual a la longitud de la lista enlazada, usamos el método append 🤌.

• En cualquier otro caso, hay que escribir un poco más de código:

• Primero, crea un nuevo nodo.

• Usa el método get para obtener la referencia al nodo anterior a la posición del índice donde queremos insertar.

• Referencia el nuevo nodo a la siguiente referencia del nodo anterior.

• Referencia el nodo anterior al nuevo nodo.

Y eso es todo, ¡el código está listo!

class LinkedList:

    #   previous code

    def insert(self, index, value) -> bool:
        """
        Insert a new node in the ll according to the index pass to the function

        Return
            True:   If the insert was successful
            False:  If the index it's out of range or is less than zero
        """
        if index < 0 or index > self.length:
            return False
        if index == 0:
            self.prepend(value=value)
            return True
        elif index == self.length:
            self.append(value=value)
            return True
        else:
            new_node        = Node(value=value)
            temp            = self.get(index= index - 1)
            new_node.next   = temp.next
            temp.next       = new_node
            self.length     += 1
            return True

La canción del post

El cuarto de Tula, le cogió candela
Se quedó dormida y no apagó la vela
Candela, muchacho
Se volvió loco, Barbarito
¡Hay que ingresarlo!
· El Cuarto de Tula, Buena Vista Social Club