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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

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

Результат теста:

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

Graph:

Вынос:

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

Ответ 6

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

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

Ответ 7

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