Copy a Java linked chain with random references without retaining aliases

Last updated: 1 Oct 20264 min read

tutorial

Copying a linked chain with random references requires a new Node for every original and a mapping from original identity to copied identity.

Allocate before wiring

Walk the next chain once to allocate copies. A second walk assigns next and random links through an IdentityHashMap. Identity matters: two nodes may have the same label, and equals may have domain behavior unrelated to graph topology. Random links can point backward or forward, so wiring during a single allocation pass can encounter a target not yet copied.

The program rejects a random target outside the next chain. Silently mapping that reference to null would corrupt the copied graph. A different product may need to copy an entire reachable graph instead; that requires graph traversal and an explicit policy for cycles and external objects.

Separate shallow and structural copies

LinkedList.clone copies collection structure but still refers to the same elements. Here each Node object is new while its immutable label string can be shared safely. If payloads were mutable, a full independent copy would also require a payload-copy policy.

The next chain must be acyclic for these two linear walks. Check cycle entry before copying if upstream construction does not enforce it.

Working program

import java.util.IdentityHashMap;

public class CopyDispatchReferences {
    static final class Node {
        final String dispatchId;
        Node next;
        Node random;
        Node(String dispatchId) { this.dispatchId = dispatchId; }
    }
    static Node copy(Node head) {
        IdentityHashMap<Node, Node> copies = new IdentityHashMap<>();
        for (Node cursor = head; cursor != null; cursor = cursor.next)
            copies.put(cursor, new Node(cursor.dispatchId));
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            Node replica = copies.get(cursor);
            replica.next = copies.get(cursor.next);
            if (cursor.random != null && !copies.containsKey(cursor.random))
                throw new IllegalArgumentException("random target outside chain");
            replica.random = copies.get(cursor.random);
        }
        return copies.get(head);
    }
    public static void main(String[] args) {
        Node intake = new Node("intake-47");
        Node audit = new Node("audit-82");
        intake.next = audit;
        intake.random = audit;
        audit.random = intake;
        Node replica = copy(intake);
        System.out.println(replica != intake && replica.next != audit);
        System.out.println(replica.random == replica.next);
        System.out.println(replica.next.random == replica);
    }
}

Output

true
true
true

Cost and ownership

Two next-chain passes take O(n) time. The identity map and copied nodes use O(n) extra memory. The original chain is not mutated; only the immutable label values are reused.

Common Mistakes

Do not key the copy map by payload value when distinct nodes may share a label.
Do not silently erase a random edge whose target lies outside the defined input chain.
Do not describe a node copy as a deep copy of mutable payload objects.