java - ArrayDeque vs LinkedList as Queue 进行层序遍历

Question

在这种情况下，ArrayDeque 是否应该优于 LinkedList？ Why is ArrayDeque better than LinkedList .

在我看来，我应该使用 LinkedList 而不是 ArrayDeque，因为有相当多的 poll 和 offer该算法中正在进行操作，并且不存在对元素的随机访问。

 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode a) {
    Queue<TreeNode> q = new LinkedList<>();  // new ArrayDeque<>() ???
    q.offer(a);
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    while (q.peek() != null){ //returns null if empty
        ArrayList<Integer> list = new ArrayList<>();
        int n = q.size();
        for (int i = 0; i < n; i++){
            TreeNode node = q.poll();
            list.add(node.val);
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
        }
        ans.add(list);
    }
    return ans;
}

Answer 1

在将 ArrayDeque 和 LinkedList 视为双端队列时，需要权衡取舍。

一般来说，LinkedList类型有以下优点:

• 添加元素的成本是最坏情况下的 O(1)，因此任何单个插入都不会花费太多时间。
• 从末端删除一个元素的成本是最坏情况下的 O(1)，因此任何单个删除都不会花费太多时间。

一般来说，LinkedList类型有以下主要缺点:

• 因为 LinkedList 中的元素不一定连续存储在内存中，LinkedList 的引用局部性差，访问可能会导致更多缓存未命中，从而降低性能。

一般来说，ArrayDeque类型有以下优点:

• 由于元素是连续存储的，ArrayDeque 具有很好的引用局部性，因此元素访问通常会造成很少的缓存未命中，从而带来出色的性能。

一般来说，ArrayDeque有以下缺点:

• 虽然 ArrayDeque 上的任何 n 操作序列都需要时间 O(n)，但当插入时超出数组容量时，ArrayDeque 可能必须执行O(n) 复制元素。因此，ArrayDeque 每次操作的最坏情况性能比 LinkedList 慢。
• 类似地，如果数组容量在删除时下降得太低，则可能需要 O(n) 的时间来调整数组的大小，但是，和以前一样，ArrayDeque 上的任何一系列 n 操作都会花费时间 O(n)。

在您的特定用例中，由于您关心的只是层序遍历的端到端效率，而不是从队列中单独添加或删除元素的成本，因此可能会更快使用 ArrayDeque 而不是 LinkedList。从某种意义上说，LinkedList 类型通常只有在您需要对执行的每个操作都具有良好的最坏情况性能时才更好，而这里不是这种情况。当您只关心端到端运行时时，ArrayDeque 通常性能更高。

希望这对您有所帮助!