CODEWITHSUNDEEP
javaalgorithm
Irinel
Irinel

Reputation: 89

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

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

Upvotes: 0

Views: 650

Answers (2)

trincot
trincot

Reputation: 349999

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

Upvotes: 2

m.antkowicz
m.antkowicz

Reputation: 13571

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:

Upvotes: 0

Related Questions