Singly, Doubly & Intrusive Linked Lists (Linux Kernel list_head)

Pointer-to-Pointer (Node**) & Circular Sentinel Elimination

In a naive singly or doubly linked list, every insertion or deletion checks a special-case branch: if (prev == nullptr) head = curr->next; else prev->next = curr->next;. As Linus Torvalds famously demonstrated, there are two complementary techniques that completely eliminate special-case boundary branches:

1. Indirect Pointer-to-Pointer (Node** pp = &head) for Singly Linked Lists: Instead of tracking a predecessor node pointer Node* prev, track the address of the pointer field that points to the current node: Node** indirect = &head. Advancing moves to indirect = &((*indirect)->next), and unlinking the target node executes *indirect = (*indirect)->next uniformly—whether the node is the head of the list or in the middle!
2. Circular Dummy Sentinel Node for Doubly Linked Lists: By maintaining a permanent sentinel node sentinel initialized to point to itself (sentinel.next = sentinel.prev = &sentinel), the list is never physically empty. Every real node sits strictly between two valid Node structs (sentinel.next is front(), sentinel.prev is back()), reducing insert_between(prev, next, node) and unlink(node) to 4 and 2 unconditional pointer stores respectively.

Non-Intrusive vs. Intrusive vs. Arena-Indexed Linked Lists

Visualizing Non-Intrusive Heap Scattering vs. Intrusive container_of

Circular Sentinel Doubly Linked List Splice & Unlink

Production Implementation: Intrusive Circular Doubly Linked List & Torvalds Indirect Unlink

#include <cstddef>
#include <cstdint>

// Linux-kernel style intrusive circular doubly-linked list hook
struct IntrusiveListNode {
  IntrusiveListNode* next = this;
  IntrusiveListNode* prev = this;

  void init() noexcept { next = prev = this; }
  bool empty() const noexcept { return next == this; }

  static void link_between(IntrusiveListNode* prev_node,
                           IntrusiveListNode* next_node,
                           IntrusiveListNode* new_node) noexcept {
    new_node->next = next_node;
    new_node->prev = prev_node;
    next_node->prev = new_node;
    prev_node->next = new_node;
  }

  // Insert new_node right before this (if this is sentinel head, this is push_back!)
  void push_back(IntrusiveListNode* new_node) noexcept {
    link_between(this->prev, this, new_node);
  }

  // Insert new_node right after this (if this is sentinel head, this is push_front!)
  void push_front(IntrusiveListNode* new_node) noexcept {
    link_between(this, this->next, new_node);
  }

  // Branchless O(1) self-unlink!
  void unlink() noexcept {
    next->prev = prev;
    prev->next = next;
    next = prev = this;
  }
};

// Compile-time offset arithmetic (C++ equivalent of Linux kernel container_of)
#define CONTAINER_OF(ptr, Type, member)   reinterpret_cast<Type*>(reinterpret_cast<char*>(ptr) - offsetof(Type, member))

// Linus Torvalds's branchless pointer-to-pointer singly linked list removal
struct SinglyNode {
  int val;
  SinglyNode* next;
};

void remove_first_matching(SinglyNode** head_ref, int target) noexcept {
  SinglyNode** indirect = head_ref;
  while (*indirect != nullptr) {
    if ((*indirect)->val == target) {
      *indirect = (*indirect)->next; // Works identically for head node and interior nodes!
      return;
    }
    indirect = &((*indirect)->next);
  }
}