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

161

Я пытаюсь понять почему Java ArrayDeque лучше, чем Java LinkedList, поскольку они оба реализуют интерфейс Deque.

Я не вижу, чтобы кто-то использовал ArrayDeque в своем коде. Если кто-то проливает больше света на реализацию ArrayDeque, это будет полезно.

Если я это понимаю, я буду более уверен в этом. Я не мог четко понять реализацию JDK относительно того, как она управляет ссылками на голову и хвост.

жестокий
источник
5
Посмотрите на ответ на этот вопрос, который я задал несколько дней назад: stackoverflow.com/questions/6129805/…
Ренато Динхани
1
В папке, где установлен ваш jdk, находится файл src.zip. Это архив с исходным кодом классов Java. Я настоятельно рекомендую изучить структуру этих классов и внутреннее оборудование, чтобы лучше понять, как работают классы Java.

Ответы:

155

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

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

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

bestsss
источник
57
Еще одно отличие: LinkedList поддерживает нулевые элементы, а ArrayDeque - нет.
Люк Ашервуд
15
Еще один небольшой недостаток (для приложений реального времени) заключается в том, что при операции push / add требуется немного больше, когда внутренний массив ArrayDeque заполнен, поскольку он должен удваивать свой размер и копировать все данные.
Андрей I
4
@AndreiI, это только одна сторона истории. Даже если вы исключите затраты на итерацию для приложения в реальном времени и сможете предварительно выделить необходимую емкость, GC может потребоваться выполнить итерацию всего LinkedList. В основном вы переносите затраты (которые выше для загрузки) в GC.
bestsss
3
@DavidT. b / c это связано с затратами GC на освобожденный узел, для назначения заголовка может также потребоваться маркировка карты (для GC снова, если LinkedList уже находится в постоянном поколении) ... и это сверх дополнительной косвенности (cache- пропустить) вернуть элемент и заново связать.
bestsss
1
Кроме того, LinkedListреализует Listпока ArrayDequeнет. Это означает, что LinkedListесть методы, такие как indexOfили, в remove(int)то время ArrayDequeкак не имеет. Это может быть важно иногда.
Жека Козлов
60

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

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

coderodde
источник
26

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

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

Крис Шут-Янг
источник
17

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

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

Тестовая установка учитывает:

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

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

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

График:

введите описание изображения здесь

вынос:

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

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

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

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

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

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

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

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

Обратитесь к документации для получения более подробной информации.

Равиндра Бабу
источник
13
«В связанном списке потребуется O (N), чтобы найти последний элемент». это не совсем так. LinkedList реализован в виде двусвязного списка, поэтому вам не нужно просматривать список, чтобы получить последний элемент ( header.previous.element). Заявление об «эффективности памяти» также может быть оспорено, поскольку размер массива
резервных копий
5
«Потребуется O (N), чтобы найти последний элемент» НЕПРАВИЛЬНО. Связанный список содержит ссылку на последний узел, и LinkedList.descendingIterator () получает этот узел. Таким образом, мы получаем O (1) производительность. См .: coffeeorientedprogramming.wordpress.com/2018/04/23/… (таким образом, понижающее голосование).
Лев Уфимцев
1
Когда вы используете Iteratorдля доступа к последнему элементу, операция O (N) для обоих классов. Когда вы используете общий Dequeинтерфейс, доступ к последнему элементу O (1) для обоих классов. Независимо от того, какую точку зрения вы придерживаетесь, приписывать O (1) ArrayDequeи O (N) LinkedListодновременно, неправильно.
Хольгер
Все ваши предложения приняты и исправлены содержание
Равиндра Бабу
1

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

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

rekinyz
источник
-1

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

Например, в случае ниже 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;
    }
}
красный
источник
-5

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

Пиюш Явалкар
источник
3
Если вы ссылаетесь на LinkedListJava Collection, он имеет двойную связь и имеет быстрый доступ к голове и хвосту, поэтому доступ к последнему элементу также занимает O (1).
Морис
Доступ к последнему элементу в LinkedList не является O (N). Если вы используете downndingIterator (), это выполняется в O (1). См. Coffeeorientedprogramming.wordpress.com/2018/04/23/… (таким образом, downvote).
Лев Уфимцев
1
Оба класса не являются потокобезопасными. И нет никакой связи между началом предложения «необходима синхронизация вручную» и его концом «они быстрее».
Хольгер