Una lista enlazada en C: insertar, borrar, invertir y liberar

Una lista enlazada simple en C, completa y comprobada con AddressSanitizer: insertar al principio y en orden, borrar un elemento, invertir la lista y liberarla sin fugas. Con el truco del puntero a puntero que evita los casos especiales y una comparación honesta con los arrays.

Una lista enlazada guarda cada elemento en un bloque de memoria aparte, un nodo, que además del valor tiene un puntero al nodo siguiente. Es la estructura de datos clásica para practicar punteros y memoria dinámica, y la base de otras, como las listas de las tablas hash.

El programa completo

#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
    int valor;
    struct Nodo *siguiente;
} Nodo;

/* Añade al principio. Recibe la dirección de la cabeza porque puede cambiarla. */
bool insertar_inicio(Nodo **cabeza, int valor)
{
    Nodo *n = malloc(sizeof *n);
    if (n == nullptr) return false;
    n->valor = valor;
    n->siguiente = *cabeza;
    *cabeza = n;
    return true;
}

/* Inserta manteniendo el orden ascendente. */
bool insertar_ordenado(Nodo **cabeza, int valor)
{
    Nodo **p = cabeza;
    while (*p != nullptr && (*p)->valor < valor) {
        p = &(*p)->siguiente;
    }
    return insertar_inicio(p, valor);
}

/* Borra el primer nodo con ese valor. Devuelve si lo encontró. */
bool borrar(Nodo **cabeza, int valor)
{
    for (Nodo **p = cabeza; *p != nullptr; p = &(*p)->siguiente) {
        if ((*p)->valor == valor) {
            Nodo *quitar = *p;
            *p = quitar->siguiente;
            free(quitar);
            return true;
        }
    }
    return false;
}

void invertir(Nodo **cabeza)
{
    Nodo *anterior = nullptr, *actual = *cabeza;
    while (actual != nullptr) {
        Nodo *siguiente = actual->siguiente;
        actual->siguiente = anterior;
        anterior = actual;
        actual = siguiente;
    }
    *cabeza = anterior;
}

void imprimir(const Nodo *n)
{
    for (; n != nullptr; n = n->siguiente) printf("%d -> ", n->valor);
    printf("NULL\n");
}

void liberar(Nodo **cabeza)
{
    Nodo *n = *cabeza;
    while (n != nullptr) {
        Nodo *siguiente = n->siguiente;
        free(n);
        n = siguiente;
    }
    *cabeza = nullptr;
}

int main(void)
{
    Nodo *lista = nullptr;
    int datos[] = {30, 10, 40, 20};
    for (int i = 0; i < 4; i++) {
        if (!insertar_ordenado(&lista, datos[i])) return EXIT_FAILURE;
    }
    imprimir(lista);

    borrar(&lista, 30);
    printf("¿Borrado el 99? %s\n", borrar(&lista, 99) ? "sí" : "no");
    imprimir(lista);

    invertir(&lista);
    imprimir(lista);

    liberar(&lista);
    imprimir(lista);
    return 0;
}

salida10 -> 20 -> 30 -> 40 -> NULL
¿Borrado el 99? no
10 -> 20 -> 40 -> NULL
40 -> 20 -> 10 -> NULL
NULL

Se compiló con AddressSanitizer y UBSan: ningún acceso indebido y ninguna fuga, porque liberar devuelve todos los nodos.

Las claves

• Las funciones que pueden cambiar la cabeza reciben Nodo **, la dirección del puntero, no el puntero. Si insertar_inicio recibiera Nodo *cabeza, cambiaría su copia local y la lista de main no se enteraría.
• El puntero a puntero evita los casos especiales. En insertar_ordenado y borrar, p apunta al «enlace» que hay que cambiar, sea la propia cabeza o el campo siguiente de un nodo. Sin él, hay que tratar aparte el primer nodo, y ahí suelen estar los errores. Linus Torvalds lo puso como ejemplo de «buen gusto» al programar.
• Guarda siguiente antes de liberar. En liberar, leer n->siguiente después de free(n) sería un uso tras liberar.
• invertir no reserva nada: le da la vuelta a cada puntero con tres variables. Es una pregunta típica de entrevista.

¿Cuándo usar una lista enlazada?

Menos de lo que dicen los libros. Insertar o borrar en medio es barato si ya tienes el nodo, pero llegar a él exige recorrer la lista, y los nodos dispersos por la memoria aprovechan mal la caché del procesador. Un array que crece (como el Vector de la lección 6) suele ser más rápido incluso para insertar, salvo en listas enormes. Las listas enlazadas brillan cuando los elementos ya existen por otro motivo y solo hay que encadenarlos: colas de procesos en un sistema operativo, listas de colisiones en una tabla hash o listas de bloques libres en un gestor de memoria.

• OperaciónLista enlazadaArray que crece
• Acceder al elemento nrecorrer n nodosinmediato: v[n]
• Añadir al principioinmediatomover todos los elementos
• Añadir al finalrecorrer, salvo que guardes la colainmediato casi siempre
• Borrar un nodo que ya tienesinmediatomover los de detrás
• Memoria extraun puntero por elementola capacidad sin usar

Todo el código de esta página se compiló con GCC 15.3 (C23, -Wall -Wextra, sin avisos) y se ejecutó en Linux, en un contenedor limpio sin acceso a la red, antes de publicarla; las salidas están copiadas de esa ejecución.