ArrayDeque vs LinkedList как очередь для прохождения порядка уровня

Question

Правда ли, что ArrayDeque предпочтительнее, чем LinkedList в этом сценарии? Почему ArrayDeque лучше, чем 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 имеет отличную локальность ссылок, поэтому доступ к элементам будет типичным.y создает несколько ошибок в кеше и, таким образом, приводит к превосходной производительности.

В общем случае ArrayDeque имеет следующий недостаток:

• Хотя любая последовательность из n операцийArrayDeque займет время O (n), когда при вставке будет превышена емкость массива, ArrayDeque может потребоваться выполнить O (n) работу для копирования элементов.В результате наихудшая производительность ArrayDeque на операцию медленнее, чем LinkedList.
• Аналогичным образом, если при удалении емкость массива слишком мала, это может занять время O (n), чтобы изменить размер массива, хотя, как и раньше, любая последовательность из n операций с ArrayDeque займет время O (n).

В вашем конкретном случае использования, так как все, что вам нужно, этосквозная эффективность обхода порядка уровней, а не стоимость какого-либо отдельного добавления или удаления элементов из очереди, вероятно, будет быстрее использовать ArrayDeque, чем LinkedList.В некотором смысле тип LinkedList, как правило, лучше только в том случае, если вам нужна хорошая производительность в худшем случае для каждой выполняемой операции, а здесь это не так.ArrayDeque, как правило, более производительный, когда все, что вам нужно, это сквозное время выполнения.

Надеюсь, это поможет!