Я пытаюсь понять почему Java ArrayDeque лучше, чем Java LinkedList, поскольку они оба реализуют интерфейс Deque.
Я не вижу, чтобы кто-то использовал ArrayDeque в своем коде. Если кто-то проливает больше света на реализацию ArrayDeque, это будет полезно.
Если я это понимаю, я буду более уверен в этом. Я не мог четко понять реализацию JDK относительно того, как она управляет ссылками на голову и хвост.
java
deque
linked-list
arraydeque
жестокий
источник
источник
src.zip
. Это архив с исходным кодом классов Java. Я настоятельно рекомендую изучить структуру этих классов и внутреннее оборудование, чтобы лучше понять, как работают классы Java.Ответы:
Связанные структуры, возможно, являются худшей структурой для итерации с отсутствием кэша для каждого элемента. Кроме того, они потребляют больше памяти.
Если вам нужно добавить / удалить оба конца, ArrayDeque значительно лучше, чем связанный список. Произвольный доступ к каждому элементу также равен O (1) для циклической очереди.
Единственная лучшая операция связанного списка - удаление текущего элемента во время итерации.
источник
LinkedList
реализуетList
покаArrayDeque
нет. Это означает, чтоLinkedList
есть методы, такие какindexOf
или, вremove(int)
то времяArrayDeque
как не имеет. Это может быть важно иногда.Я считаю, что основным узким местом в производительности
LinkedList
является тот факт, что всякий раз, когда вы продвигаетесь к любому концу deque, за кулисами реализация выделяет новый узел связанного списка, который по существу включает JVM / OS, и это дорого. Кроме того, всякий раз, когда вы открываете с любого конца, внутренние узлыLinkedList
становятся пригодными для сборки мусора, и это больше работы за кулисами. Кроме того, поскольку узлы связанного списка размещены здесь и там, использование кэша ЦП не даст большого преимущества.Если это может быть интересно, у меня есть доказательство того, что добавление (добавление) элемента к
ArrayList
илиArrayDeque
выполняется в амортизированном постоянном времени; обратитесь к этому .источник
ArrayDeque
впервые в Java 6, поэтому многие программы (особенно проекты, которые пытаются быть совместимыми с более ранними версиями Java) не используют его.В некоторых случаях это «лучше», потому что вы не выделяете узел для каждого элемента для вставки; вместо этого все элементы хранятся в гигантском массиве, размер которого изменяется, если он заполняется.
источник
Все люди, критикующие
LinkedList
, думают о каждом парне, который использовалList
в Java, вероятно, используетArrayList
иLinkedList
большую часть времени, потому что они были до Java 6 и потому, что это те, которые преподаются как начало в большинстве книг.Но это не значит, что я бы слепо принял сторону
LinkedList
илиArrayDeque
сторону. Если вы хотите знать, взгляните на нижеприведенный тест Брайана .Тестовая установка учитывает:
Результат испытаний:
График:
вынос:
ArrayList
илиArrayDeque
с хорошим предположением о максимальной емкости, которой может потребоваться список из-за строгого ограничения памяти.LinkedList
такой простоты, когда вы решаете использовать его,ArrayDeque
особенно потому, что он НЕ реализуетList
интерфейс (я думаю, что причина достаточно большая). Может случиться так, что ваша кодовая база широко общается с интерфейсом List, скорее всего, и вы решите подключиться кArrayDeque
. Использование его для внутренних реализаций может быть хорошей идеей ...источник
ArrayDeque и LinkedList реализуют Deque интерфейс , но реализация отличается.
Ключевые отличия:
Класс ArrayDeque является реализацией массива изменяемого размера интерфейса Deque, а класс LinkedList является реализацией списка
Элементы NULL могут быть добавлены в LinkedList, но не в ArrayDeque
ArrayDeque более эффективен, чем LinkedList для операции добавления и удаления на обоих концах, а реализация LinkedList эффективна для удаления текущего элемента во время итерации.
Реализация LinkedList потребляет больше памяти, чем ArrayDeque
Поэтому, если вам не нужно поддерживать NULL-элементы && в поисках меньшего объема памяти && эффективности добавления / удаления элементов на обоих концах, ArrayDeque является лучшим
Обратитесь к документации для получения более подробной информации.
источник
header.previous.element
). Заявление об «эффективности памяти» также может быть оспорено, поскольку размер массиваIterator
для доступа к последнему элементу, операция O (N) для обоих классов. Когда вы используете общийDeque
интерфейс, доступ к последнему элементу O (1) для обоих классов. Независимо от того, какую точку зрения вы придерживаетесь, приписывать O (1)ArrayDeque
и O (N)LinkedList
одновременно, неправильно.хотя
ArrayDeque<E>
иLinkedList<E>
реализовалиDeque<E>
интерфейс, но ArrayDeque использует в основном массив объектовE[]
для хранения элементов внутри своего объекта, поэтому он обычно использует индекс для определения местоположения элементов head и tail.Одним словом, он просто работает как Deque (со всеми методами Deque), но использует структуру данных массива. Что касается того, какой из них лучше, зависит от того, как и где вы их используете.
источник
Это не всегда так.
Например, в случае ниже
linkedlist
имеет лучшую производительность, чем вArrayDeque
соответствии с leetcode 103.источник
Временная сложность для ArrayDeque для доступа к элементу составляет O (1), а для LinkList - O (N) для доступа к последнему элементу. ArrayDeque не является потокобезопасным, поэтому необходима синхронизация вручную, чтобы вы могли получить к нему доступ через несколько потоков, чтобы они работали быстрее.
источник
LinkedList
JavaCollection
, он имеет двойную связь и имеет быстрый доступ к голове и хвосту, поэтому доступ к последнему элементу также занимает O (1).