Расскажите о структуре данных LinkedList и её применении.

LinkedList в Java — это реализация двусвязного списка. Каждый элемент (узел) хранит данные и ссылки на предыдущий и следующий узлы.

Ключевые характеристики:

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

Когда использовать:

• Частые операции вставки/удаления в середине списка.
• Реализация стеков, очередей или деков.
• Когда размер данных динамически меняется, а произвольный доступ не критичен.

Пример кода:

LinkedList<String> list = new LinkedList<>();
list.add("B");
list.addFirst("A"); // O(1)
list.addLast("C");  // O(1)
String first = list.get(0); // O(n) - обход с головы
list.remove(1); // Удаление элемента в середине - O(1) при известном узле

Сравнение с ArrayList: ArrayList предпочтительнее для частого чтения по индексу, LinkedList — для частой модификации структуры.