< H / $ > Хак/Собесов

Перейти на PRO

Является ли LinkedList в Java двусвязным списком?

«Является ли LinkedList в Java двусвязным списком?» — вопрос из категории Java Core, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Java Core Вероятность: 10% Категория: Java Разработчик

Ответ

Да, стандартный java.util.LinkedList реализован как двусвязный список. Каждый узел (Node) хранит ссылки на следующий и предыдущий элементы.

Внутренняя структура узла (упрощенно):

private static class Node<E> {
    E item;        // Данные элемента
    Node<E> next;  // Ссылка на следующий узел
    Node<E> prev;  // Ссылка на предыдущий узел
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Преимущества двусвязной структуры:

Эффективные операции на концах: Добавление (addFirst, addLast) и удаление (removeFirst, removeLast) выполняются за O(1), так как есть прямой доступ к голове и хвосту.
Двунаправленная итерация: ListIterator для LinkedList позволяет двигаться как вперёд (next()), так и назад (previous()).
Удаление во время итерации происходит эффективно, так как узел знает своих соседей.

Пример использования итератора:

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

ListIterator<String> iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
    System.out.println(iterator.previous()); // Выведет C, B, A
}