What is an intrusive linked list?
Short answer: In an intrusive list the link pointers are embedded inside the data structure itself, instead of a separate list node that points to the data. A generic container_of macro recovers the outer structure from the address of the embedded link. No separate allocation is needed per element, an object can be on several lists at once (one embedded link per list), and the same list code works for any type. The Linux kernel's list_head and RTOS kernels use this design.
#include <stddef.h>
#include <stdio.h>
struct list_head { struct list_head *next, *prev; };
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))
static void list_init(struct list_head *h) { h->next = h->prev = h; }
static void list_add_tail(struct list_head *n, struct list_head *h)
{
n->prev = h->prev; n->next = h;
h->prev->next = n; h->prev = n;
}
static void list_del(struct list_head *n)
{
n->prev->next = n->next; n->next->prev = n->prev;
n->next = n->prev = NULL;
}
struct request {
int id;
struct list_head queue_node; /* on the pending queue */
struct list_head all_node; /* on the list of all requests */
};
int main(void)
{
struct list_head pending, all;
list_init(&pending); list_init(&all);
struct request r[3] = { { .id = 10 }, { .id = 20 }, { .id = 30 } };
for (int i = 0; i < 3; i++) { list_add_tail(&r[i].queue_node, &pending); list_add_tail(&r[i].all_node, &all); }
list_del(&r[1].queue_node); /* O(1), no search */
for (struct list_head *p = pending.next; p != &pending; p = p->next)
printf("%d ", container_of(p, struct request, queue_node)->id); /* 10 30 */
printf("\n");
return 0;
}
Advantages: no allocation (works with static objects and pools), O(1) removal given the object (doubly linked, circular with a sentinel head, so no special cases for empty or end), type-generic code, and better cache behaviour (link and data in the same cache line).
Caveats: an object must not be added twice to the same list via the same link; lifetime is the user's responsibility; and you must remove the object from every list before freeing it.