Почему ArrayDeque лучше, чем LinkedList

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

Если вам нужно добавить / удалить оба конца, ArrayDeque значительно лучше, чем связанный список. Произвольный доступ к каждому элементу также составляет O (1) для циклической очереди.

Единственная лучшая операция связанного списка - это удаление текущего элемента во время итерации.

Я считаю, что основным узким местом производительности в LinkedList является тот факт, что всякий раз, когда вы нажимаете на любой конец двухсторонней очереди, за сценой реализация выделяет новый узел связанного списка, который, по сути, включает JVM / OS, а это дорого. Кроме того, всякий раз, когда вы выскакиваете с любого конца, внутренние узлы LinkedList получают право на сборку мусора, и это требует дополнительной работы за кулисами. Кроме того, поскольку узлы связанного списка распределяются здесь и там, использование кэша ЦП не принесет большой пользы.

Если это может быть интересно, у меня есть доказательство того, что добавление (добавление) элемента к ArrayList или ArrayDeque выполняется за амортизированное постоянное время; см. это.

ArrayDeque впервые появился в Java 6, поэтому многие программы (особенно проекты, которые пытаются быть совместимыми с более ранними версиями Java) не используют его.

В некоторых случаях это «лучше», потому что вы не выделяете узел для каждого вставляемого элемента; вместо этого все элементы хранятся в гигантском массиве, размер которого изменяется при заполнении.

Все люди, критикующие LinkedList, подумайте о каждом другом парне, который использовал List на Java, вероятно, использует ArrayList и LinkedList большую часть времени, потому что они были до Java 6 и потому, что это те, которые преподаются в качестве начала в большинстве книг .

Но это не значит, что я бы слепо встал на сторону LinkedList или ArrayDeque. Если вы хотите знать, взгляните на приведенный ниже тест сделано Брайаном (заархивировано).

В тестовой установке учитываются:

• Каждый тестовый объект представляет собой строку из 500 символов. Каждая строка - это отдельный объект в памяти.
• Размер тестового массива будет изменяться во время тестов.
• Для каждой комбинации размер массива / очередь-реализация выполняется 100 тестов и вычисляется среднее время выполнения теста.
• Каждый тест состоит из заполнения каждой очереди всеми объектами и последующего их удаления.
• Измерьте время в миллисекундах.

Результат испытаний:

• Ниже 10 000 элементов, тесты LinkedList и ArrayDeque усредняются на уровне менее 1 мс.
• По мере увеличения наборов данных разница между средним временем тестирования ArrayDeque и LinkedList увеличивается.
• При размере теста в 9 900 000 элементов подход LinkedList занял на ~ 165% больше времени, чем подход ArrayDeque.

График:

Вывод:

• Если ваше требование хранит 100 или 200 элементов, использование любой из очередей не будет иметь большого значения.
• Однако, если вы разрабатываете на мобильных устройствах, вы можете использовать ArrayList или ArrayDeque с хорошим предположением о максимальной емкости, которая может потребоваться в списке из-за строгих ограничений памяти.
• Существует много кода, написанного с использованием LinkedList, поэтому будьте осторожны при принятии решения об использовании ArrayDeque, особенно потому, что он НЕ реализует List интерфейс (я думаю, что это достаточно большая причина). Возможно, ваша кодовая база активно взаимодействует с интерфейсом List, и, скорее всего, вы решите использовать ArrayDeque. Использование его для внутренних реализаций может быть хорошей идеей ...

ArrayDeque и LinkedList реализуют Deque, но реализация отличается.

Ключевые отличия:

1. Класс ArrayDeque - это реализация массива с изменяемым размером интерфейса Deque, а класс LinkedList - реализация списка

2. Элементы NULL можно добавить в LinkedList, но не в ArrayDeque

3. ArrayDeque более эффективен, чем LinkedList для операций добавления и удаления на обоих концах, а реализация LinkedList эффективна для удаления текущего элемента во время итерации.

4. Реализация LinkedList потребляет больше памяти, чем ArrayDeque

Поэтому, если вам не нужно поддерживать элементы NULL &&, ища меньше памяти && эффективности добавления / удаления элементов с обоих концов, ArrayDeque - лучший вариант.

Дополнительные сведения см. В документации.

хотя в ArrayDeque<E> и LinkedList<E> реализован интерфейс Deque<E>, но ArrayDeque использует в основном массив объектов E[] для хранения элементов внутри своего объекта, поэтому он обычно использует индекс для поиска элементов головы и хвоста.

Одним словом, он работает как Deque (со всеми методами Deque), но использует структуру данных массива. Что касается того, какой из них лучше, зависит от того, как и где вы их используете.

Это не всегда так.

Например, в приведенном ниже случае linkedlist имеет лучшую производительность, чем ArrayDeque в соответствии с leetcode 103.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null)
            return rs;
        // ???? here ,linkedlist works better
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean left2right=true;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            LinkedList<Integer> t=new LinkedList<>();
            while(size-->0)
            {
                TreeNode tree=queue.remove();
                if(left2right)  
                    t.add(tree.val);
                else
                    t.addFirst(tree.val);
                if(tree.left!=null)
                {
                    queue.add(tree.left);
                }
                if(tree.right!=null)
                {
                    queue.add(tree.right);
                }
            }
            rs.add(t);
            left2right=!left2right;
        }
        return rs;
    }
}

Сложность времени для ArrayDeque для доступа к элементу составляет O (1), а для LinkList - O (N) для доступа к последнему элементу. ArrayDeque не является потокобезопасным, поэтому необходима ручная синхронизация, чтобы вы могли получить к нему доступ через несколько потоков, и они работают быстрее.