Estructuras de datos dinámicas - Programación en C para Sistemas Operativos

1. Elegir una estructura

Una estructura de datos dinámica guarda una cantidad de elementos que se conoce recién al ejecutar el programa, y permite agregar y quitar. Las dos de este tema se distinguen por cómo guardan los elementos:

Un arreglo dinámico los guarda en un solo bloque, contiguos, uno al lado del otro, como el arreglo del tema 17, con la diferencia de que el bloque se agranda con realloc cuando se llena.
Una lista enlazada los guarda en un bloque por elemento, dispersos en la memoria, y cada bloque, llamado nodo, contiene un puntero al siguiente. La estructura autorreferida del tema 24, con memoria dinámica en lugar de variables locales.

La elección se hace por las operaciones que más se usan:

Operación	Arreglo dinámico	Lista simple (con puntero a la cola)	Lista doble circular
Acceder al elemento i	Inmediato, `v[i]`.	Recorrer i nodos.	Recorrer i nodos.
Agregar al final	Inmediato, salvo cuando hay que crecer (promedio constante).	Inmediato.	Inmediato.
Agregar al principio	Mover todos los elementos.	Inmediato.	Inmediato.
Quitar el último	Inmediato.	Recorrer toda la lista.	Inmediato.
Insertar o quitar en el medio, si ya se tiene la posición	Mover los elementos de atrás.	Inmediato (se necesita el anterior).	Inmediato.
Buscar un valor	Recorrer.	Recorrer.	Recorrer.
Memoria por elemento	Solo el elemento (más la capacidad que sobra).	El elemento, un puntero y la sobrecarga de `malloc`.	El elemento, dos punteros y la sobrecarga.
¿Se mueven los elementos al crecer?	Sí: los punteros a elementos quedan colgantes.	No: cada nodo se queda donde nació.	No.
Velocidad real al recorrer	Muy buena (secuencial en memoria).	Peor, y mucho peor si los nodos están dispersos (sección 5).	Igual que la simple.

La regla práctica: el arreglo es la opción por omisión, porque es más simple, usa menos memoria y es más rápido; la lista gana cuando se insertan y quitan elementos del medio u de los extremos con mucha frecuencia, o cuando importa que los elementos no se muevan, porque otras partes del programa guardan punteros a ellos. Las dos secciones siguientes las construyen completas, con todo el cuidado con la memoria que pedía el tema 29.

2. El arreglo que crece

El tema 28 anunció que este tema construiría un arreglo dinámico completo. Hace falta llevar tres datos juntos, que se agrupan en una estructura: el puntero al bloque, la cantidad de elementos en uso, y la capacidad, cuántos caben sin pedir más memoria. Las funciones que lo manejan reciben la estructura por puntero, y ninguna toca los campos desde afuera:

vector.c

#define _DEFAULT_SOURCE                   /* reallocarray */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct vector {
    int *datos;
    size_t cantidad;                      /* elementos en uso */
    size_t capacidad;                     /* elementos que caben sin pedir más */
};

static void vector_iniciar(struct vector *v)
{
    v->datos = NULL;
    v->cantidad = 0;
    v->capacidad = 0;
}

static void vector_destruir(struct vector *v)
{
    free(v->datos);
    vector_iniciar(v);
}

/* asegura lugar para 'n' elementos en total; 0 si lo logró, -1 si no */
static int vector_reservar(struct vector *v, size_t n)
{
    if (n <= v->capacidad)
        return 0;
    size_t nueva = v->capacidad ? v->capacidad : 4;

    while (nueva < n) {
        if (nueva > SIZE_MAX / 2)
            return -1;                    /* duplicar se desbordaría */
        nueva *= 2;
    }
    int *tmp = reallocarray(v->datos, nueva, sizeof *tmp);
    if (tmp == NULL)
        return -1;                        /* v sigue intacto */
    v->datos = tmp;
    v->capacidad = nueva;
    return 0;
}

static int vector_agregar(struct vector *v, int x)
{
    if (vector_reservar(v, v->cantidad + 1) != 0)
        return -1;
    v->datos[v->cantidad++] = x;
    return 0;
}

static int vector_insertar(struct vector *v, size_t i, int x)
{
    if (i > v->cantidad || vector_reservar(v, v->cantidad + 1) != 0)
        return -1;
    memmove(&v->datos[i + 1], &v->datos[i], (v->cantidad - i) * sizeof v->datos[0]);
    v->datos[i] = x;
    v->cantidad++;
    return 0;
}

static int vector_quitar(struct vector *v, size_t i)
{
    if (i >= v->cantidad)
        return -1;
    memmove(&v->datos[i], &v->datos[i + 1], (v->cantidad - i - 1) * sizeof v->datos[0]);
    v->cantidad--;
    return 0;
}

/* devuelve a la biblioteca lo que sobra */
static void vector_ajustar(struct vector *v)
{
    if (v->cantidad == v->capacidad)
        return;
    if (v->cantidad == 0) {
        vector_destruir(v);
        return;
    }
    int *tmp = realloc(v->datos, v->cantidad * sizeof *tmp);
    if (tmp != NULL) {                    /* si falla, el bloque más grande sigue siendo válido */
        v->datos = tmp;
        v->capacidad = v->cantidad;
    }
}

static void mostrar(const char *que, const struct vector *v)
{
    printf("%-22s cantidad %2zu, capacidad %2zu:", que, v->cantidad, v->capacidad);
    for (size_t i = 0; i < v->cantidad; i++)
        printf(" %d", v->datos[i]);
    printf("\n");
}

int main(void)
{
    struct vector v;

    vector_iniciar(&v);
    size_t anterior = 0;

    for (int x = 1; x <= 10; x++) {
        if (vector_agregar(&v, x * x) != 0) {
            fprintf(stderr, "sin memoria\n");
            vector_destruir(&v);
            return 1;
        }
        if (v.capacidad != anterior) {
            printf("al agregar el elemento %2d la capacidad pasó de %2zu a %2zu\n", x, anterior, v.capacidad);
            anterior = v.capacidad;
        }
    }
    mostrar("después de agregar 10", &v);
    vector_insertar(&v, 0, -1);
    mostrar("insertar -1 al inicio", &v);
    vector_quitar(&v, 5);
    mostrar("quitar el índice 5", &v);
    vector_ajustar(&v);
    mostrar("ajustar", &v);
    vector_destruir(&v);
    mostrar("destruido", &v);
    return 0;
}

terminal

$ gcc -std=c17 -Wall -Wextra -g -o vector vector.c && ./vector
al agregar el elemento  1 la capacidad pasó de  0 a  4
al agregar el elemento  5 la capacidad pasó de  4 a  8
al agregar el elemento  9 la capacidad pasó de  8 a 16
después de agregar 10 cantidad 10, capacidad 16: 1 4 9 16 25 36 49 64 81 100
insertar -1 al inicio  cantidad 11, capacidad 16: -1 1 4 9 16 25 36 49 64 81 100
quitar el índice 5    cantidad 10, capacidad 16: -1 1 4 9 16 36 49 64 81 100
ajustar                cantidad 10, capacidad 10: -1 1 4 9 16 36 49 64 81 100
destruido              cantidad  0, capacidad  0:
$ valgrind --leak-check=full ./vector 2>&1 | grep -E 'total heap|All heap|ERROR SUMMARY'
  total heap usage: 5 allocs, 5 frees, 4,248 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Las decisiones de diseño merecen explicación:

Los tres campos tienen un invariante: cantidad <= capacidad, y datos es NULL exactamente cuando capacidad es 0. Un vector vacío, recién iniciado con vector_iniciar, no reserva nada; el primer vector_agregar pide 4 elementos. Todas las funciones suponen el invariante, y todas lo dejan cumplido.
La capacidad se duplica: 0, 4, 8, 16. Cada vez que se llena, se pide el doble, la estrategia del tema 28 que hace constante el costo promedio de agregar. El bucle de vector_reservar también duplica hasta alcanzar la cantidad pedida, de modo que sirve para vector_insertar y para reservar de antemano.
La comprobación de desborde: antes de duplicar se verifica que nueva no pase de SIZE_MAX / 2. reallocarray comprueba la multiplicación por el tamaño del elemento (tema 28), pero no la duplicación de la capacidad: eso lo hace el programa.
Los errores no dañan lo que había. Si reallocarray falla, el bloque original sigue válido, v no se modificó y la función devuelve −1. Quien llama decide qué hacer, y puede destruir el vector sin perder nada.
Insertar y quitar en el medio mueven con memmove, no con memcpy, porque origen y destino se superponen (tema 21). El costo es proporcional a la cantidad de elementos que se mueven.
vector_ajustar devuelve la capacidad que sobra, y si falla no importa: el bloque grande sigue siendo válido. Es una optimización opcional, para un vector que ya no va a crecer.
Se pasa siempre la estructura por puntero, como recomendó el tema 24, y el vector nunca expone datos como una dirección que dure: cualquier agregado puede mover el bloque, y entonces cualquier puntero a un elemento queda colgante, el error de crecer_mal.c del tema 29. Se accede por índice, v.datos[i], que sobrevive al movimiento.

La destrucción es una sola llamada a free: el vector tiene un bloque y es su dueño. Valgrind lo confirma: cinco reservas (las tres ampliaciones, la reducción y la que hace el propio stdio) y cinco liberaciones, cero errores.

3. La lista enlazada

Un nodo de una lista simple contiene el dato y un puntero al nodo siguiente; el último apunta a NULL. La lista misma se representa con una estructura que guarda la cabeza, el primer nodo, y conviene guardar también la cola, el último, para poder agregar al final sin recorrer:

La estructura lista guarda el primero y el último; cada nodo, el dato y el siguiente.

lista.c

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

struct nodo {
    int valor;
    struct nodo *siguiente;
};

struct lista {
    struct nodo *cabeza;
    struct nodo *cola;                    /* el último nodo: agregar al final sin recorrer */
    size_t cantidad;
};

static void lista_iniciar(struct lista *l)
{
    l->cabeza = NULL;
    l->cola = NULL;
    l->cantidad = 0;
}

static struct nodo *nodo_nuevo(int valor)
{
    struct nodo *n = malloc(sizeof *n);

    if (n != NULL) {
        n->valor = valor;
        n->siguiente = NULL;
    }
    return n;
}

static int lista_agregar_inicio(struct lista *l, int valor)
{
    struct nodo *n = nodo_nuevo(valor);

    if (n == NULL)
        return -1;
    n->siguiente = l->cabeza;
    l->cabeza = n;
    if (l->cola == NULL)                  /* era la primera */
        l->cola = n;
    l->cantidad++;
    return 0;
}

static int lista_agregar_final(struct lista *l, int valor)
{
    struct nodo *n = nodo_nuevo(valor);

    if (n == NULL)
        return -1;
    if (l->cola == NULL)
        l->cabeza = n;
    else
        l->cola->siguiente = n;
    l->cola = n;
    l->cantidad++;
    return 0;
}

static struct nodo *lista_buscar(const struct lista *l, int valor)
{
    for (struct nodo *n = l->cabeza; n != NULL; n = n->siguiente)
        if (n->valor == valor)
            return n;
    return NULL;
}

/* quita el primer nodo con ese valor; 0 si lo encontró, -1 si no */
static int lista_quitar(struct lista *l, int valor)
{
    struct nodo *previo = NULL;
    struct nodo **enlace = &l->cabeza;    /* la dirección del puntero que apunta al nodo actual */

    while (*enlace != NULL && (*enlace)->valor != valor) {
        previo = *enlace;
        enlace = &previo->siguiente;
    }
    if (*enlace == NULL)
        return -1;
    struct nodo *borrado = *enlace;

    *enlace = borrado->siguiente;         /* sirve igual para la cabeza y para el medio */
    if (borrado == l->cola)
        l->cola = previo;
    free(borrado);
    l->cantidad--;
    return 0;
}

static void lista_invertir(struct lista *l)
{
    struct nodo *anterior = NULL;
    struct nodo *actual = l->cabeza;

    l->cola = l->cabeza;
    while (actual != NULL) {
        struct nodo *siguiente = actual->siguiente;

        actual->siguiente = anterior;
        anterior = actual;
        actual = siguiente;
    }
    l->cabeza = anterior;
}

static void lista_destruir(struct lista *l)
{
    struct nodo *n = l->cabeza;

    while (n != NULL) {
        struct nodo *siguiente = n->siguiente;   /* guardarlo ANTES de liberar */

        free(n);
        n = siguiente;
    }
    lista_iniciar(l);
}

static void mostrar(const char *que, const struct lista *l)
{
    printf("%-26s", que);
    for (const struct nodo *n = l->cabeza; n != NULL; n = n->siguiente)
        printf("%d -> ", n->valor);
    printf("NULL   (cantidad %zu, cola %s)\n", l->cantidad,
           l->cola ? (l->cola->siguiente == NULL ? "ok" : "MAL") : "NULL");
}

int main(void)
{
    struct lista l;

    lista_iniciar(&l);
    for (int x = 3; x <= 5; x++)
        lista_agregar_final(&l, x);
    lista_agregar_inicio(&l, 2);
    lista_agregar_inicio(&l, 1);
    mostrar("1..5:", &l);

    printf("buscar 4: %s, buscar 9: %s\n",
           lista_buscar(&l, 4) ? "está" : "no está", lista_buscar(&l, 9) ? "está" : "no está");
    lista_quitar(&l, 3);
    mostrar("quitar 3 (medio):", &l);
    lista_quitar(&l, 1);
    mostrar("quitar 1 (cabeza):", &l);
    lista_quitar(&l, 5);
    mostrar("quitar 5 (cola):", &l);
    printf("quitar 9: %d\n", lista_quitar(&l, 9));
    lista_invertir(&l);
    mostrar("invertida:", &l);
    lista_agregar_final(&l, 7);
    mostrar("agregar 7 al final:", &l);
    lista_destruir(&l);
    mostrar("destruida:", &l);
    return 0;
}

terminal

$ gcc -std=c17 -Wall -Wextra -g -o lista lista.c && ./lista
1..5:                     1 -> 2 -> 3 -> 4 -> 5 -> NULL   (cantidad 5, cola ok)
buscar 4: está, buscar 9: no está
quitar 3 (medio):         1 -> 2 -> 4 -> 5 -> NULL   (cantidad 4, cola ok)
quitar 1 (cabeza):        2 -> 4 -> 5 -> NULL   (cantidad 3, cola ok)
quitar 5 (cola):          2 -> 4 -> NULL   (cantidad 2, cola ok)
quitar 9: -1
invertida:                4 -> 2 -> NULL   (cantidad 2, cola ok)
agregar 7 al final:       4 -> 2 -> 7 -> NULL   (cantidad 3, cola ok)
destruida:                NULL   (cantidad 0, cola NULL)
$ valgrind --leak-check=full ./lista 2>&1 | grep -E 'total heap|All heap|ERROR SUMMARY'
  total heap usage: 7 allocs, 7 frees, 4,192 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Las operaciones de una lista tienen siempre los mismos casos especiales, los extremos, y se pueden ver una por una:

Agregar necesita separar el caso de la lista vacía: el primer nodo es a la vez la cabeza y la cola. Los dos agregados mantienen cola y cantidad al día, y ese es el invariante de la lista: cola es el último nodo, o NULL si no hay ninguno.
Buscar recorre con un puntero que avanza con n = n->siguiente, el recorrido de las cadenas del tema 18, pero sobre nodos que no están contiguos.
Invertir no reserva ni libera nada: recorre la lista dando vuelta cada puntero, con tres punteros auxiliares. Al terminar, la antigua cabeza es la cola, y por eso la función actualiza cola al principio.
Mostrar comprueba el invariante en cada salida: la palabra «ok» indica que cola->siguiente es NULL.

Quitar un nodo es la operación donde casi todos se equivocan, porque obliga a cambiar el puntero que apunta al nodo, y ese puntero es distinto según dónde esté: l->cabeza si es el primero, o el siguiente del nodo anterior. La solución habitual es separar dos casos con un if. Una solución mejor aprovecha el puntero a puntero del tema 19:

La variable enlace guarda la dirección del puntero que hay que cambiar, no la del nodo. Con *enlace se lee y se escribe ese puntero.

En lista_quitar, enlace es un struct nodo **: arranca valiendo &l->cabeza, y en cada paso pasa a valer la dirección del campo siguiente del nodo que se acaba de pasar. *enlace es entonces «el puntero que apunta al nodo actual», sea cual sea, y la operación *enlace = borrado->siguiente lo saltea. No hay ningún caso especial para la cabeza: es la misma línea que para el medio. El único trabajo adicional es el de la cola, que si se quita se actualiza al nodo anterior, que el programa va guardando en previo.

Por último, lista_destruir tiene una línea que parece de más y es la más importante: siguiente = n->siguiente antes de free(n). Después de liberar un nodo ya no se puede leer su campo siguiente. La sección siguiente muestra qué pasa si se invierte el orden.

4. Destruir una lista sin errores

Liberar una lista es la operación donde se cometen dos errores clásicos. El primero es el que acabamos de ver, que se escribe con naturalidad:

liberar_mal.c · el bucle de liberación

    for (struct nodo *n = cabeza; n != NULL; n = n->siguiente)
        free(n);                          /* n->siguiente se lee DESPUÉS de free(n) */

terminal

$ gcc -std=c17 -Wall -Wextra -g -o liberar_mal liberar_mal.c
liberar_mal.c: In function ‘main’:
liberar_mal.c:22:48: warning: pointer ‘n’ used after ‘free’ [-Wuse-after-free]
   22 |     for (struct nodo *n = cabeza; n != NULL; n = n->siguiente)
      |                                              ~~^~~~~~~~~~~~~~
liberar_mal.c:23:9: note: call to ‘free’ here
   23 |         free(n);                          /* n->siguiente se lee DESPUÉS de free(n) */
      |         ^~~~~~~
$ ./liberar_mal
free(): invalid pointer
Aborted
$ ./liberar_mal_asan
==542==ERROR: AddressSanitizer: heap-use-after-free on address 0x7b8b704e0058 at pc 0x5b05aa48e4ab …
READ of size 8 at 0x7b8b704e0058 thread T0
    #0 0x5b05aa48e4aa in main /home/ana/c/tema30/liberar_mal.c:22
    …
0x7b8b704e0058 is located 8 bytes inside of 16-byte region [0x7b8b704e0050,0x7b8b704e0060)
freed by thread T0 here:
    #0 0x7f6b7212a3ff in free …
    #1 0x5b05aa48e439 in main /home/ana/c/tema30/liberar_mal.c:23

gcc avisó con -Wuse-after-free, y el programa aborta con free(): invalid pointer: el campo siguiente de un nodo liberado ya no contiene el puntero original, sino los datos que el administrador escribió en esos bytes (tema 28), y el siguiente free recibe un valor sin sentido. El mensaje no menciona la lista, ni la lectura después de liberar. ASan lo explica: una lectura de 8 bytes, a 8 bytes del comienzo de un bloque de 16, que la línea 23 acababa de liberar. Es el campo siguiente del nodo.

El segundo error es sutil, y aparece con listas largas: liberar con una función recursiva, que parece elegante:

recursiva.c

/* liberar con recursión: cada nodo es un nivel de la pila */
static void liberar_recursivo(struct nodo *n)
{
    if (n == NULL)
        return;
    liberar_recursivo(n->siguiente);
    free(n);
}

int main(int argc, char *argv[])
{
    long cuantos = argc > 1 ? strtol(argv[1], NULL, 10) : 1000000;
    struct nodo *cabeza = NULL;

    for (long i = 0; i < cuantos; i++) {
        struct nodo *n = malloc(sizeof *n);

        if (n == NULL)
            return 1;
        n->valor = (int) i;
        n->siguiente = cabeza;
        cabeza = n;
    }
    printf("lista de %ld nodos construida\n", cuantos);
    liberar_recursivo(cabeza);
    printf("liberada\n");
    return 0;
}

terminal

$ ./recursiva 100000
lista de 100000 nodos construida
liberada
$ ./recursiva 300000
Segmentation fault
$ ./recursiva
Segmentation fault
$ ./recursiva_asan
==553==ERROR: AddressSanitizer: stack-overflow on address 0x7ffdc7325ff8 (pc 0x5e6cb5fb4335 …)
    #0 0x5e6cb5fb4335 in liberar_recursivo /home/ana/c/tema30/recursiva.c:11
    #1 0x5e6cb5fb43c4 in liberar_recursivo /home/ana/c/tema30/recursiva.c:14
    #2 0x5e6cb5fb43c4 in liberar_recursivo /home/ana/c/tema30/recursiva.c:14
    …

Con 100 000 nodos funciona; con 300 000, o con el millón por omisión, el programa termina con Segmentation fault. Cada nodo de la lista es un nivel de recursión, con su marco de pila (tema 12), y la pila tiene 8 MiB, como vimos en el tema 27: con marcos de 32 bytes, el límite está alrededor de los 260 000 niveles, que es lo que ocurre. Compilar con optimización no lo evita, porque el free viene después de la llamada recursiva, de modo que no es una llamada de cola. La conclusión es una regla de diseño: una lista se recorre y se destruye con un bucle, no con recursión; su largo lo decide quien usa el programa, y la pila no es un recurso para gastar a razón de un marco por elemento. ASan lo identifica sin ambigüedad: stack-overflow, con la misma función repetida cientos de miles de veces.

5. Lo que cuesta cada una

La tabla de la sección 1 usa palabras como «inmediato». Este programa mide lo que significan: crea dos millones de enteros de 8 bytes en un arreglo y en una lista, y los recorre sumándolos. Para la lista lo hace de dos maneras: con los nodos enlazados en el orden en que se reservaron, y después enlazados en orden aleatorio, con los mismos nodos, para que cada salto caiga lejos del anterior. Las funciones auxiliares segundos y campo son las de los temas anteriores:

rendimiento.c · el programa principal

enum { N = 2000000 };

struct nodo {
    long valor;
    struct nodo *siguiente;
};

static long suma_lista(const struct nodo *n)
{
    long s = 0;

    for (; n != NULL; n = n->siguiente)
        s += n->valor;
    return s;
}

int main(void)
{
    double t0;
    long base = campo("VmRSS:");

    /* 1. arreglo: un solo bloque */
    t0 = segundos();
    long *v = malloc(N * sizeof *v);
    for (long i = 0; i < N; i++)
        v[i] = i;
    double construir_v = segundos() - t0;
    long mem_v = campo("VmRSS:") - base;
    t0 = segundos();
    long suma_v = 0;
    for (long i = 0; i < N; i++)
        suma_v += v[i];
    double recorrer_v = segundos() - t0;

    /* 2. lista: un bloque por nodo, en el orden en que se pidieron */
    base = campo("VmRSS:");
    t0 = segundos();
    struct nodo **nodos = malloc(N * sizeof *nodos);   /* para poder reordenar después */
    struct nodo *cabeza = NULL, *cola = NULL;
    for (long i = 0; i < N; i++) {
        struct nodo *n = malloc(sizeof *n);
        n->valor = i;
        n->siguiente = NULL;
        nodos[i] = n;
        if (cola == NULL)
            cabeza = n;
        else
            cola->siguiente = n;
        cola = n;
    }
    double construir_l = segundos() - t0;
    long mem_l = campo("VmRSS:") - base;
    t0 = segundos();
    long suma_l = suma_lista(cabeza);
    double recorrer_l = segundos() - t0;

    /* 3. los mismos nodos, enlazados en orden aleatorio: cada salto cae lejos del anterior */
    srand(1);
    for (long i = N - 1; i > 0; i--) {
        long j = rand() % (i + 1);
        struct nodo *t = nodos[i];

        nodos[i] = nodos[j];
        nodos[j] = t;
    }
    for (long i = 0; i + 1 < N; i++)
        nodos[i]->siguiente = nodos[i + 1];
    nodos[N - 1]->siguiente = NULL;
    t0 = segundos();
    long suma_m = suma_lista(nodos[0]);
    double recorrer_m = segundos() - t0;

    printf("%d elementos de 8 bytes\n", N);
    printf("%-34s construir %.3f s   recorrer %.4f s   memoria %6ld KiB\n",
           "arreglo (un bloque)", construir_v, recorrer_v, mem_v);
    printf("%-34s construir %.3f s   recorrer %.4f s   memoria %6ld KiB\n",
           "lista, nodos contiguos", construir_l, recorrer_l, mem_l);
    printf("%-34s                   recorrer %.4f s\n", "lista, nodos en desorden", recorrer_m);
    printf("sumas: %ld %ld %ld\n", suma_v, suma_l, suma_m);
    for (long i = 0; i < N; i++)
        free(nodos[i]);
    free(nodos);
    free(v);
    return 0;
}

terminal · compilado con -O2

$ gcc -std=c17 -Wall -Wextra -O2 -o rendimiento rendimiento.c && ./rendimiento
2000000 elementos de 8 bytes
arreglo (un bloque)                construir 0.004 s   recorrer 0.0009 s   memoria  15744 KiB
lista, nodos contiguos             construir 0.047 s   recorrer 0.0056 s   memoria  78208 KiB
lista, nodos en desorden                             recorrer 0.1583 s
sumas: 1999999000000 1999999000000 1999999000000

	Construir	Recorrer	Memoria	Contra el arreglo
Arreglo, un bloque	0,004 s	0,0009 s	15 744 KiB	—
Lista, nodos contiguos	0,047 s	0,0056 s	78 208 KiB	12× construir, 6× recorrer, 5× memoria
Lista, nodos dispersos	—	0,158 s	(la misma)	unas 175× recorrer

Los tres resultados vienen del hardware, y los tres se ven en las columnas:

Memoria: 5 veces más. Cada nodo guarda 16 bytes (el dato y el puntero), pero malloc le asigna un bloque de 32, como vimos con malloc_usable_size en el tema 28: 8 bytes de encabezado, más el redondeo. Con el arreglo de punteros auxiliar descontado, los 2 millones de nodos ocupan 62 583 KiB, 32 bytes cada uno, contra los 8 del arreglo. Un dato de 8 bytes en una lista cuesta cuatro veces su tamaño.
Construir: 12 veces más lento, por los dos millones de llamadas a malloc, que cuestan cada una unas decenas de nanosegundos, contra una sola llamada.
Recorrer los nodos contiguos: 6 veces más lento. Los nodos se reservaron uno tras otro, y malloc los puso uno al lado del otro, de modo que el recorrido es casi secuencial y la caché y el prefetcher del procesador (tema 23) trabajan bien. Aun así, el arreglo lee 8 bytes útiles por cada 8 bytes de memoria, y la lista, 8 por cada 32.
Recorrer los nodos dispersos: 28 veces más lento que los contiguos. Son los mismos nodos, con los mismos datos y la misma cantidad de trabajo; lo único que cambió es el orden de los saltos. Cada n->siguiente ahora cae en un lugar que no está en la caché, y el procesador espera a la memoria principal en cada nodo. Es el efecto del orden de recorrido que medimos en el tema 23, llevado al extremo: no hay forma de adivinar la dirección siguiente hasta haber leído el nodo actual.

En un programa real, una lista que se construye y se modifica durante mucho tiempo, con inserciones y borrados en el medio, se parece más a la tercera fila que a la segunda: los nodos nuevos ocupan los huecos que dejaron los liberados, y el orden en la lista deja de coincidir con el orden en la memoria. Por eso la recomendación de la sección 1: el arreglo por omisión. Las listas se justifican cuando sus ventajas estructurales importan, y aun así conviene medir antes de decidir. Para mover elementos en un arreglo grande, que es su punto débil, hay un último argumento a favor del arreglo: memmove es muy rápido, y para cientos o miles de elementos copiar es más barato que seguir punteros.

6. Listas dentro de los objetos

La lista de la sección 3 tiene un defecto de diseño: hay una lista distinta para cada tipo de dato, y cada elemento requiere dos reservas, el objeto y el nodo que lo apunta. El núcleo Linux, que mantiene cientos de listas de objetos de todo tipo (procesos, archivos abiertos, dispositivos), resuelve ambos problemas con las listas intrusivas: el enlace no se pone fuera del objeto, sino adentro, como un campo más. La lista solo conoce enlaces, y el objeto se recupera con container_of, la macro del tema 25. Se hace además doblemente enlazada y circular, con un enlace especial como centinela que representa la lista misma:

enlaces.c

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

/* el enlace que cada objeto lleva adentro: la lista no sabe qué objetos une */
struct enlace {
    struct enlace *anterior;
    struct enlace *siguiente;
};

#define contenedor_de(ptr, tipo, campo) \
    ((tipo *) ((char *) (ptr) - offsetof(tipo, campo)))

/* la cabeza es un enlace "centinela": una lista vacía se apunta a sí misma */
static void lista_iniciar(struct enlace *cabeza)
{
    cabeza->anterior = cabeza;
    cabeza->siguiente = cabeza;
}

static int lista_vacia(const struct enlace *cabeza)
{
    return cabeza->siguiente == cabeza;
}

/* inserta 'nuevo' justo antes de 'posicion'; sin casos especiales */
static void insertar_antes(struct enlace *nuevo, struct enlace *posicion)
{
    nuevo->anterior = posicion->anterior;
    nuevo->siguiente = posicion;
    posicion->anterior->siguiente = nuevo;
    posicion->anterior = nuevo;
}

static void agregar_final(struct enlace *cabeza, struct enlace *nuevo)
{
    insertar_antes(nuevo, cabeza);        /* antes del centinela = al final */
}

static void agregar_inicio(struct enlace *cabeza, struct enlace *nuevo)
{
    insertar_antes(nuevo, cabeza->siguiente);
}

static void quitar(struct enlace *e)
{
    e->anterior->siguiente = e->siguiente;
    e->siguiente->anterior = e->anterior;
    e->anterior = NULL;
    e->siguiente = NULL;
}

struct tarea {
    int id;
    char nombre[16];
    struct enlace en_lista;
};

static struct tarea *tarea_nueva(int id, const char *nombre)
{
    struct tarea *t = malloc(sizeof *t);

    if (t == NULL)
        return NULL;
    t->id = id;
    snprintf(t->nombre, sizeof t->nombre, "%s", nombre);
    return t;
}

static void mostrar(const char *que, const struct enlace *cabeza)
{
    printf("%-24s", que);
    for (const struct enlace *e = cabeza->siguiente; e != cabeza; e = e->siguiente) {
        const struct tarea *t = contenedor_de(e, const struct tarea, en_lista);

        printf(" %d:%s", t->id, t->nombre);
    }
    printf("  |  al revés:");
    for (const struct enlace *e = cabeza->anterior; e != cabeza; e = e->anterior) {
        const struct tarea *t = contenedor_de(e, const struct tarea, en_lista);

        printf(" %d", t->id);
    }
    printf("\n");
}

int main(void)
{
    struct enlace cabeza;
    struct tarea *t[4];
    const char *nombres[4] = {"compilar", "probar", "empaquetar", "publicar"};

    lista_iniciar(&cabeza);
    printf("vacía: %s\n", lista_vacia(&cabeza) ? "sí" : "no");
    for (int i = 0; i < 4; i++) {
        t[i] = tarea_nueva(i + 1, nombres[i]);
        if (t[i] == NULL)
            return 1;
    }
    agregar_final(&cabeza, &t[1]->en_lista);
    agregar_final(&cabeza, &t[2]->en_lista);
    agregar_inicio(&cabeza, &t[0]->en_lista);
    agregar_final(&cabeza, &t[3]->en_lista);
    mostrar("1..4:", &cabeza);

    quitar(&t[1]->en_lista);
    free(t[1]);
    mostrar("quitar la 2:", &cabeza);
    quitar(&t[0]->en_lista);
    free(t[0]);
    mostrar("quitar la primera:", &cabeza);
    quitar(&t[3]->en_lista);
    free(t[3]);
    mostrar("quitar la última:", &cabeza);
    quitar(&t[2]->en_lista);
    free(t[2]);
    printf("vacía: %s\n", lista_vacia(&cabeza) ? "sí" : "no");
    return 0;
}

terminal

$ gcc -std=c17 -Wall -Wextra -g -o enlaces enlaces.c && ./enlaces
vacía: sí
1..4:                    1:compilar 2:probar 3:empaquetar 4:publicar  |  al revés: 4 3 2 1
quitar la 2:             1:compilar 3:empaquetar 4:publicar  |  al revés: 4 3 1
quitar la primera:       3:empaquetar 4:publicar  |  al revés: 4 3
quitar la última:       3:empaquetar  |  al revés: 3
vacía: sí
$ valgrind --leak-check=full ./enlaces 2>&1 | grep -E 'total heap|All heap|ERROR SUMMARY'
  total heap usage: 5 allocs, 5 frees, 4,256 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Hay tres ventajas, y se ven en el código:

Una sola reserva por objeto. Las cuatro tareas se pidieron con un malloc cada una, y el enlace viaja adentro. Y los enlaces de la lista (anterior y siguiente) se quitan sin reservar ni liberar nada: quitar solo reajusta punteros, y el free del objeto es una decisión aparte de quien lo posee.
Ningún caso especial. Como la lista es circular y tiene el centinela, todo nodo tiene siempre un anterior y un siguiente, aunque sean la cabeza. insertar_antes sirve para agregar al final, antes del centinela, y al principio, antes del primero; quitar es de dos líneas e idéntica para el primero, el último y el único. Las condiciones de borde de la lista simple, cabeza, cola y NULL, no existen. La lista vacía no tiene un valor especial: es la cabeza apuntándose a sí misma.
Un objeto puede estar en varias listas a la vez, si lleva más de un enlace: una struct tarea con un en_lista y un en_cola puede estar en la lista de todas las tareas y en la de las pendientes. Para recuperar el objeto desde cualquier enlace, se usa contenedor_de con el nombre del campo que corresponda. Es lo que hace el núcleo con los procesos, que están al mismo tiempo en la lista de todos los procesos, en la cola del planificador y en la lista de hijos de su padre.

La macro depende de que el enlace sea un campo de la estructura: la dirección del objeto es la del enlace menos el desplazamiento del campo (offsetof, tema 25), que es 24 para en_lista en esta struct tarea (4 bytes de id, 16 de nombre y 4 de relleno para alinear el enlace a 8). El precio es que el código se vuelve menos obvio, y que el compilador no comprueba que el puntero y el tipo coincidan: si e no es el en_lista de una struct tarea, el resultado es una dirección sin sentido. La estructura de datos «lista circular con centinela» y la técnica del «enlace intrusivo» son una de las ideas más reutilizadas del código de sistemas en C.

7. Colas y un planificador

Una cola (FIFO, el primero en entrar es el primero en salir) se construye con una lista simple que tiene cabeza y cola: se agrega por la cola y se saca por la cabeza, ambas operaciones inmediatas. Una pila (LIFO) es lo mismo con una sola punta, y se hace mejor con un arreglo dinámico: vector_agregar apila y quitar el último desapila. Las colas están en el corazón de un sistema operativo: la cola de procesos listos para correr, la de peticiones a un disco, la de paquetes de una red. Este programa simula la primera, con el algoritmo de planificación más conocido, round-robin: cada proceso corre un tiempo fijo, el quantum, y si no terminó vuelve al final de la cola:

planificador.c

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

struct proceso {
    int pid;
    char nombre[16];
    int restante;                         /* unidades de CPU que todavía necesita */
    int llegada;
    struct proceso *siguiente;
};

/* una cola FIFO: se agrega por la cola y se saca por la cabeza, ambos en O(1) */
struct cola {
    struct proceso *cabeza;
    struct proceso *cola;
};

static void encolar(struct cola *c, struct proceso *p)
{
    p->siguiente = NULL;
    if (c->cola == NULL)
        c->cabeza = p;
    else
        c->cola->siguiente = p;
    c->cola = p;
}

static struct proceso *desencolar(struct cola *c)
{
    struct proceso *p = c->cabeza;

    if (p != NULL) {
        c->cabeza = p->siguiente;
        if (c->cabeza == NULL)
            c->cola = NULL;
        p->siguiente = NULL;
    }
    return p;
}

static struct proceso *crear(int pid, const char *nombre, int necesita)
{
    struct proceso *p = malloc(sizeof *p);

    if (p == NULL)
        return NULL;
    p->pid = pid;
    snprintf(p->nombre, sizeof p->nombre, "%s", nombre);
    p->restante = necesita;
    p->llegada = 0;
    p->siguiente = NULL;
    return p;
}

int main(void)
{
    enum { QUANTUM = 3 };
    struct cola listos = {NULL, NULL};
    struct { int pid; const char *nombre; int necesita; } tabla[] = {
        {1, "init", 5}, {845, "sshd", 2}, {1532, "bash", 8}, {2001, "gcc", 12},
    };
    int reloj = 0, terminados = 0, total_espera = 0, total_retorno = 0;

    for (size_t i = 0; i < sizeof tabla / sizeof tabla[0]; i++) {
        struct proceso *p = crear(tabla[i].pid, tabla[i].nombre, tabla[i].necesita);

        if (p == NULL)
            return 1;
        encolar(&listos, p);
    }
    printf("planificador round-robin, quantum = %d\n", QUANTUM);
    printf("  t  pid  proceso  corre  queda\n");

    struct proceso *p;
    while ((p = desencolar(&listos)) != NULL) {
        int corre = p->restante < QUANTUM ? p->restante : QUANTUM;

        p->restante -= corre;
        printf("%3d %4d  %-7s %5d  %5d%s\n", reloj, p->pid, p->nombre, corre, p->restante,
               p->restante == 0 ? "   terminó" : "");
        reloj += corre;
        if (p->restante > 0) {
            encolar(&listos, p);          /* vuelve al final de la cola */
        } else {
            int necesito = 0;

            for (size_t i = 0; i < sizeof tabla / sizeof tabla[0]; i++)
                if (tabla[i].pid == p->pid)
                    necesito = tabla[i].necesita;
            total_retorno += reloj;
            total_espera += reloj - necesito;
            terminados++;
            free(p);                      /* terminó: el planificador deja de ser su dueño */
        }
    }
    printf("%d procesos; retorno medio %.2f, espera media %.2f\n", terminados,
           (double) total_retorno / terminados, (double) total_espera / terminados);
    return 0;
}

terminal

$ gcc -std=c17 -Wall -Wextra -g -o planificador planificador.c && ./planificador
planificador round-robin, quantum = 3
  t  pid  proceso  corre  queda
  0    1  init        3      2
  3  845  sshd        2      0   terminó
  5 1532  bash        3      5
  8 2001  gcc         3      9
 11    1  init        2      0   terminó
 13 1532  bash        3      2
 16 2001  gcc         3      6
 19 1532  bash        2      0   terminó
 21 2001  gcc         3      3
 24 2001  gcc         3      0   terminó
4 procesos; retorno medio 16.50, espera media 9.75
$ valgrind --leak-check=full ./planificador 2>&1 | grep -E 'total heap|All heap|ERROR SUMMARY'
  total heap usage: 5 allocs, 5 frees, 4,256 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

El registro muestra cómo se reparte la CPU. init necesita 5 unidades: corre 3, vuelve al final de la cola, y termina en su segunda vuelta con 2; sshd, que necesita solo 2, termina en su primer turno sin completar el quantum; gcc, con 12, da cuatro vueltas. La cola nunca se recorre: encolar y desencolar solo tocan la cabeza o la cola, y un proceso que vuelve a la cola es el mismo bloque, que cambia de lugar con dos punteros, sin copiar ni reservar. Las métricas son las clásicas de la planificación: el tiempo de retorno, desde que llega hasta que termina, y el de espera, el que pasó en la cola sin correr; el round-robin reparte la CPU de forma equitativa, a costa de que los procesos largos tarden más. El tema de la planificación se estudia a fondo en el curso de Fundamentos de Sistemas Operativos; aquí lo importante es que la estructura de datos es la que cualquier planificador real usa.

Y hay una decisión de propiedad escondida en el programa: cada proceso lo crea main con crear, lo posee la cola mientras está en ella, lo posee el bucle cuando lo saca, y lo libera main cuando termina. Nadie lo copia, y al final no queda ninguno: cinco reservas, cinco liberaciones. Esa pregunta, quién es dueño, es el tema de la sección siguiente.

8. Quién es dueño de cada elemento

Una estructura de datos dinámica contiene elementos, y cuando esos elementos tienen memoria propia, como un texto, surge la pregunta del tema 28 en su forma más difícil: ¿quién libera el texto de un elemento cuando la estructura lo guarda? Hay tres respuestas, y la interfaz de la estructura debe elegir una y documentarla:

Política	Al agregar…	Al destruir la estructura…	Riesgo
Copiar (la estructura es dueña)	Guarda una copia propia del dato (`strdup`).	Libera todas las copias.	El costo de copiar.
Prestar (la estructura no es dueña)	Guarda la dirección que le dan, sin copiar.	No libera nada de los elementos.	El dato debe seguir vivo y sin cambiar mientras la estructura lo use.
Transferir (cambia el dueño)	Toma posesión de un bloque que le entrega quien llama.	Libera lo que todavía posee. Al sacar un elemento, se lo devuelve a quien lo pide, que pasa a ser su dueño.	Olvidar quién es dueño después de la transferencia.

Este programa implementa una lista de textos con las políticas de copiar y transferir:

textos.c

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct nodo {
    char *texto;                          /* memoria que pertenece a la lista */
    struct nodo *siguiente;
};

struct textos {
    struct nodo *cabeza;
    struct nodo *cola;
};

/* La lista COPIA el texto: desde ahora es dueña de su copia. */
static int textos_agregar(struct textos *l, const char *texto)
{
    struct nodo *n = malloc(sizeof *n);

    if (n == NULL)
        return -1;
    n->texto = strdup(texto);
    if (n->texto == NULL) {               /* deshacer lo ya reservado */
        free(n);
        return -1;
    }
    n->siguiente = NULL;
    if (l->cola == NULL)
        l->cabeza = n;
    else
        l->cola->siguiente = n;
    l->cola = n;
    return 0;
}

/* Quita el primero y TRANSFIERE la propiedad: quien llama debe hacer free del texto. */
static char *textos_sacar(struct textos *l)
{
    struct nodo *n = l->cabeza;

    if (n == NULL)
        return NULL;
    char *texto = n->texto;

    l->cabeza = n->siguiente;
    if (l->cabeza == NULL)
        l->cola = NULL;
    free(n);                              /* el nodo se libera; el texto sale de la lista */
    return texto;
}

/* Destruir libera lo que la lista todavía posee: los textos que quedan y los nodos. */
static void textos_destruir(struct textos *l)
{
    char *t;

    while ((t = textos_sacar(l)) != NULL)
        free(t);
}

int main(void)
{
    struct textos l = {NULL, NULL};
    char buffer[32];
    const char *entrada[] = {"Ana", "Luis", "Beatriz", "Carlos"};

    for (size_t i = 0; i < sizeof entrada / sizeof entrada[0]; i++) {
        snprintf(buffer, sizeof buffer, "%s", entrada[i]);     /* un único buffer, reutilizado */
        if (textos_agregar(&l, buffer) != 0) {
            fprintf(stderr, "sin memoria\n");
            textos_destruir(&l);
            return 1;
        }
    }
    for (int i = 0; i < 2; i++) {
        char *t = textos_sacar(&l);        /* ahora el texto es nuestro */

        printf("sacado: %s\n", t);
        free(t);
    }
    printf("quedan:");
    for (const struct nodo *n = l.cabeza; n != NULL; n = n->siguiente)
        printf(" %s", n->texto);
    printf("\n");
    textos_destruir(&l);
    return 0;
}

terminal

$ ./textos
sacado: Ana
sacado: Luis
quedan: Beatriz Carlos
$ valgrind --leak-check=full ./textos 2>&1 | grep -E 'total heap|All heap|ERROR SUMMARY'
  total heap usage: 9 allocs, 9 frees, 4,184 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Agregar copia. El programa usa un solo buffer, buffer, que reutiliza cuatro veces, y aun así la lista guarda cuatro textos distintos, porque textos_agregar hace su propia copia con strdup. La lista es dueña de lo que guarda.
Sacar transfiere. textos_sacar libera el nodo, que es de la lista, pero devuelve el texto sin liberarlo: a partir de ahí es de quien lo pidió, que debe llamar a free, como hace el bucle de main. La documentación de la función lo dice en su comentario. Sin esa frase, el que la usa no tiene forma de saberlo.
Destruir libera lo que queda, y lo hace reutilizando textos_sacar y liberando cada texto, de modo que hay un solo camino para dar de baja un elemento. Un error de creación, como un strdup que falla, deshace la reserva del nodo antes de salir.

La política de prestar es la más barata y la más peligrosa, y el error típico es prestar algo que se reutiliza:

prestamo.c · el mismo buffer, guardado por dirección y por copia

    for (int i = 0; i < MAX; i++) {
        snprintf(buffer, sizeof buffer, "%s", entrada[i]);
        prestados[i] = buffer;            /* error: todos apuntan al mismo arreglo */
        copias[i] = strdup(buffer);
    }

terminal

$ ./prestamo
0: prestado = "Carlos"   copia = "Ana"
1: prestado = "Carlos"   copia = "Luis"
2: prestado = "Carlos"   copia = "Beatriz"
3: prestado = "Carlos"   copia = "Carlos"

Las cuatro entradas «prestadas» apuntan al mismo arreglo, que contiene el último nombre leído: al final, todas dicen «Carlos». Es uno de los errores más comunes al guardar cadenas leídas en un bucle, y ocurre cuando el texto que se guarda es un puntero a un buffer que va a cambiar. Con memoria prestada, quien presta debe garantizar que el dato dure y no cambie; con una variable local reutilizada, no puede. Otra variante del mismo error es prestar un bloque que se libera antes que la estructura: un puntero colgante guardado adentro.

Estas reglas resumen el bloque:

Una estructura de datos documenta su política de propiedad, junto con cada función que agrega o saca: «copia», «presta», «transfiere».
La política por omisión para texto es copiar: es la más segura, y su costo rara vez importa. Prestar se reserva para datos que se sabe que viven más que la estructura, como las cadenas literales.
Destruir recorre todo lo que la estructura posee, primero los elementos y después el contenedor, y no toca lo que no posee.
Un elemento tiene un solo dueño en cada momento. Si el mismo bloque está en dos estructuras que lo liberan, es una doble liberación; si está en una que lo libera y en otra que lo conserva, es un uso después de liberar.
Se prueba con las herramientas: los cinco programas de este tema terminan con tantas liberaciones como reservas y cero errores bajo Valgrind, y con ASan sin informes. Es el criterio de terminado del tema 29.

Con esto termina el bloque de la memoria dinámica. Faltan estructuras más elaboradas, como árboles de búsqueda y tablas de dispersión, que se construyen con las mismas piezas: nodos con punteros, una política de propiedad, y destruir en el orden inverso al de creación. En el siguiente bloque dejamos la memoria y pasamos a la otra mitad de la programación en C para sistemas: cómo se convierten los archivos fuente en un programa, cómo se unen y cómo se organizan en bibliotecas.

9. Errores frecuentes

Error	Qué pasa	Corrección
Guardar un puntero a un elemento de un arreglo dinámico	Un agregado mueve el bloque y el puntero queda colgante.	Guardar el índice.
Crecer el arreglo de a un elemento	Una llamada a `realloc` por elemento.	Duplicar la capacidad.
Confundir cantidad y capacidad	Se lee más allá de los elementos en uso, o se pierde memoria.	Dos campos, con un invariante.
`p = realloc(p, …)` en el vector	Si falla, se pierde el bloque y los datos.	Un puntero temporal.
Olvidar actualizar la cola al quitar el último nodo	La cola apunta a memoria liberada.	Mantener el invariante en cada operación; mostrarlo en las pruebas.
Casos especiales para la cabeza al quitar un nodo	Código largo y propenso a errores.	El puntero a puntero, o un centinela.
`for (n = cabeza; n; n = n->siguiente) free(n);`	Lee `n->siguiente` después de liberar.	Guardar el siguiente antes de `free`.
Liberar una lista con recursión	Un marco de pila por nodo: `Segmentation fault` con listas largas.	Un bucle.
Liberar la cabeza de la lista y creer que es suficiente	Los demás nodos se pierden: fuga.	Recorrer y liberar todos.
Guardar un puntero a un buffer que se reutiliza	Todas las entradas apuntan al último contenido.	Copiar con `strdup`.
El mismo elemento en dos estructuras que lo liberan	Doble liberación.	Un solo dueño; la otra estructura presta.
No documentar quién libera lo que devuelve una función	Fugas o dobles liberaciones en quien la usa.	Comentar la política en cada función.
Usar una lista donde un arreglo bastaba	5 veces la memoria y recorridos 6 a 175 veces más lentos.	Arreglo por omisión; medir.
`contenedor_de` con el campo o el tipo equivocados	Una dirección sin sentido, sin ningún aviso.	Revisar la pareja tipo y campo; probar con ASan.

10. Resumen

Un arreglo dinámico guarda los elementos en un bloque contiguo; una lista enlazada, en un bloque por nodo, unidos por punteros. El arreglo es la opción por omisión; la lista se elige por las inserciones y borrados en los extremos y el medio, o cuando los elementos no deben moverse.
Un arreglo dinámico lleva el puntero, la cantidad y la capacidad, con el invariante cantidad <= capacidad. Crece duplicando la capacidad, con reallocarray y un puntero temporal, y el desborde de la duplicación se comprueba aparte. Sus punteros a elementos se invalidan al crecer; se usan índices.
Una lista simple tiene cabeza y cola; agregar al principio y al final es inmediato. Quitar un nodo con un struct nodo ** evita el caso especial de la cabeza. Invertir cambia los punteros, sin reservar.
Destruir una lista es un bucle que guarda el siguiente antes de liberar. Liberar con recursión agota la pila con listas largas.
La lista cuesta cuatro veces el tamaño de un dato chico, construirla es unas 12 veces más lento, y recorrerla 6 veces más lento si los nodos están contiguos y 175 veces si están dispersos: es la caché.
Una lista intrusiva, circular y doble, con un centinela, pone el enlace dentro del objeto y recupera el objeto con container_of. No tiene casos especiales, hace una reserva por objeto y permite que un objeto esté en varias listas.
Una cola FIFO es una lista con cabeza y cola; una pila es mejor con un arreglo. Un planificador round-robin es una cola de procesos listos.
Cada estructura define y documenta su política de propiedad: copiar (es dueña), prestar (no es dueña) o transferir (cambia el dueño). Un elemento tiene un solo dueño; destruir libera lo que posee, primero los elementos y después el contenedor.
Se verifica con Valgrind y ASan: tantas liberaciones como reservas y cero errores.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

1. ¿Cuándo conviene un arreglo dinámico y cuándo una lista enlazada?

El arreglo conviene por omisión: acceso por índice inmediato, menos memoria y recorridos rápidos. La lista conviene cuando se agrega o quita muy a menudo al principio o en el medio (con la posición a mano), o cuando otras partes del programa guardan punteros a los elementos y estos no deben moverse. Casi siempre, conviene medir antes de decidir.

2. ¿Qué dicen la cantidad y la capacidad de un arreglo dinámico, y por qué se llevan por separado?

La cantidad es cuántos elementos están en uso; la capacidad, cuántos caben en el bloque actual sin pedir más memoria. Se llevan por separado porque el bloque se agranda en saltos, duplicando, y no con cada elemento: la mayoría de los agregados no llaman a realloc, y el costo promedio de agregar es constante.

3. ¿Qué pasa con un puntero a v.datos[3] guardado antes de agregar elementos al vector?

Si el agregado hace crecer el bloque y realloc lo mueve, el puntero queda colgante: apunta al bloque viejo, ya liberado. Es el uso después de liberar del tema 29. Se evita guardando el índice, que sigue valiendo después del movimiento.

4. ¿Para qué sirve el puntero a la cola de una lista simple?

Para agregar al final sin recorrer la lista: cola->siguiente = nuevo es una operación inmediata. Sin él, agregar al final requiere recorrer los n nodos. A cambio, hay que mantenerlo al día en cada operación que pueda cambiar el último nodo, incluido quitar.

5. ¿Cómo evita el puntero a puntero el caso especial de la cabeza al quitar un nodo?

La variable enlace guarda la dirección del puntero que apunta al nodo actual: al principio es &l->cabeza, y después la dirección del campo siguiente del nodo anterior. *enlace = borrado->siguiente modifica ese puntero, sea el de la cabeza o el de un nodo intermedio, con la misma línea.

6. ¿Por qué no se puede liberar una lista con for (n = cabeza; n; n = n->siguiente) free(n);?

Porque la expresión n = n->siguiente se evalúa después de free(n), y lee un campo de un bloque ya liberado: un uso después de liberar. La forma correcta guarda el siguiente en una variable antes de liberar el nodo.

7. ¿Por qué liberar una lista con una función recursiva puede terminar en Segmentation fault?

Porque cada nodo es un nivel de recursión, con su marco en la pila, y la pila tiene un tamaño limitado (8 MiB por omisión). Con marcos de 32 bytes, unas 260 000 llamadas la agotan. Como la lista puede tener la cantidad de elementos que quiera quien usa el programa, la liberación se hace con un bucle.

8. ¿Por qué recorrer una lista con los nodos dispersos puede ser decenas de veces más lento que con los nodos contiguos, si hace el mismo trabajo?

Porque el costo está en los accesos a la memoria, no en la suma. Con los nodos contiguos, la caché y el prefetcher traen por adelantado los siguientes. Con los nodos dispersos, cada n->siguiente cae en un lugar que no está en la caché, y el procesador espera a la memoria principal en cada paso, sin poder adivinar la dirección hasta leer el nodo actual.

9. ¿Qué es una lista intrusiva y qué ventajas tiene sobre la lista de nodos separados?

Es una lista cuyo enlace es un campo del propio objeto: la lista solo maneja enlaces y recupera el objeto con container_of. Requiere una reserva por objeto en lugar de dos, la misma lista sirve para cualquier tipo, y un objeto con varios enlaces puede estar en varias listas a la vez. El núcleo Linux las usa para casi todo.

10. ¿Para qué sirve el centinela en una lista circular doble?

Es un enlace que representa la lista y que hace que todo nodo tenga siempre un anterior y un siguiente, incluso en la lista vacía, donde se apunta a sí mismo. Con él, insertar y quitar son las mismas operaciones para el principio, el medio y el final, sin comprobar casos de borde con NULL.

11. ¿Qué diferencia hay entre las políticas de «copiar», «prestar» y «transferir» la propiedad?

Con «copiar», la estructura guarda una copia propia y la libera al destruirse. Con «prestar», guarda la dirección que le dan y no libera nada: el dato debe vivir y no cambiar mientras lo use. Con «transferir», toma posesión de un bloque que le entregan, o lo entrega a quien lo saca, que pasa a ser su dueño y debe liberarlo.

12. En prestamo.c, ¿por qué las cuatro entradas «prestadas» dicen «Carlos»?

Porque guardan la dirección de buffer, el mismo arreglo en las cuatro vueltas, y el último contenido que se escribió en él fue «Carlos». Las copias con strdup, en cambio, son bloques distintos, uno por entrada. Prestar un buffer que se reutiliza es un error de propiedad: el dato prestado no dura.

13. En el planificador round-robin, ¿qué estructura de datos se usa y por qué?

Una cola FIFO hecha con una lista simple con cabeza y cola. Se saca el proceso de la cabeza, se lo deja correr un quantum y, si no terminó, se lo agrega por la cola. Las dos operaciones son inmediatas y no recorren la lista; el mismo bloque del proceso vuelve a la cola sin copiarse.

Para practicar

Amplía vector.c para guardar double, y después para que guarde elementos de cualquier tipo, recibiendo el tamaño del elemento en vector_iniciar y usando void * y memcpy. ¿Qué se pierde frente a la versión de int?
Agrega a vector.c una función vector_ordenar con qsort (tema 20) y otra vector_buscar con bsearch. ¿Qué precondición tiene la segunda?
Mide cuántas veces se llama a realloc al agregar un millón de elementos al vector, y compara con una versión que crece de a 1000 elementos. ¿Cuál es el costo de memoria sobrante de cada una?
Escribe lista_insertar_ordenado, que inserte un valor en una lista ordenada manteniendo el orden, con el puntero a puntero. Pruébala con la inserción al principio, en el medio y al final, y comprueba que la cola queda bien.
Escribe una lista doblemente enlazada con centinela para int, no intrusiva (con un nodo que contiene el valor y dos punteros), y compárala con enlaces.c: ¿cuántas reservas hay por elemento? ¿Y cuántas líneas de casos especiales se evitan?
Agrega a enlaces.c un segundo enlace, en_pendientes, a struct tarea, y mantén dos listas: todas las tareas y las pendientes. Una tarea terminada sale de la segunda pero no de la primera. ¿Qué hay que cambiar en contenedor_de?
Modifica el planificador para que use un quantum distinto por proceso, o para que los procesos lleguen en momentos distintos (el campo llegada ya está declarado). Calcula el tiempo de espera medio de round-robin con quantum 1, 3 y 100, y explica cómo se comporta con un quantum enorme.
Escribe una pila de cadenas con un arreglo dinámico que sea dueña de sus textos (política de copiar), y úsala para comprobar si los paréntesis de una expresión están balanceados. Verifica el programa con ASan y con Valgrind.