When to use LinkedList over ArrayList in Java?

Я всегда был из тех, кто просто использует:

List<String> names = new ArrayList<>();

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

Когда следует LinkedList использовать поверх ArrayList и наоборот?

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

До сих пор, похоже, никто не обращался к объему памяти каждого из этих списков, кроме общего согласия, что 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)

ArrayList это то, что вы хотите. LinkedList почти всегда ошибка (производительности).

Почему LinkedList отстой:

• Он использует множество небольших объектов памяти и, следовательно, влияет на производительность всего процесса.


• Множество мелких объектов вредно для локализации кэша.


• Любая индексированная операция требует обхода, т. Е. имеет O (n) производительность. Это не очевидно в исходном коде, что приводит к тому, что алгоритмы работают на O (n) медленнее, чем если бы ArrayList использовался.


• Добиться хорошей производительности сложно.


• Даже если производительность big-O такая же, как ArrayList, вероятно, она в любом случае будет значительно медленнее.


• Неприятно видеть LinkedList в исходном коде, потому что это, вероятно, неправильный выбор.

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 хороши для однократного чтения или для добавляющих устройств, но плохи при добавлении / удалении спереди или посередине.