Сравнение эффективности ArrayList и LinkedList для добавления элементов в середину #java

Подписывайся на канал и забирай свежий и полезный контент из мира программирования!

Получи реальный опыт решения коммерческих задач в Agile команде

Запись на обучение и собеседование:

Телеграм-канал с полезностями:

[randomnickname]

запостили неверный ответ на вопрос лул?

[Хитрый_Птиц]

Тут очень интересная история ) Если у нас есть структура из 100 000 элементов, то кто-то же уже определил изначальную структуру. ) Значит необходимо работать с тем, что есть. )
Ну а что эффективнее если у нас изначальные данные в виде "сферического коня в вакууме", то...
ArrayList под капотом является "надстройкой" над обычным массивом.
И вставить элемент в середину, это значит переиндексировать 2ю половину массива. (шифтонуть или как там это на программистском).
Мне кажется, что чтение и переход по ссылкам в линкед листе и вставка ноды будет быстрее, чем сдвиг массива...

[salavat_smile]

Если это практика то ArrayList выбираем из-за нативного быстрого копирования в современных архитектурах компьютера. А теоретически то LinkedList.

[ValentinMishin]

в связанном списке - за О(N) нашел середину, за О(1) вставил(изменил указатели у соседних элементов)
в массиве, если вставка по индексу, за О(1) нашел, а вот сама вставка зависит от реализации конкретной jvm функции native arraycopy(из-за сдвига элементов), в обоих случаях : есть ли место в массиве или если нет ( с последующим копированием в новый, под который выделено больше памяти)

[iono]

Вставка и удаление:
LinkedList: Вставка и удаление элементов в середине связанного списка выполняются быстро, так как не требуется перемещать все элементы. Однако доступ к элементам по индексу более затруднен.
ArrayList: Вставка и удаление элементов в середине массива списка могут быть медленными, так как требуется перемещение всех элементов после изменяемого индекса. Однако доступ к элементам по индексу осуществляется быстро

[ShaddTM]

Если оценивать Complexity с Big O Notation, то разницы особо и нет. И там и там будет O(n)

[Alex-jxbz]

Не поленился, проверил на 1млн элементов. Как уже выше озвучил человек, в теории у нас LinkedList будет быстрее (не надо сдвигать), а на практике ArrayList минимум на порядок все делает быстрее т.к. System.arraycopy настолько реактивно отрабатывает, что все аргумент за LinkedList просто расстворяются в воздухе. Вот такая суровая реальность!

[tihonpug]

А разве не лучше linkedlist, ведь если у нас не хватает емкости массива, то у нас будет перезапись в новый массив всех элементов
В случае с связанным списком, то мы итерируемся и находим середину и вставляем элемент, изменяя ноду

[ИванФаков-вд]

LinkedList не нужен) никто его не использует. ArrayList основан на массиве, операции с которыми выполняются очень быстро на аппаратном уровне

[bebra]

В любом случае лучше использлвать arrayList. Особоенно если доступ к элементам нужен часто

[seepwalker]

Есть такое ощущение, что автор не прав, можно много теоретически рассуждать, но вся экономия на спичках должна быть оправдана и подтверждена реальными тестами. Вот по крайней мере в этом бенчмарке (гуглите: Java Benchmark Adventures - ArrayList vs LinkedList) вставка в середину списка проводилась быстрее на ArrayList. ArrayList проиграл в скорости только при добавлении в самом начале и в самом конце списка. Хочется бенчмарков от автора, подтверждающих его слова, либо лучше разбираться в матчасти. Джава, конечно, может и делает все с космической скоростью, но LinkedList раскидан по памяти, а последовательное чтение происходит значительно быстрее, чем случайное