Deep copy a recursive list in Java with circular references

Question

I have the class:

public class Node
{
  private String id;

  private List<Node> children;
}

I need to create a deep copy of a List of it List, but given that there might circular references I was trying implementing the Cloneable interface and overriding the clone method but I keep getting Stackoverflow exception, so I wonder if there is a way to deep copy it that's fast and removes the circular dependencies in the process?

Class using cloneable, when I try to clone and it has circular references I get the error mention about

public class Node implements Cloneable
{
  private String id;

  private List<Node> children;

   @Override
    public Object clone() throws CloneNotSupportedException {
        Node clone = (Node) super.clone();
        if (children != null) {
 
            List<Node> cloneChildren = new ArrayList<>(children.size());
            for (Node child : children) {
                cloneChildren.add((Node) child.clone());
            }
            clone.setChildren(cloneChildren);
        }
        return clone;
    }

    public List<Node> getChildren() {
        return children;
    }

    public void setChildren(List<Node> children) {
        this.children = children;
    }
}

Is `id` guaranteed to be unique for every Node? If so, you can write a copy algorithm that tracks the id and stops if it encounters one it's seen before. — Nick Reed, May 20 '21 at 19:21
"I was trying implementing the Cloneable interface and overriding the clone method but I keep getting Stackoverflow exception" -- please share this code as a [mcve]. — ggorlen, May 20 '21 at 19:24
Well, you could track which nodes you encountered within the recursive visiting of nodes. If the node has already been encountered, skip. For example, `a -> b -> c -> d -> e -> b...` — MC Emperor, May 20 '21 at 22:03

Tom Hawtin - tackline · Answer 1 · 2021-05-20T21:53:03.807

1

The easiest approach is to use an IdentityHashMap<Node,Node> to keep track of previously seen Nodes, mapping Nodes to be copied with Nodes copied thus far.

public Node copy() {
    Map<Node,Node> copied = new IdentityHashMap<>();
    return copy(copied, this);
}
private static Node copy(Map<Node,Node> copied, Node orig) {
    Node existing = copied.get(orig);
    if (existing != null) {
        return existing;
    }
    Node copy = new Node();
    copy.id = orig.id;
    copy.children = new ArrayList<>();
    copied.put(orig, copy);
    for (Node child : orig.children) {
        copy.children.add(copy(copied, child));
    }
    return copy;
}

(As usual, code compiled but not tested.)

I was thinking there is a 'clever' approach using Floyd's Tortoise and Hare Algorithm, but this is complicated by it not being a singly-linked list.

edited May 20 '21 at 21:53

answered May 20 '21 at 19:23

Tom Hawtin - tackline

145,806
30
211
305

How would this work if the node is present but not as a circular dependency? – zepol May 20 '21 at 20:35
This code only works if the class `Node` is effectively final, that is, there is no class that extends `Node`. – Roland Illig May 20 '21 at 22:01
@RolandIllig If you start subclassing `Node` you've got more problems to worry about. Assuming there aren't other opportunities for circularity, you could easily modify this code to use a protected method at the expensive of a larger interface - although I'd go for making the class final. I originally wrote it as a being outside of the `Node` class, only changing it because the OP's class had just private fields. – Tom Hawtin - tackline May 21 '21 at 11:21
@TomHawtin-tackline i tried your solution, but it becomes cyclic again when doing this line `copy.children.add(copy(copied, child));` , it creates the child without the children but when added there it's circular again :\ – zepol May 21 '21 at 16:38
@zepol Do you mean you get the stack overflow again? (Of course, if you copy something cyclic, you expect a cyclic copy.) The following "works for me" `Node a = new Node(); Node b = new Node(); a.children.add(b); b.children.add(a); System.err.println(a.copy());` – Tom Hawtin - tackline May 21 '21 at 18:05
@TomHawtin-tackline that works for me too, but when looping later in the process the cyclic dependency still exists so I get the stack overflow anyway – zepol May 21 '21 at 18:16
@zepol Can you provide a minimal, reproducible example? https://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example – Tom Hawtin - tackline May 21 '21 at 18:39
(Better link for minimal, reproducible example: https://stackoverflow.com/help/minimal-reproducible-example ) – Tom Hawtin - tackline May 21 '21 at 20:08

Deep copy a recursive list in Java with circular references

1 Answers1