We have this class

public class A {

    private String someVariable;
    private List<A> innerObjects;

    /**
    * setters & getters...
    *
    */
}

Assuming that we do not know how many objects there are inside innerObjects how can we iterate this object manually in an optimal way? The main issue would be on the inner list because it might also have another list and another one and another one and so on...

CodePudding user response：

You cannot iterate a list more efficiently than O(n) that's for sure.

Therefore you can just create a method to iterate the list and do something (basically you can even provide there a function that is implementing your business logic) and if the inner A contains a list then recursively call again the method on the object

A simple example of such method could be:

String concatenateAllVariables(String current) {
    if(innerObjects != null) { // this and the fact loop won't start when the list will be empty is our "stop condition"
        for(A a: innerObjects) {
            current  = a.concatenateAllVariables(""); // this is recursive call
        }
    }
    current  = someVariable; // where this line (before or after processing children) shoud be is due to traversal algorithm
    return current;
}

Read also:

• What is recursion
• Java Pass Method as Parameter
• Traversing through all nodes of a binary tree in Java - because in general you can treat every A instance as some abstract tree node and it's list as it's children (this structure looks a little bit like B-tree)

CodePudding user response：

To visit each nested node, you can do a tree traversal. There are several traversal orders to choose from:

• depth first, pre-order
• depth first, post-order
• breadth first
• ...

Here is some sample code for depth-first, pre-order printing of those someVariable strings, each indented by the depth in the tree, and another function that performs a deep copy of the entire object structure:

import java.util.*;

public class A {
    private String someVariable;
    private List<A> innerObjects;

    public A(String text) {
        someVariable = text;
        innerObjects = new ArrayList<A>();
    }

    public A add(String text) {
        return add(new A(text));
    }

    public A add(A object) {
        innerObjects.add(object);
        return object;
    }

    public A deepCopy() {
        A object = new A(someVariable);
        for (A inner : innerObjects) {
            object.add(inner.deepCopy());
        }
        return object;
    }

    public void deepPrint() {
        deepPrint("");
    }
    public void deepPrint(String prefix) {
        System.out.printf("%s%s\n", prefix, someVariable);
        for (A object : innerObjects) {
            object.deepPrint(prefix   "  ");
        }
    }
}

And some driver code to test this:

    public static void main(String[] args) {
        A root = new A("world");
        A europe = root.add("Europe");
        europe.add("Germany");
        europe.add("France");
        A northAmerica = root.add("North America");
        northAmerica.add("United States");
        northAmerica.add("Canada");
        A copy = root.deepCopy();
        copy.deepPrint();
    }