Data structures

Intrusive Embedded List

4 min read

Introduction

Linked lists are simple on paper: each node points to the next node. In real systems code, that simplicity can become expensive because traversal turns into pointer chasing across memory. Each jump may pull a new cache line, and most of that cache line may be unrelated to the data the loop actually needs.

An intrusive embedded list changes the layout. Instead of allocating a separate node that points back to the payload, the list node lives inside the object being linked. This is common in kernels, embedded software, packet-processing paths, and high-performance runtimes because it improves locality and removes an extra allocation.

The separate node layout

A traditional non-intrusive layout keeps list metadata and payload in different allocations. The node contains list pointers, while the data object contains the useful fields. Traversal first reads the node, then follows the node's data pointer to reach the payload.

typedef struct node {
    struct node *next;
    packet_t *data;
} node_t;

typedef struct packet {
    int len;
    int id;
} packet_t;

Diagram showing separate node objects pointing to packet objects in fragmented memory. — In the separate-node design, the list node and packet payload can live far apart in memory.

Why traversal wastes cache

CPUs fetch memory in cache-line sized chunks, commonly 64 bytes. If the list node and packet are separate allocations, traversing one element can require multiple cache-line fetches: one for the node, another for the data object, and another for the next node.

That means the processor is not just paying for the fields the code reads. It also pulls neighboring bytes that may not help the traversal at all. In a fragmented heap, the result is more cache misses and less useful work per cache line.

Diagram showing multiple cache lines fetched while traversing an external linked list. — Pointer chasing through separate nodes can fetch multiple 64-byte cache lines for one logical list element.

Embedding the node

In an intrusive list, the list node is embedded directly inside the payload structure. The object is still a packet, but it also carries the linkage needed to participate in a list.

typedef struct list_node {
    struct list_node *next;
} list_node_t;

typedef struct packet {
    list_node_t node;
    int id;
    int len;
} packet_t;

With this design, the traversal pointer lands inside the packet object itself. The code can recover the containing object from the address of the embedded node using a container-of style calculation.

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

Diagram showing packet structures with embedded list nodes inside the payload object. — The intrusive design embeds the node inside packet_t, so list metadata and useful packet fields travel together.

Better locality

Once the node and packet fields live together, a traversal can pull the list pointer and useful fields into cache with fewer trips. The cache line still contains extra bytes, but those bytes are more likely to be part of the same object the code is about to inspect.

This is the core performance benefit: fewer allocations, fewer pointer indirections, and a better chance that the data needed by the loop is already near the linkage used by the loop.

Diagram showing fewer cache-line fetches when traversing an intrusive embedded list. — Embedding the node improves locality: traversal metadata and payload fields now sit in the same cache-friendly object.

Tradeoffs

Performance: intrusive lists avoid extra node allocations and reduce pointer chasing.
Ownership: the object owns its list node, so the data type becomes aware of the list implementation.
Flexibility: one object can participate in multiple lists only if it embeds multiple list nodes.
Safety: container-of style code is powerful, but it requires careful type discipline and lifetime management.

Summary

Separate nodes: clean abstraction, but often worse cache locality.
Intrusive nodes: embed the list pointer inside the object being linked.
Cache behavior: fewer pointer jumps can mean fewer wasted cache-line fetches.
Where it shines: kernels, embedded systems, and hot packet-processing paths where allocation and cache behavior matter.