Introducción a Listas Enlazadas

La analogía: un tren

Imagina un tren. Cada vagón tiene dos cosas: la carga (datos) y un enganche al siguiente vagón (puntero). Para llegar al tercer vagón, debes pasar por el primero y el segundo. No puedes saltar directo como en un arreglo. Eso es una lista enlazada.

¿Por qué no usar siempre arreglos?

Las listas enlazadas brillan cuando necesitas insertar o borrar elementos frecuentemente en posiciones arbitrarias.

Estructura de un nodo

struct Nodo {
    int dato;       // La información que almacena
    Nodo* siguiente; // Puntero al siguiente nodo

    Nodo(int d) : dato(d), siguiente(nullptr) {}
};

Visualización:

[dato|sig] → [dato|sig] → [dato|sig] → nullptr
  10   →      20   →      30   →    ∅

Construir una lista paso a paso

#include <iostream>
using namespace std;

struct Nodo {
    int dato;
    Nodo* siguiente;
    Nodo(int d) : dato(d), siguiente(nullptr) {}
};

int main() {
    // Crear nodos
    Nodo* cabeza = new Nodo(10);
    Nodo* segundo = new Nodo(20);
    Nodo* tercero = new Nodo(30);

    // Conectarlos
    cabeza->siguiente = segundo;
    segundo->siguiente = tercero;
    // tercero->siguiente ya es nullptr

    // Recorrer la lista
    Nodo* actual = cabeza;
    while (actual != nullptr) {
        cout << actual->dato << " → ";
        actual = actual->siguiente;
    }
    cout << "nullptr" << endl;
    // 10 → 20 → 30 → nullptr

    // Liberar memoria
    delete cabeza;
    delete segundo;
    delete tercero;

    return 0;
}

Operaciones básicas

Insertar al inicio

void insertarInicio(Nodo* &cabeza, int valor) {
    Nodo* nuevo = new Nodo(valor);
    nuevo->siguiente = cabeza;
    cabeza = nuevo;
}

¿Por qué Nodo* &cabeza? Porque necesitamos modificar el puntero cabeza, no solo su copia.

Insertar al final

void insertarFinal(Nodo* &cabeza, int valor) {
    Nodo* nuevo = new Nodo(valor);

    if (cabeza == nullptr) {
        cabeza = nuevo;
        return;
    }

    Nodo* actual = cabeza;
    while (actual->siguiente != nullptr) {
        actual = actual->siguiente;
    }
    actual->siguiente = nuevo;
}

Borrar un nodo con valor dado

void borrar(Nodo* &cabeza, int valor) {
    if (cabeza == nullptr) return;

    // Caso especial: borrar la cabeza
    if (cabeza->dato == valor) {
        Nodo* temp = cabeza;
        cabeza = cabeza->siguiente;
        delete temp;
        return;
    }

    Nodo* actual = cabeza;
    while (actual->siguiente != nullptr && actual->siguiente->dato != valor) {
        actual = actual->siguiente;
    }

    if (actual->siguiente != nullptr) {
        Nodo* temp = actual->siguiente;
        actual->siguiente = temp->siguiente;
        delete temp;
    }
}

Buscar un elemento

bool buscar(Nodo* cabeza, int valor) {
    Nodo* actual = cabeza;
    while (actual != nullptr) {
        if (actual->dato == valor) return true;
        actual = actual->siguiente;
    }
    return false;
}

Contar elementos

int longitud(Nodo* cabeza) {
    int cont = 0;
    Nodo* actual = cabeza;
    while (actual != nullptr) {
        cont++;
        actual = actual->siguiente;
    }
    return cont;
}

Lista doblemente enlazada

Cada nodo tiene puntero al siguiente y al anterior:

struct NodoDoble {
    int dato;
    NodoDoble* anterior;
    NodoDoble* siguiente;

    NodoDoble(int d) : dato(d), anterior(nullptr), siguiente(nullptr) {}
};

nullptr ← [ant|dato|sig] ⇄ [ant|dato|sig] ⇄ [ant|dato|sig] → nullptr
              10                20                30

Ventaja: puedes recorrer en ambas direcciones y borrar un nodo en $O(1)$ si tienes su puntero.

En la práctica: std::list

C++ tiene std::list, una lista doblemente enlazada ya implementada:

#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> lista = {10, 20, 30, 40};

    lista.push_front(5);    // Insertar al inicio
    lista.push_back(50);    // Insertar al final

    // Insertar en medio
    auto it = lista.begin();
    advance(it, 3);  // Avanzar al 4to elemento
    lista.insert(it, 25);

    for (int x : lista) cout << x << " ";
    // 5 10 20 25 30 40 50
    cout << endl;

    lista.pop_front();  // Borrar primero
    lista.pop_back();   // Borrar último

    cout << "Tamaño: " << lista.size() << endl;

    return 0;
}

Ejercicio de práctica

Implementa una lista enlazada que soporte:

1. Insertar un número al final
2. Borrar la primera aparición de un número
3. Imprimir todos los elementos

#include <iostream>
using namespace std;

struct Nodo {
    int dato;
    Nodo* sig;
    Nodo(int d) : dato(d), sig(nullptr) {}
};

Nodo* cabeza = nullptr;

void insertar(int val) {
    Nodo* nuevo = new Nodo(val);
    if (!cabeza) { cabeza = nuevo; return; }
    Nodo* act = cabeza;
    while (act->sig) act = act->sig;
    act->sig = nuevo;
}

void borrar(int val) {
    if (!cabeza) return;
    if (cabeza->dato == val) {
        Nodo* temp = cabeza;
        cabeza = cabeza->sig;
        delete temp;
        return;
    }
    Nodo* act = cabeza;
    while (act->sig && act->sig->dato != val) act = act->sig;
    if (act->sig) {
        Nodo* temp = act->sig;
        act->sig = temp->sig;
        delete temp;
    }
}

void imprimir() {
    Nodo* act = cabeza;
    while (act) {
        cout << act->dato;
        if (act->sig) cout << " -> ";
        act = act->sig;
    }
    cout << " -> nullptr" << endl;
}

int main() {
    insertar(10);
    insertar(20);
    insertar(30);
    imprimir();        // 10 -> 20 -> 30 -> nullptr

    borrar(20);
    imprimir();        // 10 -> 30 -> nullptr

    insertar(40);
    imprimir();        // 10 -> 30 -> 40 -> nullptr

    return 0;
}

Siguiente paso

Aprende a invertir una lista enlazada, uno de los problemas clásicos más importantes en entrevistas y competencias.