Recursive, nested list traversal

Question

Given a nested list of strings (which may contain other nested lists), print the contents of the list and the corresponding depth.

Here is my solution:

private static void dumpList(String string, List l) {
    int n = l.size();
    for (int i = 0; i < n; i++) {
        if(l.get(i) instanceof String){
            System.out.println(string+i + " " + l.get(i));
        }
        if(l.get(i) instanceof List){
            dumpList(string+i, (List)l.get(i));
        }
    }
}

Here is main():

public static void main(String[] args) {
    String s = "Foo";
    List l = new ArrayList();
    ArrayList<String> a = new ArrayList<String>();
    ArrayList<String> b = new ArrayList<String>();
    //ArrayList<String> c = new ArrayList<String>();
    a.add("a");
    a.add("b");
    a.add("c");
    b.add("eggs");
    l.add("a string");
    l.add(a);
    l.add("spam");
    l.add("eggs");
    dumpList("Foo", l);
}

My output:

Foo0 a string
Foo10 a
Foo11 b
Foo12 c
Foo2 spam
Foo3 eggs

I am not that much interested in naming of the variables, but of formatting of the output. Should I use StringBuilder instead of the + operator? Should I print it differently?

Answer 1

This is in addition to what @tim already said.

The dumpList method takes a List, and then you make 2 .get(i) calls in every iteration of the loop. Keep in mind that the List interface doesn't ensure random access. For example I can call this method with a LinkedList parameter, in which case the .get(i) calls will be costly. Either change the method parameter to ArrayList or similar random access list, or change the way you iterate (I recommend), for example like this:

private static void dumpList(String string, List<Object> list) {
    int i = 0;
    for (Object item : list) {
        if (item instanceof List) {
            dumpList(string + i, (List) item);
        } else {
            System.out.println(String.format("%s%d %s", string, i, item));
        }
        ++i;
    }
}

Instead of doing if (item instanceof String) and then if (item instanceof List), it's better to do if (item instanceof List) and an else. This solves 2 problems at once:

• Adds support for other element types, not only String and List, which otherwise would have been ignored

• The second if should have been either an else if or an else, because if the first if was true, it's pointless to evaluate the second

I changed the string + i + " " + l.get(i) to the (in my opinion) more readable String.format("...", ...) style.

Finally, I renamed l to list. Single-letter variable names are acceptable as loop counters, like i, j, k, otherwise it's better to give meaningful names.

Answer 2

Should I use StringBuilder instead of + operator?

If performance is an issue, then yes, use StringBuilder (see here).

Another advantage of this approach is, that you are separating the collection of the data from the printing of the data. It would be easy to change the print command with for example a command to print to file later on.

Because you are using recursion, you would need to pass it as a parameter:

private static void dumpList(String string, List l, StringBuilder sb) {
    int n = l.size();
    for (int i = 0; i < n; i++) {
        if (l.get(i) instanceof String) {
            sb.append(string).append(i).append(" ").append(l.get(i)).append("\n");
            // or Version 2: 
            // sb.append(string + i + " " + l.get(i) + "\n");
        }
        if (l.get(i) instanceof List) {
            dumpList(string + i, (List) l.get(i), sb);
        }
    }
}

(The second version is a bit more readable, while the first version might be faster, depending on the Java implementation)

And then output the result in main:

public static void main(String[] args) {
    String s = "Foo";
    StringBuilder sb = new StringBuilder(100);
    [...]
    dumpList("Foo", l, sb);
    System.out.println(sb.toString());
}

Should I print it differently?

That is really your decision. I think that the way you are doing it is a bit confusing, I would at least add a space in the recursive call between string and i (so Foo12 becomes Foo1 2). Personally, I would prefer the output to look something like this: ["a string" (0), ["a" (1), "b" (1), "c" (1)], "spam" (0), "eggs" (0)] (where the numbers are the depth level), but it really depends on what you want to do with the code.

Also, right now, you are not printing the corresponding depth of the item (you are printing each position inside the depth-level). To do this, you would need another argument which you can increase every time you call dumpList:

private static void dumpList(String string, List l, StringBuilder sb, int depth) {
    [...]
            dumpList(string + i, (List) l.get(i), sb, depth + 1);
    [...]
}

And by the way, you are never using list b.

Answer 3

This is in addition to what @janos already said.

Two things:

• Use generics better. List<?> is sufficient when you iterate through the list. This will allow all kinds of list to be passed to the method, such as List<String>, List<MySpecialType>.

• Is it really important to be a List specifically? No, all you care about is that it is Iterable. Which will also support this method for Sets and other Collections, and even some other types. Iterable is more generic than only Collection.

With these changes made:

private static void dumpList(String string, Iterable<?> list) {
    int i = 0;
    for (Object item : list) {
        if (item instanceof Iterable) {
            dumpList(string + i, (Iterable<?>) item);
        } else {
            System.out.println(String.format("%s%d %s", string, i, item));
        }
        ++i;
    }
}