ℹ️ Как устроен под капотом LinkedList?

LinkedList — это двусвязный список, который реализует интерфейсы List, Deque и Queue, обеспечивая гибкость в работе с элементами на обоих концах структуры.

🔹 Структура LinkedList

LinkedList хранит свои элементы в виде узлов (Nodes), каждый из которых содержит три части:

▪️ Ссылку на предыдущий узел
▪️ Ссылку на следующий узел
▪️ Само значение элемента

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

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

▪️ Добавление: При добавлении нового элемента создается новый узел, который вставляется между двумя существующими узлами, изменяя у них ссылки. Если добавление происходит в начало или конец, обновляются только ссылки на предыдущий или следующий узел. Операции на концах занимают O(1), тогда как добавление в середину требует прохождения списка до нужного узла, что занимает O(n).
▪️ Удаление: Удаление элемента работает аналогично добавлению — обновляются ссылки соседних узлов. Удаление на концах списка занимает O(1), в середине — O(n).
▪️ Поиск: Поскольку узлы хранятся в памяти разрозненно, LinkedList не поддерживает эффективный случайный доступ. Чтобы найти элемент, нужно последовательно проходить список от начала или конца, из-за чело сложность поиска O(n).

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

🔹 Преимущества и недостатки
▪️ Преимущества: Эффективные операции добавления и удаления в начале и конце списка, отсутствие необходимости в перераспределении памяти. Полезен для реализации очередей и стеков.
▪️ Недостатки: Медленный доступ к элементам (O(n)), высокий расход памяти из-за хранения ссылок, элементы хранятся разрозненно в памяти, что может приводить к фрагментации.