# 3.13 Pointer Aliasing

Pointer aliasing occurs when two or more references point to the same node. In linked list algorithms, aliasing is unavoidable. Multiple variables often refer to the same structure during traversal, insertion, deletion, or merging. Correct algorithms treat aliasing as a controlled property. Incorrect algorithms create unintended sharing, which leads to structural corruption.

## Problem

You manipulate a linked list using multiple pointers. Some of these pointers may refer to the same node at the same time. Updates through one reference affect all aliases. You must ensure that such updates preserve the intended structure.

## Basic Example

```text id="a1s9d3"
cur = head
alias = cur
```

Both `cur` and `alias` refer to the same node. Any mutation through one is visible through the other.

```text id="f7k2w8"
cur.next = null
```

After this assignment, `alias.next` is also `null`.

## Controlled Aliasing

Many algorithms rely on temporary aliasing that is safe because the roles of pointers are well defined.

Example: reversal.

```text id="v8z3n2"
prev = null
cur = head
```

During execution, `cur.next` is reassigned. The pointer `next` is used to preserve access to the remainder.

```text id="p6c4x1"
next = cur.next
cur.next = prev
```

Here:

* `cur` and `next` refer to adjacent nodes
* `prev` refers to the reversed prefix

Aliasing is controlled because each pointer has a distinct role and is updated in a fixed order.

## Dangerous Aliasing

Aliasing becomes dangerous when the same node is reachable through multiple paths that the algorithm does not expect.

Example: accidental cycle.

```text id="g4h8t6"
cur.next = head
```

If `cur` is not the tail, this creates a cycle. Traversal will no longer terminate.

Another example: shared suffix between two lists.

```text id="z2j7m5"
l1: a -> b -> c
l2: x -> y -> c
```

Both lists share node `c`. Modifying `c.next` through one list changes the other list as well.

## Aliasing in Deletion

Deletion modifies the link of a predecessor.

```text id="u9r2p6"
prev.next = cur.next
```

If another pointer also references `cur`, that pointer now refers to a detached node.

```text id="s4e1w7"
cur.next = null
```

Detaching helps avoid unintended reuse.

## Aliasing in Merging

During merging, nodes are moved from input lists to the output list.

```text id="q3n5l8"
tail.next = p
p = p.next
```

At this moment, the node just attached is still reachable from its original list unless explicitly detached. In most merge implementations, detachment is implicit because the original list is no longer used. If both structures are used later, this creates shared structure.

## Copy vs Relink

Two approaches exist:

```text id="m7v1c2"
copy nodes
relink nodes
```

Relinking reuses existing nodes and is O(1) space. Copying creates new nodes and avoids aliasing.

Example of copying:

```text id="k8d2r4"
new = Node(cur.value)
tail.next = new
```

This guarantees independence between input and output structures.

## Detecting Aliasing Issues

Symptoms include:

* unexpected cycles
* nodes appearing in multiple lists
* infinite loops during traversal
* lost segments of the list

Debugging often requires checking whether two pointers refer to the same node, not just equal values.

## Identity vs Value

Aliasing concerns identity, not value.

```text id="c9x2q7"
if p == q:
```

checks whether two pointers refer to the same node.

```text id="b6h4z1"
if p.value == q.value:
```

checks only data equality.

Confusing these leads to logical errors, especially in cycle detection and deduplication.

## Safe Patterns

1. Save the successor before modifying a link.

```text id="t5y8u3"
next = cur.next
```

2. Detach nodes when moving them between lists.

```text id="w2f6p9"
cur.next = null
```

3. Maintain clear pointer roles: `prev`, `cur`, `next`.

4. Avoid using a node after it has been removed unless explicitly reattached.

5. Use sentinels to reduce aliasing complexity at boundaries.

## Example: Partition with Detachment

```text id="r1p4v8"
small_dummy = new Node()
large_dummy = new Node()

small_tail = small_dummy
large_tail = large_dummy

cur = head

while cur != null:
  next = cur.next
  cur.next = null

  if cur.value < pivot:
    small_tail.next = cur
    small_tail = cur
  else:
    large_tail.next = cur
    large_tail = cur

  cur = next

small_tail.next = large_dummy.next
```

Detaching ensures that nodes do not carry unintended links into the new structure.

## Complexity

Aliasing does not change asymptotic complexity. It affects correctness.

| Aspect      | Impact                          |
| ----------- | ------------------------------- |
| Time        | unchanged                       |
| Space       | may increase if copying is used |
| Correctness | critical                        |

## Common Failure Modes

* Reusing a pointer after its node has been detached
* Forgetting to detach before reusing nodes
* Comparing values instead of identities
* Creating hidden cycles
* Sharing nodes between independent lists

## Key Insight

Linked lists are graphs, not arrays. Multiple references can point to the same node. Every assignment to `next` changes the graph. Correct algorithms treat pointer assignments as graph rewrites and ensure that the resulting structure remains a valid list with a single path from head to null.