Una lista que crece

Añadir por delante es lo barato: nada se mueve.

1Por qué

Encadenar tres nodos a mano sirve para verlo, pero nadie programa así. Lo normal es que los datos lleguen de uno en uno —de un archivo, del teclado— y la lista vaya creciendo sola.

Añadir por delante son dos líneas, y ninguna mueve nada: el nodo nuevo apunta a lo que era la cabeza, y la cabeza pasa a ser el nodo nuevo. Da igual que la lista tenga tres elementos o tres millones: cuesta lo mismo.

El orden es lo único que hay que cuidar. Si cambias la cabeza antes de que el nodo nuevo apunte a la vieja, pierdes la lista entera: nadie sabe ya dónde estaba. No hay forma de recuperarla y el programa sigue como si nada.

Hay un efecto secundario que sorprende la primera vez: como cada uno se pone delante, la lista sale al revés del orden en que entraron.

Y al terminar hay que devolver los nodos uno por uno. Aquí aparece la trampa: si liberas un nodo y después le pides su siguiente, estás leyendo un sitio que ya devolviste. Hay que guardarse la dirección del siguiente antes de soltar el actual.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *sig;
} Nodo;
 
int main(void)
{
    Nodo *cabeza = NULL;
 
    for (int i = 1; i <= 3; i++)
    {
        Nodo *n = malloc(sizeof(Nodo));
        n->valor = i;
        n->sig = cabeza;
        cabeza = n;
    }
 
    Nodo *p = cabeza;
    while (p != NULL)
    {
        printf("%d ", p->valor);
        p = p->sig;
    }
    printf("\n");
 
    while (cabeza != NULL)
    {
        Nodo *sig = cabeza->sig;
        free(cabeza);
        cabeza = sig;
    }
    return 0;
}

línea 9
Una lista vacía es una cabeza que no apunta a nada. No hace falta nada más para empezar.
línea 15
El nodo nuevo apunta a lo que había. Esta línea va antes que la siguiente: al revés, se pierde la lista entera.
línea 16
Y ahora la cabeza es el nuevo. Por esto la lista sale al revés del orden en que entraron.
línea 29
Se guarda el siguiente ANTES de soltar el actual. Después de free ya no se puede preguntar por él.

3Ahora tú

Este programa deja cada nodo apuntándose a sí mismo, así que el recorrido no termina nunca. Arregla el orden de las dos líneas para que escriba: 16 9 4 1

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *sig;
} Nodo;
 
int main(void)
{
    Nodo *cabeza = NULL;
 
    for (int i = 1; i <= 4; i++)
    {
        Nodo *n = malloc(sizeof(Nodo));
        n->valor = i * i;
        cabeza = n;
        n->sig = cabeza;
    }
 
    Nodo *p = cabeza;
    while (p != NULL)
    {
        printf("%d ", p->valor);
        p = p->sig;
    }
    printf("\n");
 
    while (cabeza != NULL)
    {
        Nodo *sig = cabeza->sig;
        free(cabeza);
        cabeza = sig;
    }
    return 0;
}

Una lista que crece

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

Memoria