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:

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:

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.

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:

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.

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.

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:

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.

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:

new = Node(cur.value)
append(result, new)

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

Moving reuses the node:

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.

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:

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:

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.

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.