Два популярных списка в Java:
1. ArrayList : -Воплощена концепция динамического массива.
2. LinkedList : -Воплощена концепция двусвязного списка.
- Вставки легко и быстро в LinkedList по сравнению с ArrayList, потому что нет
риск изменения размера массива и копирования содержимого в новый массив, если массив заполнится, что делает
добавление в ArrayList O (n) в худшем случае, а добавление O (1) в LinkedList
на Яве. ArrayList также должен обновлять свой индекс, если вы вставляете что-либо, кроме
в конце массива. - Удаление также лучше в LinkedList, чем в ArrayList по тем же причинам, что и вставка.
- LinkedList имеет больше памяти, чем ArrayList, потому что в ArrayList только каждый индекс
содержит фактический объект (данные), но в случае LinkedList каждый узел содержит как данные, так и адрес
следующего и предыдущего узла. - Как LinkedList, так и ArrayList требуется O (n) время, чтобы определить, присутствует элемент или нет. Однако мы можем выполнить бинарный поиск по ArrayList, если он отсортирован, и, следовательно, можем выполнять поиск за O (Log n) времени.
В чем отличие LinkedList от ArrayList ? И в каких случаях на практике удобней использовать LinkedList ?
3 ответа 3
ArrayList — это список на основе массива. LinkedList — связанный список на основе элементов и связи между ними. В качестве LinkedList лучше всего подходит представление вагонов поезда сцепленных последовательно.
ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время. Кроме того в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются.
LinkedList удобен когда важнее быстродействие операций вставки/удаления, которые в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами.
Одним словом — если часто вставляете/удаляете — выбирайте в пользу LinkedList, в противном случае ArrayList
ArrayList основан на обычном массиве. Данная коллекция динамически увеличивает размер массива, если в нем не хватает места, при вызове методов add(T element) , addAll(Collection other) Так же она может его уменьшать, если размер больше количества хранимых элементов, методом trimToSize()
LinkedList это обычный связанный список, состоящий из узлов. В каждом узле, хранится ссылки на следующий/предыдующий узел и значение. В самом списке, есть ссылки на последний и первый узел, а так же размер.
Чтобы оценить эти структуры данных, можно прибегнуть к ассимптотической сложности выполнения операций:
В LinkedList вставка осуществляется так: находится элемент, за которым должен следовать вставляемый элемент, изменяются ссылки в нем и следующим за ним.
В ArrayList создается новый массив, если в текущем нет места. Те элементы которые находятся до вставляемого, остаются на месте, или копируются в новый. Далее добавляется вставляемый элемент. Затем копируются оставщиеся элементы, которые были в исходном.
В LinkedList чтобы найти элемент с нужным индексом, нужно пройтись поочередно по ссылкам от первого элемента и до последнего (в худшем случае). В ArrayList получения элемента происходит простым взятием по индексу из массива.
В LinkedList удаление происходит аналогично вставке. В ArrayList , примерно, так же как и при добавлении.
Как мы видем в среднем, сложности одинаковые. Но я бы не стал рекомендовать использовать LinkedList , за исключением ситуации когда, преобладает удаление или вставка в начало или конец списка.
ArrayList более предсказуем для процессора, с точки зрения расположения данных. Это массив, а там элементы расположены последовательно, занимая непрырывную область памяти. Это хорошо, так как позволяет подгружать данные в кэши процессора без cache miss’ов . Процессор не простаивает, ожидая данные из оперативной памяти. С LinkedList такого нет, т.к. элементы располагаются в разных участках памяти, и предугадать расположение следующего элемента процессору не под силам.
Код демонстрирующий разницу в производительности:
На моем компьютере получилось следующее:
Из результатов видно, что LinkedList в 14 раз медленнее.
Очередь просмотра
Очередь
- Удалить все
- Отключить
YouTube Premium
Хотите сохраните это видео?
- Пожаловаться
Пожаловаться на видео?
Выполните вход, чтобы сообщить о неприемлемом контенте.
Понравилось?
Не понравилось?
Текст видео
ArrayList, LinkedList. Java собеседование
00:00 Cобеседование на позицию Java Developer
01:35 Коллекции в Java.
01:42 Разница между ArrayList и LinkedList
03:41 Преимущества и недостатки ArrayList
05:14 Преимущества и недостатки LinkedList
07:10 Вставка и удаление элементов
08:12 Что быстрее LinkedList или ArrayList?
09:05 Копирование элементов в ArrayList. Метод arraycopy в ArrayList
09:45 Поиск элемента в LinkedList и в ArrayList
10:48 Разминка для ума. Задание
Всем привет. Меня зовут Александр. Я собираюсь отснять серию роликов посвященных прохождению собеседований на работу в сфере IT и в частности на позицию Java developera — кем я и являюсь. Эти ролики в основном рассчитаны на начинающих разработчиков и возможно для тех, кто уже имеет некоторый опыт, но хотел бы освежить свои знания перед предстоящим собеседованием.
Я заметил что в большинстве своем все вопросы повторяются. Наиболее часто задаваемые я и собираюсь разобрать. Конечно же все учесть не получится, но то о чем я буду говорить поможет вам найти ответы самостоятельно. Также если вы столкнулись с вопросами которые я здесь не разобрал и они встречаются достаточно часто, то я в следующих видосах постараюсь их разобрать.
Посещая собеседования в различных фирмах я заметил что самая часто встречающаяся тема это коллекции. Поэтому начать я хочу с них.
Расскажите в чем разница между ArrayList и LinkedList
Это вопрос из разряда тех, ответ на который, должен знать каждый. Если вы не знаете то оставайтесь дома и почитайте что-нибудь по теме. К собеседованию вы не готовы!
Основное разница заключается в том что эти два списка имеют различную реализацию. ArrayList реализован на основе массива, а LinkedList на основе двусвязного списка. Особенности реализации дают нам те или иные преимущества и недостатки.
Расскажите про недостатки и плюсы ArrayList
ArrayList — то что в основе массив это нам дает как плюсы так и минусы. Плюс это возможность получать доступ к элементам по индексу за константное время. А минусом будет то что в Java все массивы имеют фиксированный размер. Следовательно мы не можем добавлять элементы бесконечно. (В отличие от LinkedList где подобной проблемы нет) Когда количество элементов в ArrayList превышает размер массива лежащего в основе, происходит создание нового массива и перезапись туда всех элементов старого массива + новый. Как вы понимаете это замедляет операцию вставки. Несмотря на это вставка в конец списка происходит в среднем за константное время. С удалением последнего элемента также все просто. Оно выполняется за константное время.