Когда использовать LinkedList поверх ArrayList в Java?
Я всегда был из тех, кто просто использует:
List<String> names = new ArrayList<>();
Я использую интерфейс в качестве имени типа для переносимости, так что, когда я задаю такие вопросы, как этот, я могу переработать свой код.
Когда следует LinkedList
использовать поверх ArrayList
и наоборот?
Переведено автоматически
Ответ 1
Резюме ArrayList
с ArrayDeque
предпочтительнее в гораздо большем количестве вариантов использования, чем LinkedList
. Если вы не уверены — просто начните с ArrayList
.
TLDR, в ArrayList
доступ к элементу занимает постоянное время [O (1)], а добавление элемента занимает O (n) времени [наихудший случай]. В LinkedList
вставка элемента занимает O (n) времени, и доступ к нему также занимает O (n) времени, но LinkedList
использует больше памяти, чем ArrayList
.
LinkedList
и ArrayList
- это две разные реализации List
интерфейса. LinkedList
реализует его с помощью двусвязного списка. ArrayList
реализует это с помощью массива с динамическим изменением размера.
Как и при стандартных операциях со связанными списками и массивами, различные методы будут иметь разное алгоритмическое время выполнения.
Для LinkedList<E>
get(int index)
- это O(n) (в среднем с n/4 шагами), но O(1) когдаindex = 0
илиindex = list.size() - 1
(в этом случае вы также можете использоватьgetFirst()
иgetLast()
). Одно из основных преимуществLinkedList<E>
add(int index, E element)
- это O(n) (в среднем с n/4 шагами), но O(1) когдаindex = 0
илиindex = list.size() - 1
(в этом случае вы также можете использоватьaddFirst()
иaddLast()
/add()
). Одно из основных преимуществLinkedList<E>
remove(int index)
- это O(n) (в среднем с n/4 шагами), но O(1) когдаindex = 0
илиindex = list.size() - 1
(в этом случае вы также можете использоватьremoveFirst()
иremoveLast()
). Одно из основных преимуществLinkedList<E>
Iterator.remove()
является O (1). Одно из основных преимуществLinkedList<E>
ListIterator.add(E element)
является O (1). Одно из основных преимуществLinkedList<E>
Примечание: Для многих операций требуется в среднем n / 4 шага, постоянное количество шагов в лучшем случае (например, index = 0) и n / 2 шага в худшем случае (середина списка)
Для ArrayList<E>
get(int index)
является O (1). Основное преимуществоArrayList<E>
add(E element)
это O (1) амортизируется, но O (n) наихудший вариант, поскольку размер массива должен быть изменен и скопированadd(int index, E element)
равно O (n) (в среднем с n / 2 шагами)remove(int index)
равно O (n) (в среднем с n / 2 шагами)Iterator.remove()
равно O (n) (в среднем с n / 2 шагами)ListIterator.add(E element)
равно O (n) (в среднем с n / 2 шагами)
Примечание: Для многих операций требуется в среднем n / 2 шага, постоянное количество шагов в лучшем случае (конец списка), n шагов в худшем случае (начало списка)
LinkedList<E>
допускает вставки или удаления в постоянное время с использованием итераторов, но только последовательный доступ к элементам. Другими словами, вы можете перемещаться по списку вперед или назад, но поиск позиции в списке требует времени, пропорционального размеру списка. В Javadoc сказано, что "операции, индексирующие список, будут проходить по списку с начала или конца, в зависимости от того, что ближе", поэтому эти методы в среднем составляют O (n) (n / 4 шага), хотя O (1) для index = 0
.
ArrayList<E>
, с другой стороны, обеспечивает быстрый произвольный доступ на чтение, так что вы можете захватить любой элемент за постоянное время. Но добавление или удаление из любого места, кроме конца, требует переноса всех последних элементов, либо для открытия, либо для заполнения пробела. Кроме того, если вы добавляете больше элементов, чем вместимость базового массива, выделяется новый массив (в 1,5 раза больше), а старый массив копируется в новый, поэтому добавление к an ArrayList
составляет O (n) в худшем случае, но в среднем остается постоянным.
Итак, в зависимости от операций, которые вы собираетесь выполнять, вам следует соответствующим образом выбирать реализации. Итерация по спискам любого типа практически одинаково дешева. (Итерация по ArrayList
технически быстрее, но если вы не делаете что-то действительно чувствительное к производительности, вам не стоит беспокоиться об этом - они оба являются константами.)
Основные преимущества использования a LinkedList
возникают при повторном использовании существующих итераторов для вставки и удаления элементов. Затем эти операции можно выполнить в O (1), изменив список только локально. В списке массивов остальная часть массива должна быть перемещена (т.е. Скопирована). С другой стороны, поиск в a LinkedList
означает переход по ссылкам за O (n) (n / 2 шага) в худшем случае, тогда как в an ArrayList
желаемая позиция может быть вычислена математически и доступна за O (1).
Еще одно преимущество использования a LinkedList
возникает при добавлении или удалении из заголовка списка, поскольку эти операции являются O(1), в то время как они являются O (n) для ArrayList
. Обратите внимание, что ArrayDeque
может быть хорошей альтернативой LinkedList
для добавления и удаления из head, но это не List
.
Кроме того, если у вас большие списки, имейте в виду, что использование памяти также отличается. Каждый элемент a LinkedList
имеет больше накладных расходов, поскольку указатели на следующий и предыдущий элементы также хранятся. ArrayLists
у вас нет таких накладных расходов. Однако ArrayLists
занимают столько памяти, сколько выделено для емкости, независимо от того, были ли элементы добавлены на самом деле.
Начальная емкость an по умолчанию ArrayList
довольно мала (10 в Java 1.4 - 1.8). Но поскольку базовой реализацией является массив, размер массива необходимо изменять, если вы добавляете много элементов. Чтобы избежать высоких затрат на изменение размера, когда вы знаете, что собираетесь добавить много элементов, создайте ArrayList
с большей начальной емкостью.
Если для понимания двух структур используется перспектива структур данных, LinkedList в основном представляет собой последовательную структуру данных, которая содержит головной узел. Узел является оболочкой для двух компонентов : значения типа T [принимается через generics] и другой ссылки на узел, связанный с ним. Итак, мы можем утверждать, что это рекурсивная структура данных (узел содержит другой узел, у которого есть другой узел и так далее ...). Добавление элементов в LinkedList занимает линейное время, как указано выше.
ArrayList - это растущий массив. Он похож на обычный массив. Обычно, когда добавляется элемент, а ArrayList уже заполнен до отказа, создается другой массив с размером, превышающим предыдущий размер. Затем элементы копируются из предыдущего массива в новый, и элементы, которые необходимо добавить, также размещаются по указанным индексам.
Ответ 2
До сих пор, похоже, никто не обращался к объему памяти каждого из этих списков, кроме общего согласия, что a LinkedList
"намного больше", чем an ArrayList
поэтому я произвел некоторую числовую обработку, чтобы точно продемонстрировать, сколько оба списка занимают для N нулевых ссылок.
Поскольку ссылки имеют 32 или 64 бита (даже когда null) в соответствующих системах, я включил 4 набора данных для 32 и 64 бит LinkedLists
и ArrayLists
.
Примечание: Размеры, указанные для ArrayList
строк, относятся к обрезанным спискам - На практике емкость резервного массива в ArrayList
обычно больше, чем текущее количество его элементов.
(спасибо BeeOnRope) Примечание 2: Поскольку CompressedOops теперь используется по умолчанию начиная с середины JDK6 и выше, приведенные ниже значения для 64-разрядных машин будут в основном соответствовать их 32-разрядным аналогам, если, конечно, вы специально не отключите это.
Результат ясно показывает, что LinkedList
это намного больше, чем ArrayList
, особенно при очень большом количестве элементов. Если важна память, держитесь подальше от LinkedLists
.
Формулы, которые я использовал, следующие, дайте мне знать, если я сделал что-то не так, и я это исправлю. 'b' - это либо 4, либо 8 для 32- или 64-разрядных систем, а 'n' - количество элементов. Обратите внимание, что причина модификаций заключается в том, что все объекты в java будут занимать пространство, кратное 8 байтам, независимо от того, используется все это или нет.
ArrayList:
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList:
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
Ответ 3
ArrayList
это то, что вы хотите. LinkedList
почти всегда ошибка (производительности).
Почему LinkedList
отстой:
- Он использует множество небольших объектов памяти и, следовательно, влияет на производительность всего процесса.
- Множество мелких объектов вредно для локализации кэша.
- Любая индексированная операция требует обхода, т. Е. имеет O (n) производительность. Это не очевидно в исходном коде, что приводит к тому, что алгоритмы работают на O (n) медленнее, чем если бы
ArrayList
использовался. - Добиться хорошей производительности сложно.
- Даже если производительность big-O такая же, как
ArrayList
, вероятно, она в любом случае будет значительно медленнее. - Неприятно видеть
LinkedList
в исходном коде, потому что это, вероятно, неправильный выбор.
Ответ 4
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
Алгоритмы: нотация Big-Oh (архивировано)
ArrayLists хороши для однократного чтения или для добавляющих устройств, но плохи при добавлении / удалении спереди или посередине.