Estructuras enlazadas: listas, árboles y container_of

Un array es una decisión que tomas una vez: tamaño fijo, memoria contigua. Una estructura enlazada es lo contrario: nodos dispersos cosidos por punteros, que crecen sin límite y se reordenan cambiando direcciones en vez de moviendo datos. Aquí construimos listas y árboles, y luego damos el salto que da el kernel de Linux: invertir la relación entre el nodo y el dato para obtener genéricos con coste cero.

Del array a la lista

Un nodo de lista es un dato más una dirección: la del siguiente nodo. El último apunta a nulo, y eso marca el final.

typedef struct Nodo {
    int          dato;
    struct Nodo *siguiente;     // el nombre de la struct hace falta aqui
} Nodo;

Nodo *insertar_frente(Nodo *cabeza, int valor) {
    Nodo *n = malloc(sizeof *n);
    if (!n) return cabeza;
    n->dato = valor;
    n->siguiente = cabeza;      // engancha lo que habia
    return n;                   // la nueva cabeza
}

for (Nodo *p = cabeza; p != nullptr; p = p->siguiente)
    printf("%d ", p->dato);

El intercambio frente al array es nítido: insertar o borrar en cualquier posición cuesta tiempo constante una vez tienes el puntero, pero pierdes el acceso indexado y, sobre todo, pierdes la localidad. Recorrer un millón de nodos dispersos por el heap puede ser un orden de magnitud más lento que recorrer un array del mismo tamaño, porque cada salto es un fallo de caché potencial. La estructura de datos elegante en la pizarra no siempre gana en el hardware real.

Árboles: dos punteros y recursión

Cambia un enlace por dos y tienes un árbol. La estructura se vuelve recursiva y, con ella, los algoritmos.

typedef struct Arbol {
    int           clave;
    struct Arbol *izq, *der;
} Arbol;

// insercion con doble puntero: sin caso especial para la raiz vacia
void insertar(Arbol **enlace, int clave) {
    while (*enlace) {
        Arbol *n = *enlace;
        enlace = (clave < n->clave) ? &n->izq : &n->der;
    }
    Arbol *nuevo = malloc(sizeof *nuevo);
    if (!nuevo) return;
    *nuevo = (Arbol){ .clave = clave };     // izq y der quedan a nullptr
    *enlace = nuevo;
}

void en_orden(const Arbol *a) {
    if (!a) return;
    en_orden(a->izq);
    printf("%d ", a->clave);
    en_orden(a->der);
}

Reaparece el patrón de la lección anterior: al guardar el puntero que hay que escribir en vez del nodo padre, el árbol vacío deja de ser un caso aparte. Y observa la inicialización compuesta *nuevo = (Arbol){ .clave = clave };, que pone a cero todo lo no mencionado: es la forma disciplinada de no dejar punteros con basura.

El giro intrusivo del kernel

Hasta aquí, cada estructura de datos define su propio nodo, y por tanto una lista de Persona y una de Tarea necesitan dos implementaciones o una genérica con void *. Linux hace algo mucho más astuto: incrusta el enlace dentro del objeto y escribe la lista una sola vez, sobre el enlace.

/* include/linux/list.h, esencia */
struct list_head { struct list_head *next, *prev; };

struct tarea {
    int              prioridad;
    char             nombre[32];
    struct list_head lista;      /* el enlace vive DENTRO del objeto */
};

La lista no contiene tareas: contiene list_head. Todas las operaciones —insertar, borrar, recorrer— manipulan solo list_head y por tanto están escritas una vez, en C normal y corriente, sin void * y sin castes. Es una lista intrusiva: el nodo no envuelve al dato, el dato aloja al nodo.

flowchart LR
H[head list_head] --> A[list_head dentro de tarea A]
A --> B[list_head dentro de tarea B]
B --> C[list_head dentro de tarea C]
C --> H
style H fill:#89b4fa,color:#11111b
style C fill:#a6e3a1,color:#11111b

Las ventajas son sustanciales, y conviene enumerarlas por separado.

El problema, claro, es el camino de vuelta: teniendo un struct list_head *, ¿cómo recuperas la struct tarea que lo contiene?

container_of: del enlace al objeto

Con aritmética de direcciones y una constante que el compilador conoce. offsetof, de stddef.h, da el desplazamiento en bytes de un miembro dentro de su estructura; restarlo de la dirección del miembro devuelve la dirección del contenedor.

#include <stddef.h>

#define container_of(ptr, tipo, miembro) \
    ((tipo *)((char *)(ptr) - offsetof(tipo, miembro)))

struct tarea *t = container_of(enlace, struct tarea, lista);

Todo ocurre en tiempo de compilación salvo una resta de entero, que el optimizador suele plegar dentro del direccionamiento de la instrucción siguiente: coste cero en tiempo de ejecución. El kernel añade una comprobación de tipos con typeof, disponible ya como palabra estándar en C23, para que el compilador rechace un ptr cuyo tipo no coincida con el del miembro.

/* variante con verificacion de tipos, al estilo del kernel */
#define container_of(ptr, tipo, miembro) ({            \
    const typeof(((tipo *)0)->miembro) *__m = (ptr);   \
    (tipo *)((char *)__m - offsetof(tipo, miembro));   \
})

Sobre esa base se construye el recorrido idiomático, que devuelve directamente objetos y no enlaces:

#define list_for_each_entry(pos, head, miembro)                        \
    for (pos = container_of((head)->next, typeof(*pos), miembro);      \
         &pos->miembro != (head);                                      \
         pos = container_of(pos->miembro.next, typeof(*pos), miembro))

struct tarea *t;
list_for_each_entry(t, &cola, lista)
    printf("%s\n", t->nombre);

La misma técnica sostiene los árboles rojo-negro del kernel (struct rb_node), las tablas hash (struct hlist_node) y los contadores de referencias (struct kref): un enlace incrustado, una macro de recuperación y una implementación única para todos los tipos.