# 3.23 Testing Pointer Code

Pointer code should be tested by checking structure, not only values. A linked list can contain the right values while still having broken links, accidental cycles, stale tails, or shared nodes that should have been detached. Good tests therefore verify both the sequence and the shape of the list.

## Problem

You want to test linked list algorithms such as insertion, deletion, reversal, splitting, merging, and LRU operations.

A weak test checks only this:

```text id="t2h8m5"
values(list) == expected_values
```

A stronger test also checks:

```text id="q9v4r1"
the list terminates
no node appears twice
head and tail are consistent
prev and next agree in a doubly linked list
removed nodes are detached when required
```

## Build Lists from Arrays

A helper function should create a list from a simple sequence.

```text id="x5m1p7"
from_array(values):
  head = null
  tail = null

  for value in values:
    node = Node(value)
    node.next = null

    if head == null:
      head = node
      tail = node
    else:
      tail.next = node
      tail = node

  return head
```

This makes tests short and readable.

```text id="z8r6k3"
head = from_array([1, 2, 3])
```

## Convert Lists to Arrays

Most tests compare the resulting values against an expected array.

```text id="p4y7d2"
to_array(head):
  result = []
  cur = head

  while cur != null:
    result.append(cur.value)
    cur = cur.next

  return result
```

For unsafe input, add a traversal limit or visited set.

```text id="f7n2x9"
to_array_checked(head):
  result = []
  seen = set()
  cur = head

  while cur != null:
    if cur in seen:
      error "cycle detected"

    seen.add(cur)
    result.append(cur.value)
    cur = cur.next

  return result
```

## Check Acyclicity

Many linked list algorithms assume that the list eventually reaches `null`. A test helper should verify that.

```text id="c6b8q1"
assert_acyclic(head):
  seen = set()
  cur = head

  while cur != null:
    if cur in seen:
      error "cycle detected"
    seen.add(cur)
    cur = cur.next
```

This catches accidental cycles caused by incorrect relinking.

## Check Tail Consistency

If a list stores a tail pointer, verify that it matches the last node.

```text id="m9r2v5"
assert_tail(head, tail):
  if head == null:
    assert tail == null
    return

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

  assert cur == tail
  assert tail.next == null
```

A stale tail is a common bug after deleting the last node.

## Check Doubly Linked Structure

For a doubly linked list, forward and backward links must agree.

```text id="h3k7d9"
assert_doubly_linked(head, tail):
  prev = null
  cur = head

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

  assert prev == tail

  next = null
  cur = tail

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

  assert next == head
```

This catches one-sided updates, where `next` is correct but `prev` is stale, or the reverse.

## Test Empty and Small Lists First

Every pointer algorithm should be tested on boundary sizes.

```text id="r1w6m8"
[]
[1]
[1, 2]
[1, 2, 3]
```

These cases expose head updates, tail updates, and off-by-one errors.

## Test Reversal

```text id="u2k5q4"
assert to_array(reverse(from_array([]))) == []
assert to_array(reverse(from_array([1]))) == [1]
assert to_array(reverse(from_array([1, 2]))) == [2, 1]
assert to_array(reverse(from_array([1, 2, 3]))) == [3, 2, 1]
```

Also assert acyclicity after reversal.

```text id="v5c9t1"
head = reverse(from_array([1, 2, 3]))
assert_acyclic(head)
```

## Test Deletion

Deletion tests should cover head, middle, tail, no match, and all removed.

```text id="k8p3d6"
assert to_array(delete_value(from_array([1, 2, 3]), 1)) == [2, 3]
assert to_array(delete_value(from_array([1, 2, 3]), 2)) == [1, 3]
assert to_array(delete_value(from_array([1, 2, 3]), 3)) == [1, 2]
assert to_array(delete_value(from_array([1, 2, 3]), 4)) == [1, 2, 3]
assert to_array(delete_all(from_array([2, 2, 2]), 2)) == []
```

Consecutive matches are especially important.

```text id="d7y1z5"
assert to_array(delete_all(from_array([1, 2, 2, 3]), 2)) == [1, 3]
```

## Test Splitting

Splitting should be tested on odd and even lengths.

```text id="q6n4b2"
left, right = split_half(from_array([1, 2, 3, 4]))
assert to_array(left) == [1, 2]
assert to_array(right) == [3, 4]

left, right = split_half(from_array([1, 2, 3, 4, 5]))
assert to_array(left) == [1, 2, 3]
assert to_array(right) == [4, 5]
```

Also check that the two halves do not remain accidentally connected.

```text id="g9s2x8"
assert_acyclic(left)
assert_acyclic(right)
```

## Test Merging

Merging tests should include empty inputs and unequal lengths.

```text id="x4m8c7"
assert to_array(merge(null, from_array([1, 2]))) == [1, 2]
assert to_array(merge(from_array([1, 3]), null)) == [1, 3]
assert to_array(merge(from_array([1, 3, 5]), from_array([2, 4]))) == [1, 2, 3, 4, 5]
```

For stable merge, use node identity rather than only values.

```text id="p9k5r3"
a1 = Node(1)
a2 = Node(1)
b1 = Node(1)

l1 = chain([a1, a2])
l2 = chain([b1])

merged = merge(l1, l2)

assert merged == a1
assert merged.next == a2
assert merged.next.next == b1
```

## Test Identity When Relinking

If an algorithm promises to relink existing nodes rather than copy values, verify identity.

```text id="f1h7v6"
nodes = make_nodes([1, 2, 3])
head = chain(nodes)

result = reverse(head)

assert result == nodes[2]
assert result.next == nodes[1]
assert result.next.next == nodes[0]
```

This catches implementations that accidentally allocate new nodes.

## Test Detached Nodes

When an operation removes a node and promises to detach it, check its links.

```text id="b4x8m1"
node = delete_and_return_node(list, target)

assert node.next == null
assert node.prev == null   // for doubly linked lists
```

This is important in intrusive lists and manual-memory settings.

## Property Tests

Property-based tests generate many inputs and check invariants.

Examples:

```text id="m2c7q9"
reverse(reverse(list)) has the same values as list
merge(sorted_a, sorted_b) is sorted
length(merge(a, b)) == length(a) + length(b)
split(list) preserves total length
delete_all(x) leaves no node with value x
```

A property test for reversal:

```text id="y8z4d2"
for values in generated_arrays:
  head = from_array(values)
  result = reverse(reverse(head))
  assert to_array(result) == values
  assert_acyclic(result)
```

## Mutation Tests

Pointer code should be tested for mutation side effects.

If an algorithm should not modify input lists, test that the original lists remain unchanged.

```text id="z3f9q6"
a = from_array([1, 3])
b = from_array([2, 4])

result = merge_copy(a, b)

assert to_array(result) == [1, 2, 3, 4]
assert to_array(a) == [1, 3]
assert to_array(b) == [2, 4]
```

If an algorithm is allowed to consume inputs, document that behavior and test the consumed structure accordingly.

## Complexity Checks

Tests should not only validate results. They should also catch accidental quadratic behavior.

For example, queue enqueue without a tail pointer may pass functional tests but fail performance tests.

```text id="v8n5p2"
queue = new Queue()

for i in 1..1_000_000:
  enqueue(queue, i)
```

This should run in linear total time, not quadratic total time.

## Common Failure Modes

A list may contain the correct values but form a cycle. Always check termination after pointer-heavy operations.

A list may be correct forward but broken backward. Doubly linked lists need both directions checked.

A list may return correct values but use copied nodes when the contract says to relink. Check node identity.

A queue or cache may function for many operations but leave a stale tail after removing the last node. Test transitions between empty and non-empty states.

## Key Insight

Testing linked list code requires value checks and structure checks. Values tell you what the user observes. Structure tells you whether the data structure remains valid for the next operation. A robust test suite verifies both.