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

cur = head
alias = cur

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

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.

prev = null
cur = head

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

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.

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.

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.

prev.next = cur.next

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

cur.next = null

Detaching helps avoid unintended reuse.

Aliasing in Merging

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

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:

copy nodes
relink nodes

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

Example of copying:

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.

if p == q:

checks whether two pointers refer to the same node.

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.

next = cur.next

2. Detach nodes when moving them between lists.

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

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.

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.