Test Java linked-chain mutations with node-identity invariants

Last updated: 1 Oct 20264 min read

tutorial

A linked-chain mutation test should check node identity, topology, and termination, not only the printed sequence of payloads.

Check topology after each operation

A reversal can print the expected labels while allocating replacement nodes, dropping a duplicate-valued node, or leaving a hidden cycle. Construct chains from distinct Node objects, reverse them, and traverse with an IdentityHashMap so a repeated object is rejected before a test loop can hang. Compare each visited reference with the expected original object.

This fixture enumerates lengths zero through eight, reverses each chain twice, and checks that both passes contain exactly the original nodes in the expected order. The empty and one-node cases matter; they expose root handling that a three-node demonstration can miss.

Know what the fixture does not prove

Nine shapes do not prove correctness for all inputs, nor do they test concurrent mutation or cycles supplied as input. Add larger randomized inputs and independent oracles for release checks. The article demonstrates a focused invariant test for whole-chain reversal, then points to group reversal and deletion for separate contracts.

A step cap protects test execution from a regression that forms a cycle. It is a test guard, not an algorithmic property of the production function.

Working program

import java.util.IdentityHashMap;

public class DispatchChainInvariantCheck {
    static final class Node {
        final int dispatchKey;
        Node next;
        Node(int dispatchKey) { this.dispatchKey = dispatchKey; }
    }
    static Node reverse(Node head) {
        Node previous = null;
        for (Node cursor = head; cursor != null;) {
            Node following = cursor.next;
            cursor.next = previous;
            previous = cursor;
            cursor = following;
        }
        return previous;
    }
    static void assertOrder(Node head, Node[] expected, boolean reversed) {
        IdentityHashMap<Node, Boolean> visited = new IdentityHashMap<>();
        Node cursor = head;
        for (int offset = 0; offset < expected.length; offset++) {
            int expectedIndex = reversed ? expected.length - 1 - offset : offset;
            if (cursor != expected[expectedIndex] || visited.put(cursor, true) != null)
                throw new AssertionError("identity or order changed");
            cursor = cursor.next;
        }
        if (cursor != null) throw new AssertionError("extra node or cycle");
    }
    public static void main(String[] args) {
        for (int size = 0; size <= 8; size++) {
            Node[] original = new Node[size];
            for (int index = 0; index < size; index++) original[index] = new Node(47 + index);
            for (int index = 1; index < size; index++) original[index - 1].next = original[index];
            Node root = size == 0 ? null : original[0];
            Node reversed = reverse(root);
            assertOrder(reversed, original, true);
            assertOrder(reverse(reversed), original, false);
        }
        System.out.println("9 chain lengths checked");
    }
}

Output

9 chain lengths checked

Cost and ownership

Each fixture of n nodes uses O(n) time for construction and each traversal, plus O(n) references in the expected array and identity map. Across the nine fixed lengths, total work is bounded. The production reverse function itself still uses O(1) extra references.

Common Mistakes

Do not use value equality to prove original nodes were retained.
Do not let a test traverse a possibly cyclic result without an identity guard or step bound.
Do not treat a small enumeration as proof of every input contract.