How do you implement a correct deep copy of an object graph that contains cycles and objects referenced from more than one place?

### The problem in concrete terms A deep copy of `root` means: produce `root'` such that the subgraph reachable from `root'` is structurally the same as that from `root`, but shares no mutable object with it. Two graph features break the obvious recursive implementation. **1. Cycles.** `a.next = b; b.prev = a`. Copying `a` copies `b`, which copies `a`, which copies `b`… → infinite recursion, stack overflow. **2. Diamonds (shared references).** `a.left = c; a.right = c` — one `c` reachable by two paths. Naive recursion copies `c` twice, so `a'.left !== a'.right`. Nothing crashes; the copy simply has *different sharing structure* than the original. Later, `a'.left.set(...)` no longer shows up in `a'.right`, and behaviour diverges from the original in a way that is very hard to trace back to the clone. So correctness has two requirements: **terminate**, and **preserve the sharing topology** — equal-by-identity originals must map to equal-by-identity copies. ### The identity map algorithm ``` function deepCopy(obj, seen): # seen: identity-keyed map original -> copy if obj is null or immutable: return obj if seen.contains(obj): return seen.get(obj) # (A) cycle + sharing fix copy = allocateEmptyLike(obj) # shell, no fields yet seen.put(obj, copy) # (B) BEFORE recursing for each field f in obj: copy.f = deepCopy(obj.f, seen) return copy ``` The two load-bearing lines are (A) and (B). Line (B) must come *before* the field loop; if you fill fields first and register afterwards, a cycle re-enters before the entry exists and you are back to infinite recursion. This requires the ability to allocate an object without fully initializing it — hence why generic deep-copy utilities bypass constructors, and why constructor-based copying (`new Node(deepCopy(child))`) cannot handle cycles without a two-phase approach: allocate all shells, then link them. ### Identity, not equality The map must key on **reference identity** ("is this the same object?"), not on user-defined equality ("do these look the same?"). If two distinct nodes are `equal` by value, an equality-keyed map treats them as one and the copy collapses them into a single shared node — a subtle structural corruption. Languages provide this as identity hash maps / reference-equality dictionaries. A second reason: user-defined equality on a cyclic structure may itself recurse forever, or may depend on fields not yet filled in during copying. ### Depth and stack A 100 000-node linked list will overflow the call stack. The fix is to make the traversal iterative: 1. Push `root` on a work stack. 2. Pop an object; if unseen, allocate its shell, register it, and push its referenced objects. 3. Second pass (or same pass, filling by looking up the map): assign each copy's fields from the map. The two-phase "allocate all shells, then wire them" formulation is often clearer than one-phase recursion and is naturally cycle-safe. ### What still must be decided per field The identity map solves *structure*; it does not solve *policy*. You still choose which references to follow at all: - **Immutable values** → return as-is; no need to copy, and skipping them keeps the map small. - **Shared services** (logger, connection pool, configuration) → share, do not follow. A generic deep copier that follows every reference will happily clone half the application, because a single back-reference to a container or context object makes the entire heap reachable. This is the number-one practical failure of "just deep copy everything". - **External resources** (sockets, file handles, locks, threads) → cannot be copied; share, reset, or refuse. - **Identity fields** → reset after copying. A good implementation therefore combines the identity map with a **cut set**: an explicit rule for where the copy stops. Without a cut set, transitive reachability makes deep copy unbounded in practice. ### Cost Time and space are O(nodes + edges) in the copied region, plus the map itself (one entry per copied node). Deep copying inside a hot loop is a common performance surprise; if you need it often, consider copy-on-write or immutable/persistent structures, which give independence without traversal. ### Testing it Three assertions catch nearly everything: 1. Mutate any part of the copy → the original is unchanged (and vice versa). 2. Sharing preserved: if `a.left === a.right` in the original, then `a'.left === a'.right` in the copy. 3. Cyclic input terminates and the cycle is reproduced: `a'.next.prev === a'`.