Java嵌套评论树BFS：ArrayDeque与带front指针ArrayList选型对比

我在Java 17中实现嵌套评论树的BFS遍历，输入是包含id和parentId的扁平节点列表。先通过HashMap<Long, List<PlainNode>>按父节点索引子节点，再进行树遍历，目前有两种可行实现：

方案A — 使用ArrayDeque作为队列+单独结果列表 #

public List<PlainNode> bfs(List<PlainNode> nodes) {
    Map<Long, List<PlainNode>> byParent = new HashMap<>();
    PlainNode root = null;
    for (PlainNode n : nodes) {
        if (n.parentId() == null) { root = n; continue; }
        byParent.computeIfAbsent(n.parentId(), k -> new ArrayList<>()).add(n);
    }
    List<PlainNode> result = new ArrayList<>();
    Deque<PlainNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        PlainNode curr = queue.poll();
        result.add(curr);
        queue.addAll(byParent.getOrDefault(curr.id(), List.of()));
    }
    return result;
}

方案B — 通过front索引指针复用ArrayList作为队列 #

public List<PlainNode> bfs(List<PlainNode> nodes) {
    Map<Long, List<PlainNode>> byParent = new HashMap<>();
    PlainNode root = null;
    for (PlainNode n : nodes) {
        if (n.parentId() == null) { root = n; continue; }
        byParent.computeIfAbsent(n.parentId(), k -> new ArrayList<>()).add(n);
    }
    List<PlainNode> queue = new ArrayList<>();
    int front = 0;
    queue.add(root);
    while (front < queue.size()) {
        PlainNode curr = queue.get(front++);
        queue.addAll(byParent.getOrDefault(curr.id(), List.of()));
    }
    return queue; // 已为BFS顺序，无需单独结果列表
}

性能差异分析（1000节点规模） #

在1000节点的树中，两种实现的实际性能差异可以忽略不计：

• ArrayDeque的poll()和ArrayList的get(front++)都是O(1)操作，核心遍历逻辑的时间复杂度均为O(n)（n为节点总数）。
• 方案A需要额外维护一个结果列表，多一次元素添加操作，但1000个元素的开销极小，几乎不会被感知。
• 方案B复用ArrayList作为队列，减少了一次列表创建，但ArrayList和ArrayDeque的内部数组扩容逻辑类似，1000节点的规模下都不会触发多次扩容，扩容开销可忽略。

Java惯用实现方式 #

方案A更符合Java的惯用写法：

• Deque是Java标准库中专门用于队列/双端队列操作的抽象接口，使用ArrayDeque作为队列实现是BFS遍历的通用规范写法，可读性更高，其他开发者能快速理解这是队列操作逻辑。
• 方案B的front指针写法属于技巧性实现，可读性稍差，需要额外理解指针的作用，不符合常规的队列使用习惯。
• 从代码维护角度，方案A的职责划分更清晰：队列负责管理待处理节点，结果列表负责存储遍历顺序，逻辑更直观。

内容的提问来源于stack exchange，提问作者Eduardo Visoni