A simple intrusive linked list

September 13, 2021

Linked lists aren't necessarily the first data structure you might reach for, but if you need them, it's nice to not have to keep reimplementing the structures and operations. An intrusive linked list is a minimal list structure which is embedded in other structures to link them. The greater structure can be recovered from the list address using basic pointer arithmetic and the offsetof macro, but the list operations only need to operate on the list structure.

To illustrate, here is a simple singularly-linked-list.

#include <stddef.h>

#define list_item(list, type, member) ((type*)((char*)(list) - offsetof(type, member)))

struct list
{
    struct list* next;
};

static inline void
list_push(struct list* item, struct list** head)
{
    item->next = *head;
    *head = item;
}

static inline struct list*
list_pop(struct list** head)
{
    struct list* old = *head;

    if (old)
    {
        *head = old->next;
        old->next = NULL;
    }

    return old;
}

Notice how all the core list operations only need to operate on struct list. To illustrate the basic use, here is a simple driver:

#include <stdio.h>

#include "list.h"

#define ARRAY_LENGTH(a) sizeof(a) / sizeof((a)[0])

struct intlist
{
    int x;
    struct list list;
};

struct intlist nodes[] = {
    { .x = 1 },
    { .x = 2 },
    { .x = 3 },
};

int
main(int argc, char* argv[])
{
    struct list* head = NULL;

    // Link the nodes with the embeded list structure
    for (size_t ix = 0; ix < ARRAY_LENGTH(nodes); ++ix)
    {
        list_push(&nodes[ix].list, &head);
    }

    // Iterate over the nodes
    for (struct list* iter = head; iter != NULL; iter = iter->next)
    {
        printf("LIST ITEM: %ld\n", list_item(iter, struct intlist, list)->x);
    }

    // Illustrate removing nodes
    while (head)
    {
        printf("REMOVING: %ld\n", list_item(list_pop(&head), struct intlist, list)->x);
    }

    return 0;
}

which produces

LIST ITEM: 3
LIST ITEM: 2
LIST ITEM: 1
REMOVING: 3
REMOVING: 2
REMOVING: 1