Однажды на собеседовании мне задали вопрос: какая реализация списка быстрее вставится в середину: ArrayList или LinkedList? На первый взгляд вопрос простой — нужно посчитать алгоритмическую сложность каждого варианта и сравнить их.
Вставку в середину можно разделить на две операции: поиск середины списка и саму вставку.
Для ArrayList поиск элемента по индексу не представляет сложности, поскольку элементы списка находятся в массиве.
Алгоритмическая сложность равна O(1).
В случае с LinkedList нам придется последовательно перебирать все элементы, пока не доберемся до нужного элемента.
Сложность будет O(n).
Вставка в ArrayList предполагает сдвиг всех элементов после точки вставки, поэтому алгоритмическая сложность этой операции равна O(n).
В LinkedList вставка заключается в создании нового связывающего объекта и установке ссылок на него в соседних элементах.
Сложность O(1).
В целом сложность вставки в середину ArrayList и LinkedList одинаковая — O(n).
Я показал это рассуждение интервьюеру, на что он задал мне вопрос: «Так что быстрее: пройти по элементам или сдвинуть элементыЭ» Я быстро подсчитал, что операция чтения существенно быстрее операции записи, и сказал, что LinkedList сделает это быстрее.
Придя домой, я задумался над этим вопросом.
Искал решение этой проблемы на форумах.
Кто-то со мной согласился, но многие учли, что операция смещения выполняется родной более быстрый метод, поэтому ArrayList быстрее выполнит вставку в середину.
Не получив однозначного и неопровержимого ответа, я решил провести собственное исследование.
Сначала я углубился в исходный код этих классов.
Вставка элемента в ArrayList происходит так: сначала при необходимости массив увеличивается, затем все элементы, расположенные после точки вставки, смещаются на количество позиций, равное количеству вставленных элементов (я рассматриваю один элемент), и в конце вставленный элемент ставится на место.
Массив увеличивается со скоростью n*1,5, где n — размер массива, а минимальное увеличение при стандартных условиях (емкость=10) составляет 5 элементов.
В связи с этим операцией увеличения массива можно пренебречь при расчете алгоритмической сложности вставки.
Сдвиг элементов после точки вставки имеет алгоритмическую сложность O(n).
Таким образом, общая сложность по-прежнему остается O(n).
Да, мы помним, что операция увеличения массива немного увеличивает сложность, но нативность действий с массивом увеличивает скорость работы.
Поиск элемента в LinkedList начинается в цикле с края списка.
Если искомый элемент находится в первой половине списка, то поиск начинается с начала; иначе, с конца.
Так как мы вставляем ровно посередине, то в цикле пройдем ровно половину элементов.
Сложность O(n).
Сама вставка, как я писал выше, заключается в создании объекта и указании ссылки на него.
Сложность O(1).
Опять же, ничего нового я не обнаружил: общая сложность осталась O(n), при этом учитывая, что создание объекта — «дорогая» операция.
Анализ исходного кода ситуацию не прояснил, поэтому я начал писать тесты.
Я решил исследовать зависимость от двух параметров: исходного размера списка и количества последовательных вставок (количества итераций).
Пример исходного кода
Теги: #java #list #arraylist #linkedlist #алгоритмическая сложность #программирование #java #Алгоритмыpackage com.jonasasx.liststest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Main {
-
Обзор Принтера Kyocera Taskalfa 250Ci
19 Oct, 24 -
Windows Phone. Спешите За Приложениями
19 Oct, 24 -
Размышления О Правильности Своей Работы
19 Oct, 24 -
Расширение Opera: Вконтакте Информер
19 Oct, 24 -
Широкий Веб-Мир
19 Oct, 24
