# 3.17 Memory Ownership

Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node. In linked list algorithms, pointer correctness is only one side of the problem. The other side is lifetime correctness: every node that remains linked must be alive, and every node that is removed must still be handled according to the memory model of the language.

## Problem

You have a linked list whose nodes are allocated dynamically. You need to update the structure without leaking nodes, freeing live nodes, or leaving dangling pointers.

Common ownership questions are:

```text id="av61up"
Who allocated this node?
Who is allowed to unlink it?
Who is responsible for freeing it?
Can another list still reference it?
Can another pointer still observe it?
```

The answer depends on the language and data structure design.

## Ownership in Garbage-Collected Languages

In a garbage-collected language, removed nodes are reclaimed automatically after they become unreachable.

Deletion may look like this:

```text id="tgvto1"
prev.next = cur.next
cur.next = null
```

The assignment `cur.next = null` is not required for memory reclamation in all cases, but it is often useful because it detaches the node cleanly. It prevents accidental traversal through a removed node and may allow the suffix to be reclaimed sooner if no other reference exists.

The list does not explicitly free memory. It only controls reachability.

## Ownership in Manual-Memory Languages

In a language with manual memory management, unlinking and freeing are separate operations.

```text id="x36mgl"
node = prev.next
prev.next = node.next
node.next = null
free(node)
```

The safe order is:

1. Save the node to be deleted.
2. Preserve access to the suffix.
3. Rewire the predecessor.
4. Detach the removed node.
5. Free the removed node.

Freeing before rewiring can leave the list pointing to freed memory.

## Ownership in RAII Languages

In languages with RAII or affine ownership, such as C++ with smart pointers or Rust, the type system may encode ownership constraints.

A list using unique ownership has this conceptual shape:

```text id="jb8l6i"
Node owns next
List owns head
```

Removing a node transfers ownership out of the list. The removed node is destroyed when no owner remains.

This model prevents many use-after-free bugs, but it also makes pointer manipulation more explicit. The algorithm must move ownership rather than merely copy pointers.

## Borrowed References

A borrowed reference observes a node but does not own it.

```text id="go9vau"
cur = head   // borrowed traversal pointer
```

Borrowed references are useful for traversal, but they become unsafe if the underlying node is removed or freed during traversal.

A safe mutation loop must avoid keeping stale borrowed references after unlinking.

```text id="0nq78p"
next = cur.next
remove(cur)
cur = next
```

The pointer `next` must be obtained before `cur` is invalidated.

## Shared Ownership

Shared ownership allows multiple references to keep a node alive. This can prevent premature destruction, but it introduces other risks.

Common issues include:

```text id="kdj68e"
cycles that prevent reclamation
unclear mutation authority
hidden sharing between lists
expensive reference counting
```

A doubly linked list with shared ownership in both directions can easily create a reference cycle. Many implementations use strong ownership in one direction and weak references in the other.

## Ownership and Aliasing

Ownership answers "who may destroy this node." Aliasing answers "who can observe this node."

Both matter.

A node may have one owner but many observers. If the owner removes and destroys the node while observers still hold references, those observers become invalid.

A node may also have multiple logical owners through shared references. Then mutation can affect all owners unless the structure is immutable or copy-on-write.

## Moving Nodes Between Lists

When moving a node from one list to another, the operation must transfer ownership and clear old links.

```text id="9orx4y"
next = cur.next

old_prev.next = next
cur.next = null

new_tail.next = cur
new_tail = cur
```

The node must not remain reachable from the old list and the new list unless sharing is intentional.

## Copying vs Moving

Two designs avoid different classes of bugs.

Copying creates a new node:

```text id="yka9s4"
new = Node(cur.value)
append(result, new)
```

The original list remains unchanged. Ownership stays simple, but memory use increases.

Moving reuses the node:

```text id="sohm68"
detach(cur)
append(result, cur)
```

This saves memory but requires strict ownership transfer.

## Destructor Rules

If a list owns all its nodes, destroying the list must destroy every node reachable from `head`.

```text id="6zecj4"
cur = head

while cur != null:
  next = cur.next
  cur.next = null
  free(cur)
  cur = next

head = null
```

Saving `next` before freeing `cur` is mandatory. After `cur` is freed, reading `cur.next` is invalid.

## Ownership Invariants

A linked list with exclusive ownership should maintain:

```text id="exr3ur"
Every live node is owned by exactly one list or exactly one external owner.
Every linked node is live.
No freed node is reachable from the list.
No node is freed twice.
```

An intrusive list uses a different invariant:

```text id="w10bal"
The list links objects, but does not necessarily own their lifetime.
Every linked object must outlive its membership in the list.
```

## Complexity

Ownership rules do not change asymptotic bounds, but they change implementation cost.

| Operation    | Time | Extra Space | Ownership concern      |
| ------------ | ---: | ----------: | ---------------------- |
| Delete node  | O(1) |        O(1) | Who frees the node     |
| Move node    | O(1) |        O(1) | Transfer ownership     |
| Copy node    | O(1) |        O(1) | Duplicate value safely |
| Destroy list | O(n) |        O(1) | Free every node once   |

## Common Failure Modes

A use-after-free occurs when code reads or writes a node after it has been freed.

A memory leak occurs when a node becomes unreachable without being freed in a manual-memory language.

A double free occurs when the same node is destroyed twice.

A dangling link occurs when a list still points to a freed node.

A hidden ownership bug occurs when two lists both believe they own the same node.

## Key Insight

Pointer manipulation preserves structure. Ownership management preserves lifetime. A linked list algorithm is correct only when both are correct. Each update must answer two questions: which links change, and which component owns each node after the change.