# 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:

```text id="h2j8p4"
Node {
  value : Object
  next  : Node | null
}
```

An intrusive list places the link directly inside the object:

```text id="x7m2q5"
Object {
  data
  next : Object | null
}
```

For a doubly linked intrusive list:

```text id="m5r9c2"
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.

```text id="f6t3n8"
insert_after(cur, obj):
  obj.next = cur.next
  cur.next = obj
```

For a doubly linked list:

```text id="r1v8k6"
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:

```text id="v9c4d1"
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:

```text id="k3m7z9"
every next pointer is either null or points to a live object
```

For a doubly intrusive list:

```text id="q8h2v5"
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

```text id="z1b6n4"
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

```text id="g4k9s7"
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

```text id="t6n1w8"
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.

```text id="p3h8m2"
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

| Feature             | Non-intrusive list | Intrusive list                |
| ------------------- | ------------------ | ----------------------------- |
| Link storage        | Separate node      | Inside object                 |
| Extra allocation    | Usually yes        | No                            |
| Object independence | Higher             | Lower                         |
| Membership tracking | External           | Built into object             |
| Multiple lists      | Easy with wrappers | Requires multiple link fields |
| Memory locality     | Often weaker       | Often stronger                |
| Lifetime risk       | Lower              | Higher                        |

## Use Case: Scheduler Queue

A scheduler may keep runnable tasks in a queue.

```text id="c2v7q1"
Task {
  id
  state
  prev
  next
}
```

The ready queue can link tasks directly.

```text id="y5k1r6"
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.

```text id="u7m6d2"
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

| Operation                         | Time | Extra Space |
| --------------------------------- | ---: | ----------: |
| Insert known object               | O(1) |        O(1) |
| Remove after known predecessor    | O(1) |        O(1) |
| Remove known doubly linked object | O(1) |        O(1) |
| Search                            | O(n) |        O(1) |

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.