Когда нужно использовать LinkedList — пример ответа на собеседовании Android Разработчик

Когда нужно использовать LinkedList

«Когда нужно использовать LinkedList» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 23% Категория: Android Разработчик

Ответ

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

Пример:

val linkedList = LinkedList<String>()
linkedList.add("A") // O(1)
linkedList.add(1, "B") // O(n) - поиск позиции
linkedList.removeFirst() // O(1)

Но для доступа по индексу (get/set) LinkedList плох - O(n) против O(1) у ArrayList. Также LinkedList потребляет больше памяти из-за хранения ссылок. В большинстве случаев ArrayList предпочтительнее.