Lista Enlazada

Lista Enlazada

Una lista enlazada es una estructura de datos lineal en la que cada elemento no se guarda en una posición contigua de memoria, es decir, cada elemento puede vivir en cualquier dirección de memoria.

La forma en que una lista enlazada guarda información es en nodos. Una lista enlazada forma una serie de nodos conectados, donde cada nodo guarda el dato y la dirección del siguiente nodo.

Ahora que ya tenemos una idea básica de qué es una LL (lista enlazada), ¿por qué la usamos? Usamos listas enlazadas en casi todas las apps o programas. Por ejemplo, en el carrusel de fotos del teléfono se muestran todas las fotos que hemos tomado. Sabemos que no todas las fotos se toman el mismo día, así que el teléfono guarda la foto (el dato) y crea un puntero que hace referencia a la siguiente foto tomada. Este proceso se llama asignación dinámica de almacenamiento.

Ventajas de las listas enlazadas

• Tamaño dinámico: las listas enlazadas pueden crecer o reducirse dinámicamente, ya que la memoria se asigna en tiempo de ejecución.

• Inserción y eliminación: añadir o quitar elementos de una lista enlazada es eficiente, sobre todo en listas grandes.

• Flexibilidad: las listas enlazadas se pueden reorganizar y modificar fácilmente sin necesitar un bloque contiguo de memoria.

Desventajas de las listas enlazadas

• Acceso aleatorio: las listas enlazadas no permiten acceder directamente a un elemento por índice. Hay que recorrerlas para llegar a un nodo específico.

• Memoria extra: las listas enlazadas necesitan memoria adicional para guardar los punteros, en comparación con los arreglos.

Estructura del nodo

Mencioné el nodo antes, pero no explique bien qué es, así que, resumiendo, podemos decir que un nodo es la suma de dos componentes: Data: guarda el valor real asociado al nodo. Next Pointer: la dirección de memoria (referencia) del siguiente nodo en la secuencia.

Código

Bueno, ya escribí bastante, así que ahora metámonos de lleno en la sección de código.

Constructor del nodo

Antes de crear una lista enlazada hace falta crear un Node, así que creamos una clase llamada Node. Esta clase es muy simple, con un solo método (el constructor de la clase) que guarda solo dos cosas: el valor (data) y next (la referencia al siguiente puntero).

class Node:
    """
    Node class

    Define every item on the linked list

    Attributes:
        value:  The item of the list in that node
        Next:   The next hope to the element to the linked list
    """
    def __init__(self, value) -> None:
        """
        Constructore of the node
        """
        self.value = value
        # The pointer
        self.next = None

Constructor de la lista enlazada

Perfecto, ya creamos el constructor de Node, que es la base de esta clase. Ahora necesitamos crear la clase de la lista enlazada. Pero antes de escribir su constructor, se me olvidó mencionar dos elementos importantes de una lista enlazada. El primero es el head, que hace referencia al primer elemento de la lista, y el otro es el tail, que es el último elemento.

class LinkedList:
    """
    Linked List class

    Define a general class of linked list,
    with basic operation over the LL

    Attributes:
        lenght: The number of nodes in the LL
        head:   The first node of the LL, could be Null
        tail:   The last node of the LL, could be Null
    """
    def __init__(self, value) -> None:
        """
        Constructore of the LL
        """
        new_node    = Node(value = value)
        self.head   = new_node
        self.tail   = new_node
        self.length = 1

Ya completamos el constructor de la lista enlazada, y ahora nuestra lista contiene un solo elemento. En un próximo post escribiré sobre las operaciones que podemos implementar en la clase, como el método append o el método pop.

La canción del post

Going Kokomo
Our life’s a beach so let’s let go
Don’t stress yourself
Might even play this on the radio
· Going Kokomo, Royel Otis