Operaciones Básicas de una Lista Enlazada, #1

En un post anterior ya dejamos la base de la clase de lista enlazada. En este post vamos a escribir algo de código para ampliarla, así que vamos a crear los métodos append, pop y print. Metámonos de lleno en el código.

Append

El método append añade un elemento al final de la lista enlazada. Para crear este método sigue estos pasos:

• Crea un nuevo nodo.

• Haz que el tail actual de la lista apunte al nuevo nodo.

• Cambia el tail de la lista al nuevo nodo.

• Incrementa el tamaño de la lista enlazada.

class LinkedList:

    #   previous code

    def append(self, value) -> bool:
        """
        The append method add a new node to the LL
        The tail of the LL, will be the new node
        """
        new_node = Node(value = value)
        #Check if the LL is empty
        if self.length == 0:
            self.head   = new_node
            self.tail   = new_node
            self.length = 1
        else:
            #The current tail refence to the new_node
            self.tail.next  = new_node
            #The new_node is now the tail of the LL
            self.tail       = new_node
            #Increase the lenght of the LL
            self.length     += 1
        return True

Pop

El método pop elimina el último nodo de una lista enlazada y lo devuelve. Este método es más complejo que append, porque hay que eliminar el último elemento y mover el tail al nodo anterior. Como las listas enlazadas no tienen índices, hay que recorrer toda la lista para encontrar el nodo previo al tail. Luego, ese nodo previo pasa a ser el nuevo tail y se desreferencia el tail actual. Para lograrlo usamos dos variables en el método, temp y previous. La variable temp recorre toda la lista hasta llegar a None, y la variable previous guarda el nodo anterior a temp en cada iteración. En resumen, los pasos son:

• Poner las variables temp y prev en el head de la lista enlazada.

• Recorrer la lista mientras temp.next no sea None.

• Mover prev a temp, y temp a la siguiente referencia, en cada iteración.

• Al llegar al final de la LL, poner en None el next de prev.

• Devolver temp.

class LinkedList:

    #   previous code

    def pop(self) -> any:
        """
        The append method delete the last node of the LL
        The tail of the LL, will be the previous node to the tail

        Return:
            the node poped in the LL
        """
        #Check if the LL is empty
        if self.length == 0:
            return None
        temp = self.head
        prev = self.head
        #Iterate over every node of the LL until temp is None
        while(temp.next):
            prev = temp
            #Move temp to the next node
            temp = temp.next
        #Set the tail to the previous node
        self.tail       = prev
        self.tail.next  = None
        self.length     -= 1
        #If before pop the node into the LL the lenght is 0, set head and tail to None
        if self.length == 0:
            print("h")
            self.head = None
            self.tail = None
        #Return the pop element
        return temp

Print

El método print es muy básico. Recorre la lista enlazada e imprime el valor de cada nodo. No hace falta que explique el código, se entiende solo.

class LinkedList:

    #   previous code

    def print(self) -> None:
        """
        Print every value of the nodes in the LL in ascendent order, this mean to the head until the tail
        """
        current_node = self.head
        #Iterate over every node of the LL until temp is None
        while(current_node):
            print(current_node.value)
            #Move to the next node
            current_node = current_node.next

La canción del post

¡Te están buscando, matador!
Me dicen el matador, nací en Barracas
Si hablamos de matar mis palabras matan
No hace mucho tiempo que cayó el León Santillán
Y ahora sé que, en cualquier momento, me la van a dar
· El Matador, Los Fabulosos Cadillacs