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:

values(list) == expected_values

A stronger test also checks:

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.

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.

head = from_array([1, 2, 3])

Convert Lists to Arrays

Most tests compare the resulting values against an expected array.

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.

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.

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.

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.

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.

[]
[1]
[1, 2]
[1, 2, 3]

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

Test Reversal

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.

head = reverse(from_array([1, 2, 3]))
assert_acyclic(head)

Test Deletion

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

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.

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.

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.

assert_acyclic(left)
assert_acyclic(right)

Test Merging

Merging tests should include empty inputs and unequal lengths.

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.

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.

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.

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:

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:

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.

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.

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.