How do we efficiently iterate a list of objects from the same object class?

Question

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...

This ia tree structure. Handling that is covered very broadly. Just iterate recursively. If you do it breadth-first or depth-first does not matter at first glance. — f1sh, Jan 13 '22 at 11:16
"Since you do not know the depth, you have to use recursion." - I don't believe that is correct. Not knowing the depth does not impose a requirement that recursion be used to visit all of the elements. — Jeff Scott Brown, Jan 13 '22 at 17:31

trincot · Accepted Answer · 2022-01-13T17:25:15.580

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.println(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();
    }

I just want to create a deep copy manually made by iterating everything and pass the values to another A reference. A serializer of the object followed by a deserializer method would work as well but I want to make it manually — Irinel, Jan 13 '22 at 12:26
*"I want to make it manually"*: so have you tried with this coding pattern that I showed? — trincot, Jan 13 '22 at 12:30
Added a method to perform a deep copy. Let me know if this is what you were looking for. — trincot, Jan 13 '22 at 14:06

m.antkowicz · Answer 2 · 2022-01-13T11:39:03.987

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;
}

How do we efficiently iterate a list of objects from the same object class?

2 Answers2