3.16 Intrusive Lists

An intrusive list stores the linkage fields inside the objects being linked. Instead of allocating a separate wrapper node that contains a value, each object contains its own next pointer, or both prev and next pointers for a doubly linked list.

This design is common in kernels, memory allocators, schedulers, game engines, and low-level systems where allocation, ownership, and memory layout must be controlled carefully.

Problem

You want to maintain a list of existing objects without allocating separate list nodes.

A non-intrusive list usually looks like this:

Node {
  value : Object
  next  : Node | null
}

An intrusive list places the link directly inside the object:

Object {
  data
  next : Object | null
}

For a doubly linked intrusive list:

Object {
  data
  prev : Object | null
  next : Object | null
}

The object itself is the node.

Core Idea

In an intrusive list, list membership is part of the object representation. This means insertion and deletion do not allocate a wrapper node. They only update fields already present in the object.

insert_after(cur, obj):
  obj.next = cur.next
  cur.next = obj

For a doubly linked list:

insert_between(left, right, obj):
  obj.prev = left
  obj.next = right
  left.next = obj
  right.prev = obj

Ownership Model

The list does not own the object in the same way that a wrapper list might own its node. The object may be created and destroyed elsewhere.

This is the main design constraint:

an object must outlive its membership in the list

If an object is freed while it is still linked, the list contains a dangling pointer.

Invariant

For a singly intrusive list:

every next pointer is either null or points to a live object

For a doubly intrusive list:

if x.next != null, then x.next.prev == x
if x.prev != null, then x.prev.next == x

The list is valid only while all linked objects remain alive.

Insert at Head

obj.next = head
head = obj

If the object may already be in a list, check or clear its links first. In many systems, inserting a linked object twice is a structural error.

Remove After a Node

remove_after(prev):
  obj = prev.next
  if obj == null:
    return null

  prev.next = obj.next
  obj.next = null
  return obj

Clearing obj.next makes it easier to detect accidental reuse.

Remove a Known Node in a Doubly Intrusive List

remove(obj):
  left = obj.prev
  right = obj.next

  if left != null:
    left.next = right
  else:
    head = right

  if right != null:
    right.prev = left
  else:
    tail = left

  obj.prev = null
  obj.next = null

This is O(1) because the object stores its predecessor.

Multiple List Membership

An object can belong to multiple intrusive lists only if it has separate link fields for each list.

Task {
  id
  ready_prev
  ready_next
  timer_prev
  timer_next
}

One pair of links belongs to the ready queue. Another pair belongs to the timer queue. Reusing the same prev and next fields for two lists corrupts both lists.

Non-Intrusive vs Intrusive

Use Case: Scheduler Queue

A scheduler may keep runnable tasks in a queue.

Task {
  id
  state
  prev
  next
}

The ready queue can link tasks directly.

push_ready(task):
  task.prev = tail
  task.next = null

  if tail != null:
    tail.next = task
  else:
    head = task

  tail = task

No allocation is needed when a task becomes runnable. The task already contains its queue links.

Use Case: Memory Allocator Free List

A memory allocator may link free blocks directly through metadata stored in each block.

Block {
  size
  next_free
}

When a block becomes free, it is inserted into a free list. When it is allocated again, it is removed. This avoids separate bookkeeping allocations.

Complexity Summary

The savings are in allocation and memory layout, not asymptotic complexity.

Common Failure Modes

The most serious bug is freeing an object while it is still linked. This leaves dangling references inside the list.

A second common bug is inserting the same object twice. If the same link fields are used twice, the list may form a cycle or lose a segment.

A third bug is using one set of link fields for multiple lists at the same time. Each active membership needs its own link fields.

Another common issue is forgetting to clear links after removal. Stale links make later membership checks unreliable.

Key Insight

An intrusive list treats the object as the node. This removes wrapper allocation and improves control over memory layout, but it moves responsibility to the caller. The algorithm must maintain both structural correctness and object lifetime correctness.