Реальный пример использования LinkedList

#java #структуры_данных

В каких случаях можно использовать LinkedList, на собеседованиях спрашивают где можно
использовать, когда привожу примеру типа как очередь или стек, они говорят что для
таких случаев есть свои Queue и Stack
    

Ответы

Ответ 1

Каноническим ответом на такой вопрос является следующий:


  LinkedList используется если необходимо производить много операций вставки/удаления
элементов в середине списка и мало операций доступа к элементу по индексу.


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

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


Потребление памяти на один элемент у LinkedList больше, чем у ArrayList (для каждого
элемента хранятся ссылки на предыдущий и следующий элементы)
Доступ к элементу по индексу медленнее (O(n) в худшем случае)


А со следующими задачами обе реализации справляются одинаково:


Поиск элемента по значению (в обеих реализациях O(n) в худшем случае)
Итерация по элементам (сложность получения следующего элемента O(1) в обоих случаях)


С учётом того что ArrayList при вставке сдвигает элементы массива достаточно быстрым
нативным методом System.arraycopy() (документация утверждает, что сложность вставки
n элементов в ArrayList будет O(n)), я бы рекомендовал в общем случае использовать
только ArrayList, а к LinkedList обращаться разве что в академических целях (например,
в бенчмарках).