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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

Все люди, критикующие 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.Использование его для внутренних реализаций может быть хорошей идеей ...

Answer 5

Доступ к элементу в ArrayDeque всегда быстрее по сравнению с LinkedList с O (1) для доступа к элементам.В связанном списке потребуется O (N), чтобы найти последний элемент.

ArrayDeque эффективно использует память, поскольку вам не нужно отслеживать следующий узел в отличие от связанного списка.

Даже в соответствии с документацией Java, было указано, что

ArrayDeque - реализация массива Resizable для интерфейса Deque.У массивов нет ограничений по емкости;они растут по мере необходимости для поддержки использования.Они не являются потокобезопасными;в отсутствие внешней синхронизации они не поддерживают одновременный доступ несколькими потоками.Нулевые элементы запрещены.Этот класс, вероятно, будет быстрее, чем Stack, когда используется в качестве стека, и быстрее, чем LinkedList, когда используется в качестве очереди.

Сравнительный анализ из этих двух доказывает, что ArrayDeque быстрее.

Answer 6

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

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

Answer 7

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