Intrusive Linked Lists

2025-07-12 c++ data-structures

Intrusive linked lists are an alternative implementation of linked lists optimized for fewer memory allocation / copying calls. A standard (‘un-intrusive’) singly linked list is implemented as follows:

#include <iostream>

// Contains the 'business' data that you care about in a node.
struct NodeData
{
    int x{0};
    float y{0.0f};
};

// Datastructure used to organize / bookkeep the underlying
// linked list.
struct ListNode
{
    NodeData* data{nullptr};
    ListNode* next{nullptr};
};

ListNode* create_list_node(int x, float y)
{
    // Allocation #1
    NodeData* new_data = new NodeData();
    new_data->x = x;
    new_data->y = y;

    // Allocation #2
    ListNode* new_node = new ListNode();
    new_node->data = new_data;
    new_node->next = nullptr;
    return new_node;
}

void print_list(ListNode* head)
{
    ListNode* curr = head;
    while (curr != nullptr)
    {
        std::cout << "(" << curr->data->x << "," << curr->data->y << ")" << " -> ";
        curr = curr->next;
    }
    std::cout << "null" << std::endl;
}

int main()
{
  ListNode* n1 = create_list_node(1, 2.0f);
  ListNode* n2 = create_list_node(4, 6.0f);
  n1->next = n2;

  print_list(n1);
  // Assume cleanup is done.
}

The output here would look like:

(1,2) -> (4,6) -> null

The main thing to note are the two allocations in the create_list_node function, since the ListNode and NodeData are two different datastructures the memory is allocated separately for them that leads to two calls to the memory manager. The intrusive linked list collapses this into one call by storing the linked list-specific bookkeeping datastructure within the business data datastructure such that a single call for memory allocation allocates memory for both objects.

#include <iostream>

// Intrusive Linked List node contains both the business data and bookkeeping
// info for the linked list datastructure.
struct IntrusiveLinkedListNode
{
    int x{0};
    float y{0.0f};
    IntrusiveLinkedListNode* next{nullptr};
};

IntrusiveLinkedListNode* create_list_node(int x, float y)
{
    // Allocation #1 
    IntrusiveLinkedListNode* new_node = new IntrusiveLinkedListNode();
    new_node->x = x;
    new_node->y = y;
    new_node->next = nullptr;

    return new_node;
}

void print_list(IntrusiveLinkedListNode* head)
{
    IntrusiveLinkedListNode* curr = head;
    while (curr != nullptr)
    {
        std::cout << "(" << curr->x << "," << curr->y << ")" << " -> ";
        curr = curr->next;
    }
    std::cout << "null" << std::endl;
}


int main()
{
    IntrusiveLinkedListNode* n1 = create_list_node(1, 2.0f);
    IntrusiveLinkedListNode* n2 = create_list_node(4, 6.0f);
    n1->next = n2;

    print_list(n1);
    // Assume cleanup is done.
}

As the create_list_node function implementation shows, a single call to new allocates the memory for the business data and the bookkeeping data. The code here is a simplified here a lot to drive the main point home and a more ‘complete’ implementation of the intrusive linked list can be found in Doom 3’s codebase that shows the common linked list operations implemented.

Tradeoffs

Advantages

  • Fewer memory allocations allows for better performance in cases where node items are being added / removed very rapidly.
  • The code for modifications to the datastructures are branch-free which can allow for better pipelining during execution. No unpredictable branch prediction needed since there are no branches.

Drawbacks

  • Tighter coupling of the NodeData and the ListNode datastructures such that if the same node is in multiple lists, multiple entries would be needed in the IntrusiveListNode struct which couples the different, potentially independent, lists together.
  • The implementation doesn’t really mitigate the drawbacks of linked lists in general, and so std::vector or arrays can be better performing.

Applications

References

Recent Posts