# Intrusive Doubly-Linked List (O(1) Splice)
## What It Is
An **intrusive list** stores `prev/next` pointers *inside* the node itself. This makes list operations O(1) without allocating wrapper list nodes.
Used for:
- LRU / MRU ordering (move-to-front on hit)
- Segmented LRU (probation/protected lists)
- ARC/2Q lists (multiple LRU lists)
- “LRU within a bucket” tie-breakers (LFU bucket lists)
## Core Types
You need:
- `Node { prev: Option<Handle>, next: Option<Handle>, ... }`
- `List { head: Option<Handle>, tail: Option<Handle>, len: usize }`
Where `Handle` is one of:
- `NonNull<Node>` (pointer-based)
- `EntryId`/`usize` index into a stable arena/slot vector (recommended)
## Operations (Must Be O(1))
- `push_front(handle)`
- `push_back(handle)`
- `remove(handle)`
- `move_to_front(handle)` (remove + push_front)
- `pop_front()` / `pop_back()`
## Invariants
Maintain these at all times:
- `head.prev == None`
- `tail.next == None`
- For any node `n` in the list:
- if `n.next = Some(m)`, then `m.prev = Some(n)`
- if `n.prev = Some(p)`, then `p.next = Some(n)`
- `len` matches number of nodes reachable from head (debug-only validation is useful)
## Rust Implementation Notes
### Pointer-based (`NonNull<Node>`)
Pros: direct, classic LRU design. Cons: unsafe invariants and lifetime management.
- Nodes must have **stable addresses** (`Box`, arena allocation).
- Never move nodes after linking.
- Always unlink before freeing.
### Index-based (`usize`/`EntryId`)
Pros: usually safe, cache-friendly, easier to test. Cons: requires a stable slot array.
- Store nodes in `Vec<NodeSlot>`; each node stores `prev/next` as indices.
- Removal is purely index manipulation; no raw pointers.
Index-based is a good “generalized DS” because it composes cleanly with `slot-arena.md`.
## Common Pitfalls
- Forgetting to update both sides of a link on remove.
- Double-removing a node (keep an “is_linked” flag or use `Option<Entry>` slots).
- Using `Vec` of nodes without stable slots (reallocation moves nodes; breaks pointer-based lists).
## Testing Tips
- Property-test sequences of operations: push/remove/move/pop.
- Validate invariants after every op in debug builds.
- Include adversarial patterns (remove head/tail/middle repeatedly).