java.util.ConcurrentModificationException while merge node in a tree structure

Question

I want to merge the node which has the same name, and add their children together. But I got a java.util.ConcurrentModificationException exception:

Exception in thread "main" java.util.ConcurrentModificationException    
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)   
at java.util.ArrayList$Itr.next(Unknown Source)     
at test.Test.mergeNode(Test.java:60)    
at test.Test.main(Test.java:43)

Following is the source.Could someone give any hints? Any suggestions will be welcomed.

public class Test {
    public static void main(String[] args) throws Exception {

        TreeLayoutNode root = new TreeLayoutNode();
        root.setName("Production");

        TreeLayoutNode node1 = new TreeLayoutNode();
        node1.setName("node1");

        TreeLayoutNode node2 = new TreeLayoutNode();
        node2.setName("node1");

        TreeLayoutNode child1 = new TreeLayoutNode();
        child1.setName("child1");

        TreeLayoutNode child2 = new TreeLayoutNode();
        child2.setName("child2");

        TreeLayoutNode child3 = new TreeLayoutNode();
        child3.setName("child3");

        root.addChildNode(node1);
        root.addChildNode(node2);

        node1.addChildNode(child1);
        node1.addChildNode(child2);

        node2.addChildNode(child1);
        node2.addChildNode(child3);

        HashMap<String, TreeLayoutNode> nodeMap = Maps.newHashMap();
        mergeNode(root, nodeMap);

    }

    /**
     * 
     * @param node
     */
    private static void mergeNode(TreeLayoutNode node, HashMap<String, TreeLayoutNode> nodeMap) {
        List<TreeLayoutNode> children = node.getChildren();

        if(CollectionUtils.isEmpty(children)){
            return;
        }

        Iterator<TreeLayoutNode> it = children.iterator();
        while(it.hasNext()){
            TreeLayoutNode child = it.next();
            if(nodeMap.containsKey(child.getName())){
                TreeLayoutNode duplicate = nodeMap.get(child.getName());
                List<TreeLayoutNode> childrenOfChild = child.getChildren();
                if(CollectionUtils.isNotEmpty(childrenOfChild)){
                    for(TreeLayoutNode single: childrenOfChild){
                        duplicate.addChildNode(single);
                    }
                    node.removeChildNode(child);
                    mergeNode(duplicate, nodeMap);
                }
            }else{
                nodeMap.put(child.getName(), child);
            }
        }
    }
}

public class TreeLayoutNode {

    private String name;

    private String parent;

    private Long capacity;

    private List<Proportion> proportions;

    private List<TreeLayoutNode> children;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getParent() {
        return parent;
    }

    public void setParent(String parent) {
        this.parent = parent;
    }

    public Long getCapacity() {
        return capacity;
    }

    public void setCapacity(Long capacity) {
        this.capacity = capacity;
    }

    public List<Proportion> getProportions() {
        return proportions;
    }

    public void setProportions(List<Proportion> proportions) {
        this.proportions = proportions;
    }

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

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

    public void addChildNode(TreeLayoutNode child) {
        if (children == null) {
            children = Lists.newArrayList();
        }

        child.setParent(this.getName());
        children.add(child);
    }

    public void removeChildNode(TreeLayoutNode child){
        children.remove(child);
    }

    public void addProportion(Proportion proportion) {
        if (proportions == null) {
            proportions = Lists.newArrayList();
        }
        proportions.add(proportion);
    }

    public int hashCode() {
        return name == null ? 0: name.hashCode();
    }

    public boolean equals(Object o) {
        if (o instanceof TreeLayoutNode) {
            TreeLayoutNode target = (TreeLayoutNode) o;
            if (this.name == null) {
                return target.getName() == null;
            } else {
                return this.name.equals(target.getName());
            }
        } else {
            return false;
        }
    }
}  

Answer 1

Iterator<TreeLayoutNode> it = children.iterator();
while(it.hasNext()){
    TreeLayoutNode child = it.next();
    if(nodeMap.containsKey(child.getName())){
        TreeLayoutNode duplicate = nodeMap.get(child.getName());
        List<TreeLayoutNode> childrenOfChild = child.getChildren();
        if(CollectionUtils.isNotEmpty(childrenOfChild)){
            for(TreeLayoutNode single: childrenOfChild){
                duplicate.addChildNode(single);
            }
            node.removeChildNode(child);
            mergeNode(duplicate, nodeMap);
        }
    }else{
        nodeMap.put(child.getName(), child);
    }
}

This loop is the problem in your code. When you are using an Iterator, you can not modify the underlying Collection. In this case you are iterating over 'children' in this loop, and you are removing items from the underlying list when you call 'node.removeChildNode( child )'.

A solution is to clone the 'children' list before you iterator over it.

List< TreeLayoutNode > children = node.getChildren().clone();

This means you are no longer iterating over the list that is being edited in the later on in the method.

You could also create another List to store children nodes to be removed after you are done iterating over it.

List< TreeLayoutNode > removedChildren = new LinkedList< >();
// Iterate over the elements, adding children to be removed to removedChildren
for( TreeLayoutNode child : removedChildren ) {
    node.removeChildNode( child );
}

Finally you could use 'it.remove()' to remove the element from the underlying Collection. This method has the disadvantage of breaking encapsulation.

// node.removeChildNode( child )
it.remove();