Hoy te enseñaré cómo implementar una lista ligada en el lenguaje de programación C++ también conocido como CPP.

Además de mostrarte la clase Lista y la clase Nodo, te enseñaré las operaciones que podemos realizar con ella. Son las siguientes:

• Recorrer la lista imprimiendo los valores
• Verificar si un elemento existe dentro de la lista
• Eliminar un elemento de la lista ligada en C++
• Crear una nueva lista sin elementos repetidos (eliminar duplicados)

Todo esto usando C++ e implementando los métodos y algoritmos manualmente. Por cierto, en este caso el tipo de dato que vamos a almacenar será un int pero fácilmente puedes cambiarlo a cualquier otro tipo de dato.

El Nodo

La lista se compone de nodos que van ligados entre sí. Cada nodo tiene un dato que puede ser un entero, doble, cadena o incluso un objeto, pero además tiene un apuntador al siguiente nodo.

class Nodo
{
public:
    int dato;
    Nodo *siguiente;
    Nodo(int dato)
    {
        this->dato = dato;
        this->siguiente = NULL;
    }
};

Por defecto el siguiente nodo apunta a NULL. Ya cuando se agregue un nodo, el siguiente del primero apuntará al nuevo y así.

El nodo que está al final de la lista no apuntará a nada, y el primer nodo que se agrega es la cabeza o el nodo head. Todo esto lo vamos a manejar desde la clase Lista.

La lista en C++

Ahora veamos la lista que va a manejar los nodos. Tiene varios métodos y si te fijas, algunos se repiten pero es porque algunos métodos son para ser llamados desde el exterior y otros desde el interior.

Esto es debido a que se debe usar la recursividad para solucionar ciertas operaciones, pero para ahorrarle al invocador implementar todo esto, definimos métodos públicos sencillos.

La verdadera implementación, por lo tanto, estará en los métodos privados.

class Lista
{

private:
    void agregarRecursivo(Nodo *n, int dato)
    {
        if (n->siguiente == NULL)
        {
            n->siguiente = new Nodo(dato);
        }
        else
        {
            this->agregarRecursivo(n->siguiente, dato);
        }
    }

    void imprimirRecursivo(Nodo *n)
    {
        if (n != NULL)
        {
            std::cout << "Tenemos " << n->dato << std::endl;
            this->imprimirRecursivo(n->siguiente);
        }
    }

    void eliminarRecursivo(Nodo *n, int dato)
    {
        if (n == NULL)
        {
            return;
        }
        if (n->dato == dato && n == this->cabeza)
        {
            Nodo *temporal = this->cabeza;
            if (this->cabeza->siguiente != NULL)
            {
                this->cabeza = this->cabeza->siguiente;
                delete temporal;
            }
            else
            {
                this->cabeza = NULL;
            }
            return;
        }
        if (n->siguiente != NULL && n->siguiente->dato == dato)
        {
            Nodo *temporal = n->siguiente;
            if (n->siguiente != NULL)
            {
                n->siguiente = n->siguiente->siguiente;
            }
            delete temporal;
        }
        else
        {
            this->eliminarRecursivo(n->siguiente, dato);
        }
    }
    bool existeRecursivo(Nodo *n, int dato)
    {
        if (n == NULL)
        {
            return false;
        }
        if (n->dato == dato)
        {
            return true;
        }
        return this->existeRecursivo(n->siguiente, dato);
    }

public:
    Nodo *cabeza;
    void copiaSinDuplicados(Lista *l)
    {
        Nodo *temporal = this->cabeza;
        while (temporal != NULL)
        {
            if (!l->existe(temporal->dato))
            {
                l->agregar(temporal->dato);
            }
            temporal = temporal->siguiente;
        }
    }
    void eliminar(int dato)
    {
        this->eliminarRecursivo(this->cabeza, dato);
    }
    void agregar(int dato)
    {
        if (this->cabeza == NULL)
        {
            this->cabeza = new Nodo(dato);
        }
        else
        {
            this->agregarRecursivo(this->cabeza, dato);
        }
    }

    void imprimir()
    {
        std::cout << "Imprimiendo " << std::endl;
        this->imprimirRecursivo(this->cabeza);
    }
    bool existe(int dato)
    {
        return this->existeRecursivo(this->cabeza, dato);
    }
};

Si me lo preguntas, el método más interesante a mi parecer es el de eliminar un valor, pues no lo había implementado antes.

Lo que se hace es que ahora el nodo actual (número 1) apunta al tercero, y deja de apuntar al segundo. Luego eliminamos la referencia al segundo para que no haya problemas de gestión de memoria.

Por cierto, ahora que lo noto, solo va a eliminar el primer elemento que encuentre, y si hay duplicados entonces va a dejarlos intactos.

Se me ocurre que se puede combinar el método existe con el de eliminar para que se elimine mientras siga existiendo un elemento en la lista.

Modo de uso

Ya te mostré cómo implementar una lista y un nodo en C++ para el manejo de listas ligadas, ahora te enseñaré un poco sobre cómo usarlas. Obviamente puedes llenar la lista desde la consola, un archivo de texto, base de datos, etcétera.

int main()
{
    Lista *l = new Lista();
    l->agregar(1);
    l->eliminar(1);
    l->agregar(2);
    l->agregar(3);
    l->agregar(4);
    l->agregar(5);
    l->imprimir();
    l->eliminar(3);
    l->imprimir();
    l->agregar(3);
    l->eliminar(1);
    l->eliminar(2);
    l->eliminar(3);
    l->eliminar(4);
    l->eliminar(5);
    l->imprimir();
    l->agregar(123);
    l->agregar(123);
    l->agregar(123);
    l->agregar(123);
    l->agregar(88);
    l->agregar(123);
    l->agregar(123);
    l->agregar(88);
    l->agregar(123);
    l->agregar(88);
    l->agregar(60);
    l->imprimir();
    Lista *sinDuplicados = new Lista();
    l->copiaSinDuplicados(sinDuplicados);
    sinDuplicados->imprimir();
}

Si ves varias llamadas a agregar, eliminar e imprimir es porque estoy probando todos los métodos. La salida es correcta como se aprecia en la siguiente imagen:

Finalmente te dejo con un enlace en donde puedes aprender más de programación en C++.