Listas enlazadas en C++: entendiendo la estructura sin morir en el intento

Resumen: En este post te explico qué es una lista enlazada en C++, por qué existe si ya hay arrays, y cómo implementar una lista enlazada simple paso a paso con ejemplos de código.

Nivel: Junior

Introducción

Si estás empezando con C++ o estructuras de datos, probablemente ya te preguntaste:
“Si tengo arrays y std::vector, ¿para qué quiero una lista enlazada?”.
Buena pregunta.

Las listas enlazadas son una estructura de datos clásica que aparece en entrevistas, exámenes y, sobre todo,
te obliga a entender mejor cómo funcionan los punteros y la memoria dinámica en C++.
En este post vamos a ver:

• Qué es una lista enlazada y cómo se diferencia de un array.
• Cuándo tiene sentido usarla (y cuándo es mejor no complicarse).
• Una implementación básica en C++ con las operaciones típicas.
• Errores comunes que comete todo el mundo la primera vez (yo incluido).

¿Qué es una lista enlazada?

Una lista enlazada (singly linked list) es una colección de nodos donde:

• Cada nodo guarda un valor.
• Cada nodo sabe quién es el siguiente nodo (puntero next).
• La lista solo conoce el primer nodo, llamado head.

Visualmente, algo así:

[valor1 | *] → [valor2 | *] → [valor3 | *] → nullptr

A diferencia de un array:

• Los elementos no están uno al lado del otro en memoria.
• Para acceder al elemento N, tienes que recorrer desde el inicio.
• Agregar o eliminar elementos al inicio puede ser muy barato (O(1)).

¿Cuándo usar listas enlazadas y cuándo no?

Te conviene usar una lista enlazada cuando:

• Necesitas hacer muchas inserciones y eliminaciones al inicio de la colección.
• No te importa tanto el acceso “dame el índice 10” rápido.
• Estás aprendiendo estructuras de datos y quieres entender bien punteros y memoria dinámica.

No es la mejor idea cuando:

• Vas a acceder constantemente por índice (tipo v[100000]).
• Tu caso de uso es básicamente una lista que solo crece y rara vez eliminas en medio.
• Ya puedes usar std::vector o std::list de la STL sin reinventar la rueda.

En la práctica, en C++ del mundo real, normalmente usarás std::vector y compañía.
Pero entender listas enlazadas te hace mucho mejor programador.

Implementación básica de una lista enlazada en C++

Vamos con una implementación simple de una lista enlazada de enteros.

Definiendo el nodo

#include <iostream>

struct Node {
    int data;      // valor que guarda el nodo
    Node* next;    // puntero al siguiente nodo

    // Constructor cómodo
    Node(int value) : data(value), next(nullptr) {}
};

Manejando la lista

Podemos manejar la lista con un puntero head que apunte al primer nodo:

struct LinkedList {
    Node* head;

    LinkedList() : head(nullptr) {}

    // Insertar al inicio
    void push_front(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Mostrar todos los elementos
    void print() const {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // Liberar memoria (destructor)
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }
};

Usando la lista en main

int main() {
    LinkedList list;

    list.push_front(10);
    list.push_front(20);
    list.push_front(30);

    list.print(); // 30 -> 20 -> 10 -> nullptr

    return 0;
}

Aquí estamos insertando siempre al inicio, así que el orden queda invertido:
el último que insertas es el primero de la lista.

Operaciones típicas en una lista enlazada

Insertar al final

Insertar al final requiere recorrer la lista hasta llegar al último nodo.

void push_back(int value) {
    Node* newNode = new Node(value);

    if (head == nullptr) {
        head = newNode;
        return;
    }

    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

Eliminar el primer nodo con un cierto valor

bool remove(int value) {
    if (head == nullptr) return false;

    // Si el que hay que borrar es el primero
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return true;
    }

    Node* current = head;
    while (current->next != nullptr && current->next->data != value) {
        current = current->next;
    }

    if (current->next == nullptr) {
        // No se encontró el valor
        return false;
    }

    Node* nodeToDelete = current->next;
    current->next = current->next->next;
    delete nodeToDelete;
    return true;
}

Buscar un valor

bool contains(int value) const {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

Ejemplo completo

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

struct LinkedList {
    Node* head;

    LinkedList() : head(nullptr) {}

    void push_front(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    void push_back(int value) {
        Node* newNode = new Node(value);

        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }

    bool remove(int value) {
        if (head == nullptr) return false;

        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return true;
        }

        Node* current = head;
        while (current->next != nullptr && current->next->data != value) {
            current = current->next;
        }

        if (current->next == nullptr) {
            return false;
        }

        Node* nodeToDelete = current->next;
        current->next = current->next->next;
        delete nodeToDelete;
        return true;
    }

    bool contains(int value) const {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                return true;
            }
            current = current->next;
        }
        return false;
    }

    void print() const {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }
};

int main() {
    LinkedList list;

    list.push_front(10);
    list.push_front(20);
    list.push_back(5);

    list.print(); // 20 -> 10 -> 5 -> nullptr

    list.remove(10);
    list.print(); // 20 -> 5 -> nullptr

    std::cout << "Contiene 5? " << (list.contains(5) ? "sí" : "no") << std::endl;
    std::cout << "Contiene 42? " << (list.contains(42) ? "sí" : "no") << std::endl;

    return 0;
}

Errores típicos con listas enlazadas (y cómo evitarlos)

• Olvidar inicializar punteros: deja siempre next como nullptr en el constructor.
• Acceder a current->next sin comprobar current != nullptr:
  esto es receta segura para un segmentation fault.
• Fugas de memoria: cada new necesita un delete.
  Por eso el destructor que recorre y libera la lista es tan importante.
• Perder la referencia a la lista: si reasignas head sin guardar el nodo anterior,
  te quedas sin acceso al resto de nodos.

Conclusión

Las listas enlazadas son una de esas estructuras que, al principio, parecen más complicadas de lo que “valen”.
Pero una vez las entiendes, te abren la puerta a muchas otras estructuras más avanzadas
(listas dobles, colas, pilas, árboles, grafos…).

En C++ moderno, en la mayoría de casos reales usarás contenedores de la STL
como std::vector o std::list.
Aún así, implementar tu propia lista enlazada te obliga a entender punteros, memoria dinámica y destructores,
lo cual es oro puro si quieres crecer como desarrollador C++.

Si te gustaría, en otro post podemos ver:

• Listas doblemente enlazadas.
• Implementar una pila o una cola usando una lista enlazada.
• La misma estructura pero usando templates para soportar cualquier tipo, no solo int.

Recursos recomendados

• Búsqueda en Google de “singly linked list C++” con imágenes: ayuda un montón a visualizar.
• Documentación de std::list en C++ para ver cómo lo hace la STL.