ArrayDeque 与 LinkedList 作为队列进行层序遍历

Question

在这种情况 下，真的ArrayDeque应该优先选择吗？为什么 ArrayDeque 比 LinkedList 更好？LinkedList

在我看来，我应该使用 LinkedList 而不是 ArrayDeque，因为这个算法中有相当多的pollandoffer 操作，并且没有对元素的随机访问。

 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类型有以下主要缺点：

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

总体来说，该ArrayDeque类型具有以下优点：

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

一般来说，它ArrayDeque有以下缺点：

• 尽管任何 n 个操作序列都ArrayDeque将花费 O(n) 时间，但当插入超出数组容量时，ArrayDeque可能需要执行 O(n) 工作来复制元素。因此，ArrayDeque每个操作的最坏情况性能比LinkedList.
• 类似地，如果在删除时数组容量下降得太低，则调整数组大小可能需要花费 O(n) 时间，但与之前一样，对 an 进行任何一系列 n 操作都ArrayDeque将花费 O(n) 时间。

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

希望这可以帮助！