Подготовка к интервью
21 вопрос с ответами по теме «Связные списки»
Что проверяют на интервью
Подборка о свойствах связных списков и цене операций при разных исходных условиях. Общие алгоритмы дополнены примерами LinkedList в Java и .NET, обратного обхода, реализации очереди и использования списков в хеш-таблице.
Каталог
В реализации HashMap в Java связный список, который используется для разрешения коллизий, является односвязным.
Читать ответArrayDeque и LinkedList в Java оба реализуют интерфейсы Deque и Queue, что позволяет использовать их для организации очередей и стэков. Главное отличие в их внутренней структуре и производительности:
Читать ответОсновные трудности при операциях со связными списками:
Читать ответВ двусвязном списке получение последнего элемента обычно имеет временную сложность O(1), если у списка есть ссылка на хвостовой элемент.
Читать ответМожно использовать итератор, полученный с помощью метода descendingIterator().
Читать ответОценка памяти для хранения одного примитива byte в LinkedListByte:
Читать ответВ Java интерфейс Queue описывает структуру данных очередь — коллекцию, работающую по принципу FIFO (первым пришёл — первым вышел). LinkedList — это класс, который реализует несколько интерфейсов, включая List и Queue.
Читать ответВставка элемента в середину односвязного списка требует сначала пройти по списку от начала до нужной позиции, так как в односвязном списке нет обратных ссылок и прямого доступа к элементам по индексу.
Читать ответДобавление элемента в начало двусвязного списка выполняется за константное время, то есть имеет сложность O(1).
Читать ответВременная сложность добавления нового элемента в конец односвязного списка зависит от того, есть ли у списка указатель на последний элемент (хвост).
Читать ответВ связном списке поиск элемента по значению требует последовательного обхода узлов, начиная с головы списка, пока не будет найден нужный элемент или достигнут конец списка.
Читать ответПри вызове функции, которая считает элементы меньше 42, на массиве и на связном списке с одинаковыми данными, секундомер покажет заметно разное время из-за особенностей доступа к элементам.
Читать ответ