Lista Doblemente Enlazada

¡Hey! ❗❗❗ Volví, y traigo dos cosas conmigo:

• La primera, una nueva estructura de datos.

• La segunda, una nueva banda de música que me gusta mucho, y los posts sobre esta nueva estructura de datos van a seguir la vibra que me da esta banda 🥥🏝️🐠🌊.

Así que, ¡vamos a ello!

Lista doblemente enlazada

Entonces, ¿qué es una lista doblemente enlazada? Básicamente es una lista enlazada bidireccional. O sea, se puede recorrer en ambas direcciones. A diferencia de las listas enlazadas simples, sus nodos tienen un puntero extra llamado previous pointer. Este puntero apunta al nodo anterior 🥸.

Para ser honesto es muy parecida a una lista enlazada normal, pero este puntero extra llamado nodo previo nos ayuda mucho a escribir métodos para nuestra clase de lista doblemente enlazada, ya lo veremos más adelante.

Clase Node 🏗️

Si recuerdas, en un post anterior ya escribimos una clase node, y esa clase será la base de nuestra clase node actual (solo le añadimos un atributo 🤫).

Código

class Node:
    def __init__(self, value: any) -> None:
        self.value = value
        self.next = None
        self.prev = None

Clase de lista doblemente enlazada

Constructor 🧱

No me voy a complicar aquí, digamos simplemente que es igual al que usamos en la lista enlazada normal. 😅

Código

class DoublyLinkedList:

    def __init__(self,value: any) -> None:
        new_node = Node(value)
        self.head   = new_node
        self.tail   = new_node
        self.length = 1

Ahhhh 🤔, creo que es buena idea añadir un método extra que nos ayude a imprimir nuestra lista enlazada, como también hicimos en la sección de lista enlazada.

Un poco de código extra 🪡

class LinkedList:

    #   previous code

    def print_list(self) -> None:
        temp = self.head

        while temp is not None:
            print(temp.value)
            temp = temp.next

Método append

El método append añade un nuevo nodo al final de la lista enlazada.

Desglose de los pasos:

1. Crea un nuevo nodo: instancia un nuevo objeto Node, pasando el value dado como argumento para guardar dentro del nodo.

2. Maneja una lista vacía:

• Si la lista está vacía actualmente (self.head is None), pone tanto el head como el tail apuntando al nodo recién creado. Esto establece el punto de partida de la lista.

1. Añade a una lista no vacía:

• Si la lista ya tiene nodos:

• Conecta el puntero next del nodo tail actual al nuevo nodo.

• Pone el puntero prev del nuevo nodo apuntando al nodo tail actual.

• Actualiza el tail de la lista para que apunte al nodo recién añadido. Esto asegura que el final de la lista se mantenga correctamente.

1. Incrementa el length: aumenta el atributo length de la lista, llevando la cuenta del número de nodos.

Código

class DoublyLinkedList:

    #   previous code

    def append(self, value: any):
        """
        It adds a new node containing a specified value to the end of a doubly linked list

        Args
            Value: the data that will contain the new node
        Return
            None
        """
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next  = new_node
            new_node.prev   = self.tail
            self.tail       = new_node
        self.length += 1

Método pop

El método pop elimina el último elemento de la lista doblemente enlazada y devuelve ese nodo.

Pasos que sigue:

1. Revisa si la lista está vacía:

• Si la lista está vacía (self.length == 0), no tiene elementos que eliminar. El método devuelve None para indicarlo.

1. Maneja la eliminación del único elemento:

• Si hay solo un elemento en la lista (self.length == 1), pone tanto head como tail en None, ya que no quedan más nodos.

1. Elimina el último elemento de una lista no vacía (length > 1):

• Guarda una referencia temporal (temp) al nodo tail actual. Este es el elemento que se va a eliminar.

• Actualiza el tail de la lista para que apunte al penúltimo nodo (temp.prev).

• Pone el puntero next del nuevo tail en None, ya que ahora es el final de la lista.

• Desconecta el nodo eliminado (temp) poniendo su puntero prev en None. Esto ayuda a evitar referencias colgantes.

1. Actualiza el length de la lista: reduce el atributo length para reflejar la eliminación del nodo.

2. Devuelve el elemento eliminado: el método devuelve la referencia temporal (temp), que contiene el dato del nodo eliminado.

Código

class DoublyLinkedList:

    #   previous code

    def pop(self) -> any:
        """
        This method removes and returns the last element from a doubly linked list.

        Return
            None: if the doubly linked list is empty
            Node: if the doubly linked list is not empty
        """
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.tail = temp.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

Método prepend

El último método que voy a describir, pero no menos importante, es el método prepend. Este método añade un nuevo nodo al inicio de la lista doblemente enlazada y devuelve true para indicar que se añadió con éxito.

Desglose de los pasos:

1. Crea un nuevo nodo: crea un nuevo objeto Node, guardando el value recibido dentro de él.

2. Maneja una lista vacía: Si la lista está vacía actualmente (self.length == 0), pone tanto head como tail apuntando al nodo recién creado. Esto establece el primer y único elemento de la lista.

3. Añade al inicio de una lista no vacía:

• Si la lista ya tiene nodos:

• Pone el puntero prev del nodo head actual apuntando al nuevo nodo. Esto crea una conexión entre el nuevo nodo y el que antes era el primer nodo.

• Pone el puntero next del nuevo nodo apuntando al nodo head actual. Esto establece al nuevo nodo como el primero de la lista.

• Actualiza el head de la lista para que apunte al nodo recién añadido, reflejando el nuevo inicio.

1. Incrementa el length: aumenta el atributo length para reflejar el nuevo nodo añadido.

Código

class DoublyLinkedList:

    #   previous code

    """
        This method adds a new node containing a specified value to the beginning (front) of a doubly linked list

        Args
            Value: the data that will contain the new node
        Return
            bool
        """
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node
        self.length += 1
        return True

Las canciones del post

Hace poco vi una película llamada Anatomy of a fall (y es una película muy buena, la recomiendo 100 por ciento), y en los primeros minutos de la película sonaba esta canción:

PIMP

· PIMP, Bacao Rhythm & Steel Band

Fue amor a primera escuchada 👂💘.

Obviamente es un cover de P.I.M.P de 50 Cent.

Así que decidí escuchar más de esta banda y me gustó mucho su vibra tropical, te la recomiendo si tienes la oportunidad de escucharla. Mi canción favorita es:

Bacao Suave

· Bacao Suave, Bacao Rhythm & Steel Band