En este post te mostraré una lista ligada en Python que después se podría modificar como una cola o pila (ya que se pueden insertar elementos al inicio y al final).

Las operaciones que manejaremos con esta lista enlazada son:

• Agregar al inicio
• Agregar al final
• Saber si elemento existe
• Eliminar un elemento
• Obtener cabeza
• Obtener cola
• Recorrer lista

Por cierto, vamos a usar ciclos y no recursión para las operaciones. De esta manera el código queda más simple.

El nodo de la lista

La lista se compone de nodos o elementos que van enlazados entre sí. Cada nodo tiene dos cosas: el dato que guarda y un apuntador al nodo siguiente, del mismo tipo.

Python es un lenguaje bonito (no como C en donde tienes que solicitar memoria hasta para respirar) así que podemos guardar cualquier tipo de dato en los nodos, no importa si son cadenas, listas, objetos, números, etcétera.

class Nodo():
    dato = None
    siguiente = None

    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None

Digamos que el dato será de tipo genérico.

Agregar elemento al final

Veamos cómo agregar un nodo al final de la lista enlazada usando Python. Lo que hacemos es recorrer la lista hasta el final y asignarlo ahí:

def agregar_al_final(nodo_inicial, dato):
    nuevo_nodo = Nodo(dato)
    if nodo_inicial == None:
        nodo_inicial = nuevo_nodo
        return nodo_inicial
    temporal = nodo_inicial
    while temporal.siguiente:
        temporal = temporal.siguiente
    temporal.siguiente = nuevo_nodo
    return nodo_inicial

Por cierto, si el nodo es None (eso sería cuando la lista está vacía) entonces el nuevo nodo será la cabeza de la lista (ya que sería el primero en la lista).

Añadir elemento al inicio de la lista enlazada

Ahora veamos la operación de agregar un elemento a la lista pero al inicio. En este caso solo debemos crear un nuevo nodo (que será la nueva cabeza o nuevo inicio) y hacer que su siguiente sea el que antes era el inicio:

def agregar_al_inicio(nodo_inicial, dato):
    nuevo_nodo = Nodo(dato)
    nuevo_nodo.siguiente = nodo_inicial
    return nuevo_nodo

Ten en cuenta que en ambas funciones que agregan un nodo a la lista (estructura de datos) de Python regresan un nodo que será el apuntador al inicio o cabeza de la lista.

Obtener inicio y final de cola/pila

Otra operación interesante con esta lista ligada de Python es la de obtener la cabeza o inicio, y el final o la cola. En este caso solo recorremos y regresamos el nodo.

def obtener_cabeza(nodo_inicial):
    return nodo_inicial


def obtener_cola(nodo_inicial):
    temporal = nodo_inicial
    while temporal.siguiente:
        temporal = temporal.siguiente
    return temporal

Obviamente para el caso de la cabeza simplemente regresamos el nodo que nos envían como argumento, ya que es el inicio de la lista.

Saber si elemento existe

Para saber si un elemento existe dentro de la lista enlazada que estamos creando basta recorrer toda la lista y comparar el dato de cada nodo con la búsqueda.

Si encontramos un dato de un nodo que coincida con la búsqueda entonces regresamos True.

def existe(nodo, busqueda):
    while nodo != None:
        if nodo.dato == busqueda:
            return True
        nodo = nodo.siguiente
    return False

En caso de terminar de recorrer la lista y no haber encontrado nada, regresamos False.

Nota: esto puede funcionar con objetos de cualquier tipo (incluso instancias de tus propias clases), solo debes implementar el método __eq__.

Eliminar elemento de lista enlazada con Python

Ahora veamos la operación en donde eliminamos un elemento. En este caso lo que hago es ir comparando el siguiente nodo del nodo actual, ya que no puedo ir hacia atrás en caso de que el elemento actual sea el que quiero eliminar.

Lo que hago cuando encuentro el elemento a eliminar es hacer que su elemento anterior apunte a su elemento siguiente.

def eliminar(nodo, busqueda):
    if nodo == None:
        return
    if nodo.dato == busqueda:
        return nodo.siguiente
    temporal = nodo
    while temporal.siguiente != None:
        if temporal.siguiente.dato == busqueda:
            if temporal.siguiente.siguiente != None:
                temporal.siguiente = temporal.siguiente.siguiente
            else:
                temporal.siguiente = None
                return nodo
        temporal = temporal.siguiente
    return nodo

Nota: igual y se podría hacer algo con el operador del de Python (así como lo hicimos en C++), pero supongo que el recolector de basura se encarga de liberar la memoria porque ya nadie tiene una referencia a ese nodo.

Poniendo todo junto

A continuación muestro un ejemplo en donde usamos las funciones expuestas y trabajamos con la lista enlazada.

Ten en cuenta que en este caso he usado cadenas pero puede usarse cualquier tipo de dato e incluso objetos.

class Nodo():
    dato = None
    siguiente = None

    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None


def agregar_al_final(nodo_inicial, dato):
    nuevo_nodo = Nodo(dato)
    if nodo_inicial == None:
        nodo_inicial = nuevo_nodo
        return nodo_inicial
    temporal = nodo_inicial
    while temporal.siguiente:
        temporal = temporal.siguiente
    temporal.siguiente = nuevo_nodo
    return nodo_inicial


def agregar_al_inicio(nodo_inicial, dato):
    nuevo_nodo = Nodo(dato)
    nuevo_nodo.siguiente = nodo_inicial
    return nuevo_nodo


def imprimir_lista(nodo):
    while nodo != None:
        print(f"Tenemos {nodo.dato}")
        nodo = nodo.siguiente


def obtener_cabeza(nodo_inicial):
    return nodo_inicial


def obtener_cola(nodo_inicial):
    temporal = nodo_inicial
    while temporal.siguiente:
        temporal = temporal.siguiente
    return temporal


def existe(nodo, busqueda):
    while nodo != None:
        if nodo.dato == busqueda:
            return True
        nodo = nodo.siguiente
    return False


def eliminar(nodo, busqueda):
    if nodo == None:
        return
    if nodo.dato == busqueda:
        return nodo.siguiente
    temporal = nodo
    while temporal.siguiente != None:
        if temporal.siguiente.dato == busqueda:
            if temporal.siguiente.siguiente != None:
                temporal.siguiente = temporal.siguiente.siguiente
            else:
                temporal.siguiente = None
                return nodo
        temporal = temporal.siguiente
    return nodo


def main():
    lista = None
    lista = agregar_al_final(lista, "Luis")
    lista = agregar_al_final(lista, "Leon")
    lista = agregar_al_inicio(lista, "Link")
    print("Antes de eliminar: ")
    imprimir_lista(lista)  # Link, Luis, Leon
    lista = eliminar(lista, "Link")
    print("Después de eliminar: ")
    imprimir_lista(lista)  # Luis, Leon
    print(existe(lista, "Link"))  # False
    print(existe(lista, "Luis"))  # True
    # obtener_cabeza nos regresa el nodo, pero accedemos al dato para imprimirlo
    print(obtener_cabeza(lista).dato)  # Luis
    print(obtener_cola(lista).dato)  # Leon


main()

Por cierto, he dejado todas las funciones globales y sin pertenecer a una clase en común.

Esto es porque he hecho el ejemplo rápidamente y no pensé en hacerlo una clase desde un inicio. Incluso así, sería muy fácil agruparlo en una clase por ti mismo.

Para terminar te dejo con más tutoriales de Python y Estructura de datos en mi blog.

Bonus

Mientras grababa el vídeo explicativo hice un ejemplo con una clase para demostrar que se pueden usar objetos como datos de los nodos. Aquí el código:

class Nodo():
    dato = None
    siguiente = None

    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None


def agregar_al_final(nodo_inicial, dato):
    nuevo_nodo = Nodo(dato)
    if nodo_inicial == None:
        nodo_inicial = nuevo_nodo
        return nodo_inicial
    temporal = nodo_inicial
    while temporal.siguiente:
        temporal = temporal.siguiente
    temporal.siguiente = nuevo_nodo
    return nodo_inicial


def agregar_al_inicio(nodo_inicial, dato):
    nuevo_nodo = Nodo(dato)
    nuevo_nodo.siguiente = nodo_inicial
    return nuevo_nodo


def imprimir_lista(nodo):
    while nodo != None:
        print(f"Tenemos {nodo.dato}")
        nodo = nodo.siguiente


def obtener_cabeza(nodo_inicial):
    return nodo_inicial


def obtener_cola(nodo_inicial):
    temporal = nodo_inicial
    while temporal.siguiente:
        temporal = temporal.siguiente
    return temporal


def existe(nodo, busqueda):
    while nodo != None:
        if nodo.dato == busqueda:
            return True
        nodo = nodo.siguiente
    return False


def eliminar(nodo, busqueda):
    if nodo == None:
        return
    if nodo.dato == busqueda:
        return nodo.siguiente
    temporal = nodo
    while temporal.siguiente != None:
        if temporal.siguiente.dato == busqueda:
            if temporal.siguiente.siguiente != None:
                temporal.siguiente = temporal.siguiente.siguiente
            else:
                temporal.siguiente = None
                return nodo
        temporal = temporal.siguiente
    return nodo


class Mascota():
    def __init__(self, nombre) -> None:
        self.nombre = nombre

    def __str__(self) -> str:
        return f"Mascota llamada {self.nombre}"

    def __eq__(self, __o: object) -> bool:
        return self.nombre == __o.nombre


def main():
    lista = None
    lista = agregar_al_final(lista, Mascota("Maggie"))
    lista = agregar_al_final(lista, Mascota("Grimm"))
    lista = agregar_al_inicio(lista, Mascota("Panqué"))
    lista = agregar_al_inicio(lista, Mascota("Ejemplo"))
    print("Antes de eliminar: ")
    imprimir_lista(lista)
    lista = eliminar(lista, Mascota("Ejemplo"))
    print("Después de eliminar: ")
    imprimir_lista(lista)  # Luis, Leon
    print(existe(lista, Mascota("Grimm")))  # False
    print(existe(lista, Mascota("Ejemplo")))  # False
    # obtener_cabeza nos regresa el nodo, pero accedemos al dato para imprimirlo
    print(obtener_cabeza(lista).dato)  # Luis
    print(obtener_cola(lista).dato)  # Leon


main()