Что такое LinkedList?

Реализация интерфейсов List и Deque в Java, представляющая собой двусвязный список. Каждый узел (Node) содержит ссылки на предыдущий и следующий элементы, а также данные.

Особенности:

• Вставка/удаление: Эффективно вставлять или удалять элементы в любом месте списка (O(1)), так как требуется лишь изменить ссылки у соседних узлов.
• Произвольный доступ: Доступ к элементу по индексу (get) или поиск элемента (indexOf) требуют обхода списка с начала или конца, что занимает время пропорционально положению элемента (O(n)).
• Использование памяти: Требует больше памяти по сравнению с ArrayList, так как каждый узел хранит две ссылки в дополнение к данным.
• Null-элементы: Позволяет хранить null.
• Потокобезопасность: Не является потокобезопасным по умолчанию.

Применение:

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

Пример:

// Создание LinkedList
LinkedList<String> list = new LinkedList<>();

// Добавление элементов
list.add("Apple");
list.add("Banana");
list.addFirst("Orange"); // Добавить в начало

// Удаление элемента
list.removeLast(); // Удалить последний

// Получение элемента
String firstElement = list.getFirst(); // Получить первый

// Итерация
for (String item : list) {
    System.out.println(item);
}