我们如何有效地迭代来自同一对象类的对象列表？

Question

我们有这节课

public class A {

    private String someVariable;
    private List<A> innerObjects;

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

假设我们不知道InnerObject中有多少个对象，我们如何以最佳方式手动迭代该对象？主要的问题将在内部列表上，因为它可能还有另一个列表，另一个和另一个，等等。。。

Answer 1

毫无疑问，你不可能比< code>O(n)更有效地迭代一个列表。

因此，您可以创建一个方法来迭代列表并做一些事情（基本上您甚至可以在那里提供一个实现业务逻辑的函数），如果内部A包含一个列表，则递归地再次调用对象上的方法

这种方法的一个简单例子可能是：

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

延伸阅读：

< li >什么是递归 < li>Java将方法作为参数传递 < li >在Java中遍历二叉树的所有节点-因为通常您可以将每个< code>A实例视为某个抽象树节点，并将它的列表视为其子节点(这种结构看起来有点像B树)

Answer 2

要访问每个嵌套节点，可以执行树遍历。有几种遍历订单可供选择：

• 深度第一，预购
• 深度优先，后订购
• 广度第一
• ...

以下是一些示例代码，用于深度优先、预排序打印这些在字符串中，每个都按树中的深度缩进，以及另一个执行整个对象结构的深度副本的函数：

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 + "  ");
        }
    }
}

和一些驱动程序代码来测试这一点:

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