Какова цель LinkedList в Java, учитывая, что ArrayList не имеет ограничений по размеру?

avatar
Dog
9 августа 2021 в 02:28
173
4
-1

Во многих сообщениях, когда я читал о преимуществах LinkedList, чаще всего я слышал о том, что в некоторых ситуациях LinkedList более эффективен, потому что вставка и удаление выполняются быстрее, чем в массиве.

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

Однако, поскольку в Java есть список ArrayList, у которого нет ограничения емкости, утверждение о более высокой производительности LinkedList кажется неверным. Являются ли LinkedLists устаревшими в Java? Существуют ли какие-либо ситуации, в которых LinkedList на самом деле лучше, чем ArrayList в Java?

Источник
samabcde
9 августа 2021 в 02:32
1

«у которого нет ограничения емкости» - ArrayList по-прежнему поддерживается массивом, но он просто скрывает для вас расширение и копирование массива.

Sweeper
9 августа 2021 в 02:34
1

Вы когда-нибудь задумывались о почему ArrayList называется "массив список"? Он использует массив под капотом.

Ole V.V.
9 августа 2021 в 03:29
1

Вы правы, вряд ли вам когда-либо понадобится LinkedList. Я использовал его один раз за свои 20 с лишним лет работы Java-программистом и, оглядываясь назад, пожалел об этом.

Ole V.V.
9 августа 2021 в 03:33
1

Кажется, до появления Java существовала традиция использования связанных списков, поэтому, я думаю, они подумали, что им лучше включить один из них и в Java Collections Framework. Так что, если я прав, цель скорее заключалась в том, чтобы представить то, что люди воспримут как полный набор реализаций коллекций. Это был простой способ избежать критики за недостатки, независимо от того, была ли эта критика обоснованной или нет. Цель не была практической.

Dog
9 августа 2021 в 03:35
2

Хуже всего то, что они до сих пор используются на технических собеседованиях при собеседовании с кандидатами.

Ole V.V.
9 августа 2021 в 03:48
1

Для технического интервью то, что я написал в своих комментариях, должно быть хорошим ответом (иначе я не хочу там работать).

Ответы (4)

avatar
Green Cloak Guy
9 августа 2021 в 02:34
4

Скажем, у вас есть список из 100 000 (или такого же большого числа) элементов.

Скажите, что вы хотите вставить элемент в начале или где-то в середине.

В ArrayList вам нужно переместить каждый элемент назад на одно место, чтобы освободить место. Очевидно, для этого требуется O(n) операций.

С LinkedList вам просто нужно создать новый узел и вставить его. Если вы уже знаете, где он вам нужен, это операция O(1).

Наоборот для удаления — особенно по мере увеличения размера списка и по мере того, как индексирование становится менее важным по сравнению с вставкой и удалением, связанные списки имеют преимущества в производительности по сравнению со списками-массивами.

И это без учета того, как связанные списки демонстрируют концепции, которые важны для последующего расширения на деревья и графы с точки зрения обучения. Но вы спрашиваете не об этом.

Dog
9 августа 2021 в 02:35
0

Большое спасибо, что нашли время, чтобы объяснить это. Ваш ответ действительно прояснил этот момент для меня.

Ole V.V.
9 августа 2021 в 03:37
0

Для вставки в начале явно нужно использовать ArrayDeque, а не LinkedList. Даже при вставке в середину большого списка в некоторых случаях было измерено, что общая производительность выше с ArrayList, поскольку LinkedList, используемый таким образом, имеет тенденцию распространяться на гораздо большее количество страниц памяти и, следовательно, вызывать перегрузку.

avatar
Stephen C
9 августа 2021 в 03:13
3

Какова цель LinkedList в Java, учитывая, что ArrayList не имеет ограничений по размеру?

Не так много ситуаций, когда LinkedList объективно лучше, чем ArrayList.

Сначала несколько основных фактов:

  • Оба типа списков имеют динамический размер (без разницы).
  • ArrayList занимает меньше памяти на элемент, чем LinkedList. В 4 раза и более. (Один указатель на элемент вместо трех указателей плюс накладные расходы узла кучи.)
  • Если вы грубо ошибетесь в оценке начальной емкости ArrayList, он может использовать больше памяти, чем LinkedList. (Но на самом деле это ошибка приложения.)
  • Большинство операций выполняются быстрее для ArrayList.
    • позиционные операции O(1) против O(N)
    • влияние локальности на производительность по сравнению с кэшем памяти/кэшем TLB/промахами страниц виртуальной машины может быть значительным для больших списков.
  • Некоторые операции могут выполняться быстрее для LinkedList; например вставка и удаление. Однако это зависит от специфики; например положение вставки или удаления, или активирует ли операция расширение резервного массива.

Итак, в каких случаях LinkedList может оказаться выгодным?

Одним из случаев является добавление и удаление элементов в начале списка. Это O(1) для LinkedList и O(N) для ArrayList. (ArrayDeque обычно лучше, чем LinkedList... за исключением того, что он не реализует API List.)

Второй случай — обход списка и добавление или удаление элементов во время обхода. Метод LinkedList.listIterator возвращает ListIterator, который позволяет добавить или удалить элемент в текущей позиции. Это O(1) операций.

В-третьих, LinkedList может оказаться выгодным, если ваше приложение крайне нетерпимо (например) к добавлениям списка, которые могут занять много времени. (Подумайте о приложениях жесткого реального времени....)

Наконец, неверно говорить, что ArrayList не имеет ограничений по размеру. На самом деле он ограничен чуть менее 2 ^ 31 элементами. Это связано с тем, что массивы Java ограничены JVM чуть менее чем 2^31 элементами. LinkedList не имеет этой проблемы.


Устарели ли списки LinkedList в Java?

Этот класс редко используется (и всегда использовался), но он не устарел.

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


Обратите внимание, что вам необходимо учитывать все операции, выполняемые над списком. Часто это слишком сложно сделать заранее. И усилия (программиста) часто неоправданны. Поскольку ArrayList обычно оказывается лучшим выбором, большинство программистов выбирают его по умолчанию.

Избегайте ловушки преждевременной оптимизации....

Ole V.V.
9 августа 2021 в 03:27
1

Одним из случаев является добавление и удаление элементов в начале списка. Не используйте для этого LinkedList. Используйте ArayDeque. Я имею в виду, ясно.

Dog
9 августа 2021 в 03:29
0

Спасибо за ваш ответ.

Stephen C
9 августа 2021 в 03:30
0

Ну... да... но ArrayDeque не позволяет вам выполнять другие операции со списками.

avatar
Luke Nelson
9 августа 2021 в 02:37
1

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

avatar
vszholobov
9 августа 2021 в 02:34
1

ArrayList содержит массив внутри себя, и для того, чтобы быть динамичным, иногда требуется расширение внутреннего массива. Внутренняя работа ArrayList в Java