что быстрее arraylist или linkedlist

Разница между ArrayList и LinkedList в Java – коде и производительности

В этой статье мы рассмотрим, в чем разница между ArrayList и LinkedList в Java. Мы сравним их код и производительность, чтобы подчеркнуть различие.

Вступление

Списки-это некоторые из наиболее часто используемых структур данных. В Java распространенным вопросом при использовании реализации List является:

Какую реализацию я использую?

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

Обзор списков на Java

Списки-это структуры данных, используемые для хранения последовательных элементов. Это означает, что у каждого элемента списка есть как предшественник, так и преемник (за исключением первого и последнего, конечно, – у них есть только один из каждого).

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

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

ArrayList и LinkedList являются двумя различными реализациями этих методов. Однако LinkedList также реализует интерфейс Очередь|/.

Внутренняя работа ArrayList и LinkedList

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

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

Сравнение реализаций ArrayList и LinkedList

Извлечение Элементов С Помощью get()

Извлечение Элементов С Помощью get()

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

Список ссылок.get()

Ранее мы упоминали, что связанный список не существует в одном месте в памяти, а содержит разные узлы, соединенные друг с другом. Чтобы извлечь элемент, список необходимо просмотреть с начала (или до конца, в зависимости от того, что ближе) и следовать соединениям каждого узла, пока не будет найден нужный элемент.

Реализация того же метода выглядит следующим образом:

Это делается за O(N) время по сравнению с ArrayList ‘s O(1) время.

Вставка Элементов С Помощью add()

По сути, любой вид вставки может быть обобщен и реализован с использованием одного общего метода – вставки по заданному индексу.

ArrayList.добавить()

Однако вставить в заданную позицию немного сложнее. Вы должны разбить массив в том месте, которое хотите вставить – скопируйте все после этой точки и переместите его вправо, добавив новый элемент в индекс:

Чем больше скопированная часть, тем медленнее выполняется эта операция. Это делает добавление элементов в ArrayList относительно неэффективной операцией. Тем не менее, добраться до точки, где должна быть выполнена вставка, действительно эффективно.

Список ссылок.добавить()

Реализация LinkedList позволяет нам довольно легко добавлять элементы в любой заданный индекс. Вы просто указываете указатели head и tail предыдущего и последующего элементов на новый, соответственно. Если вы вставляете в начале или в конце списка, необходимо обновить только один указатель.

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Давайте взглянем на реализацию:

Независимо от того, насколько велик список, нужно изменить только два указателя. Это делает добавление элементов в Связанный список высокоэффективной операцией. Однако достижение позиции, в которую должен быть вставлен элемент, является неэффективным.

Поиск Элементов С индексом()

ArrayList.indexOf()

В реализации ArrayList это делается с помощью простого для цикла, идущего от 0 в размер-1 и проверка соответствия элемента текущего индекса заданному значению:

Это буквально линейный поиск, который не очень эффективен, но на самом деле это единственный способ поиска элемента в перетасованной коллекции (если мы игнорируем метаэвристические алгоритмы и приближения).

Список ссылок.индекс()

Связанный список делает это немного по-другому. Вместо того, чтобы перебирать массив, он должен перемещаться по списку, переходя от одного элемента к другому с использованием указателей. В конечном счете, результат один и тот же – посещение каждого элемента по одному, пока не будет найден искомый:

Удаление Элементов С Помощью Функции удалить()

ArrayList.удалить()

Чем больше скопированная часть, тем медленнее выполняется эта операция. Опять же, это делает удаление элементов из ArrayList неэффективной операцией. Хотя, хорошая вещь в ArrayList s заключается в том, что вы можете очень легко добраться до этого элемента. elementData(индекс) возвращает элемент, который вы хотите удалить в O(1) время.

Список ссылок.удалить()

Удаление элемента из Связанного списка выполняется путем отсоединения предыдущего и последующих указателей от элемента, который мы хотели бы удалить. После этого предыдущий элемент связывается со следующим в строке. Таким образом, старый элемент “застрял”, и без каких-либо ссылок на него GC заботится о нем:

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

Сравнение Производительности

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

В этом разделе мы кратко сравним две реализации с точки зрения производительности:

Кредиты: Миро Медиум

Сравнение get()

Сравнение вставки()

Сравнение удалить()

LinkedList s имеют O(1) сложность для удаления с начала или конца и O(N) в других случаях.

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

Вывод

ArrayList и LinkedList являются двумя различными реализациями интерфейса List|/. У них есть свои различия, которые важно понимать, чтобы правильно их использовать.

Источник

Отличие ArrayList от LinkedList?

3 ответа 3

ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время. Кроме того в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются.

LinkedList удобен когда важнее быстродействие операций вставки/удаления, которые в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами.

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

Чтобы оценить эти структуры данных, можно прибегнуть к ассимптотической сложности выполнения операций:

В LinkedList вставка осуществляется так: находится элемент, за которым должен следовать вставляемый элемент, изменяются ссылки в нем и следующим за ним.

В ArrayList создается новый массив, если в текущем нет места. Те элементы которые находятся до вставляемого, остаются на месте, или копируются в новый. Далее добавляется вставляемый элемент. Затем копируются оставщиеся элементы, которые были в исходном.

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

Код демонстрирующий разницу в производительности:

На моем компьютере получилось следующее:

Из результатов видно, что LinkedList в 14 раз медленнее.

Источник

ArrayList vs. LinkedList

— Как насчёт немного размять мозги? Надеюсь, они ещё не закипели.

— В таблице контейнеров и коллекций ты ранее видел, что у одного и того же интерфейса может быть несколько реализаций. Сейчас я расскажу тебе, зачем это нужно. И в чем отличие ArrayList от LinkedList.

— Все дело в том, что коллекции могут быть реализованы разными способами и нет единственного – самого правильного. При одном подходе одни операции являются быстрыми, а остальные медленными, при другом – все наоборот. Нет одного идеального, подходящего всем решения.

— Ага. Кое-что начинает проясняться. А есть какие-нибудь критерии или правила, когда какая коллекция лучше?

— Ну, для простоты, я бы сформулировала такое правило: если ты собираешься вставлять (или удалять) в середину коллекции много элементов, то тебе лучше использовать LinkedList. Во всех остальных случаях – ArrayList.

— Как они устроены мы разберем в старших уровнях, а пока будем учиться ими пользоваться.

Источник

Вставка в середину: ArrayList против LinkedList

Как-то на собеседовании мне задали вопрос: какая реализация списка выполнит вставку в середину быстрее: ArrayList или LinkedList? С первого взгляда вопрос простой — нужно посчитать алгоритмическую сложность каждого варианта и сравнить их. Вставку в середину можно разделить на две операции: поиск середины списка и саму вставку. Для ArrayList поиск элемента по индексу не составляет труда, так как элементы списка находятся в массиве. Алгоритмическая сложность составляет O(1). В случае LinkedList придётся последовательно перебрать все элементы, пока не доберёмся до нужного элемента. Сложность будет O(n). Вставка в ArrayList связана со сдвигом всех элементов, находящихся после точки вставки, поэтому алгоритмическая сложность этой операции O(n). В LinkedList вставка заключается в создании нового связующего объекта и установки ссылок на него у соседних элементов. Сложность O(1). В сумме сложность вставки в середину у ArrayList и у LinkedList получается одинаковая — O(n). Эти рассуждения я показал интервьюеру, на что он мне задал вопрос: «Так что всё-таки быстрее: пробежаться по элементам или сместить элементы?». Я быстро прикинув, что операция чтения по сути быстрее операции записи, сказал, что LinkedList справится быстрее.
Когда я пришёл домой, я задумался над этим вопросом. Поискал решение этой задачи на форумах. Кто-то был согласен со мной, но многие учли, что операция смещения производится native методом, который работает быстрее, поэтому ArrayList выполнит вставку в середину быстрее. Не получив окончательного и неопровержимого ответа, я решил провести собственное исследование.

Сперва я углубился в изучение исходного кода этих классов. Вставка элемента в ArrayList проходит так: сначала, при необходимости, массив увеличивается, затем все элементы, стоящие после места вставки сдвигаются на число позиций, равное количеству вставляемых элементов (я рассматриваю один элемент), и в конце встаёт на свое место вставляемый элемент. Массив увеличивается со скоростью n*1,5, где n — размер массива, а минимальное увеличение при стандартных условиях (capacity=10) — 5 элементов. В связи с этим, операцией по увеличению массива при расчёте алгоритмической сложности вставки можно пренебречь. Сдвиг элементов, находящихся после точки вставки обладает алгоритмической сложностью O(n). Таким образом общая сложность всё равно остаётся O(n). Да, мы держим в уме, что операция увеличения массива незначительно повышает сложность, но нативность действий с массивом увеличивает скорость работы.

Поиск элемента в LinkedList начинается в цикле от края списка. Если искомый элемент находится в первой половине списка, то поиск идёт с начала, в обратном случае — с конца. Так как мы вставляем именно в середину, то в цикле пройдём ровно половину элементов. Сложность O(n). Сама вставка, как я уже писал выше, заключается в создании объекта и указании ссылок на него. Сложность O(1). Опять же ничего нового я не выяснил: общая сложность осталась O(n), при этом держим в уме, что создание объекта — «дорогая» операция.

Анализ исходного кода ситуацию не разъяснил, поэтому стал писать тесты. Я решил исследовать зависимость от двух параметров: начальный размер списка и количество вставок подряд (количество итераций).

Для каждого размера списка и количества итераций создаются по одному массиву ArrayList и LinkedList, они заполняются одинаковыми объектами, после чего под замер скорости производится n вставок одного объекта в середину. В качестве сравниваемой величины я использую десятичный логарифм от отношения времён выполнения ArrayList к LinkedList. Когда это значение меньше нуля, ArrayList справляется быстрее, когда больше — быстрее LinkedList.

Привожу результаты теста в таблице:

На оси X указан изначальный размер списка, линии представляют разные количества итераций, а на оси Y отношение скорости работы двух реализаций списка.

Так как с каждой итерацией размер списка увеличивается, можно сделать общий вывод: LinkList работает быстрее при небольшом размере списка. Но самое главное: без чёткой конкретизации условий сравнивать скорость работы этих двух алгоритмов нельзя!

Чтобы увеличить точность, я отказался от параметра количества вставок и уменьшил шаг размера до одного. Для каждого из размеров я провёл тест тысячу раз и взял среднее значение. Получил график:

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

Общий вывод можно сделать такой: операция вставки в середину происходит в основном быстрее в ArrayList, но не всегда. С теоретической точки зрения нельзя однозначно сравнить скорость этих двух алгоритмов без учёта изначального размера списка.

Спасибо за внимание, надеюсь, кому-то моя работа покажется интересной и/или полезной.

Источник

Сравнение скорости работы ArrayList и LinkedList на практике

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

Рекомендую предварительно прочитать расширенные посты про работу:
ArrayList — habrahabr.ru/post/128269
LinkedList — habrahabr.ru/post/127864

Почему решил измерять? Потому, что после изучения информации остались пробелы, где и что всё-таки быстрее. Особенно сподвиг прочтенный комментарий к статье про LinkedList:

Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.

Начнем. Как замерял?
Возможно, у кого-то возникнут сомнения по-поводу корректности замера, но результаты оказались в некоторых ситуациях очень схожи с теорией.
Пример кода, с помощью которого делал один из типов замеров:

k — во всех замерах разное, т.к. где-то для получения результата нужно 3 миллиона операций, а где-то 10 тысяч достаточно, т.к. при 3 миллионах необходимо ждать не одну минуту.

==============Insert=================
—Insert elements to begin( 100k )
LinkedList: 132 ms
ArrayList: 2742 ms
LinkedList is faster

—Insert elements to middle( 60k )
LinkedList: 4110 ms
ArrayList: 494 ms
ArrayList is faster

==============Remove=================
—Remove elements from begin ( 100k )
LinkedList: 2 ms
ArrayList: 3220 ms
LinkedList is faster

—Remove elements from middle ( 100k )
LinkedList: 7519 ms
ArrayList: 1544 ms
ArrayList is faster

—Remove elements from end ( 1kk )
LinkedList: 37 ms
ArrayList: 8 ms
ArrayList is faster

==============Get====================
—Get elements from begin ( 4kk )
LinkedList: 25 ms
ArrayList: 7 ms
ArrayList is faster

—Get elements from middle ( 40k )
LinkedList: 2320 ms
ArrayList: 0 ms
ArrayList is faster

—Get elements from end ( 3kk )
LinkedList: 23 ms
ArrayList: 5 ms
ArrayList is faster

==============Set====================
—Set elements at begin ( 1kk )
LinkedList: 342 ms
ArrayList: 12 ms
ArrayList is faster

—Set elements at middle ( 50k )
LinkedList: 3734 ms
ArrayList: 1 ms
ArrayList is faster

—Set elements at end ( 3kk )
LinkedList: 40 ms
ArrayList: 267 ms
LinkedList faster

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

Комментарии обязательные к ознакомлению:
Ув. denonlink

Источник