LinkedList

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

List<String> queue = new LinkedList<>();
queue.add("первый");
queue.add("второй");
queue.add(0, "новый первый");   // вставка в начало — дёшево для LinkedList

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

Копнуть глубже

Когда LinkedList выгоднее ArrayList: частые вставки/удаления в начало или середину списка. У ArrayList это означает сдвиг всех элементов после точки вставки — дорого. У LinkedList — просто переставить пару ссылок у соседних узлов.

Когда ArrayList выгоднее: доступ по индексу get(i). У ArrayList это мгновенно (прямой переход по адресу в массиве), у LinkedList — нужно пройти по цепочке от начала до нужного узла.

	`ArrayList`	`LinkedList`
`get(i)`	быстро	медленно (проход по цепочке)
вставка в середину	медленно (сдвиг)	быстро (перестановка ссылок)
память	компактнее	больше (хранит ссылки у каждого узла)

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

🎤 Закрыл тему, если можешь объяснить:

• чем устройство `LinkedList` отличается от `ArrayList`;
• когда `LinkedList` реально выгоднее `ArrayList` (если дошёл до 2-го слоя).