Какие сложности возникают при создании новых узлов вместо изменения существующих?
Что проверяют
Вопрос обычно всплывает после задачи на связный список или дерево, которую вы решили созданием новых узлов, а не перестановкой ссылок в старых. Интервьюер хочет понять, осознаёте ли вы цену неизменяемого подхода и когда она оправдана. Следом часто просят сделать то же самое за O(1) дополнительной памяти.
Как отвечать
Сначала цена:
- память и аллокации: разворот списка из n элементов через новые узлы требует O(n) памяти вместо O(1) при перестановке ссылок. В горячем цикле это ещё и нагрузка на сборщик мусора;
- копирование пути: в неизменяемом дереве вставка пересоздаёт узлы от корня до места изменения, в сбалансированном дереве это O(log n) новых объектов. Остальные узлы переиспользуются (structural sharing);
- старые ссылки: кто держал ссылку на прежний корень, продолжает видеть старую версию. Если код ждёт, что изменение увидят все, получится тонкий баг;
- обратные ссылки: указатели на родителя и двусвязные списки плохо сочетаются с разделяемой структурой: изменение одного узла тянет пересоздание почти всего;
- идентичность: сравнение через
==ломается, нужны корректныеequalsиhashCode, например черезrecord.
Затем выигрыш, иначе ответ однобокий: неизменяемые узлы можно читать из нескольких потоков без блокировок, final-поля гарантируют безопасную публикацию, а старая версия бесплатно становится снимком для отмены или истории.
Покажите, как это выглядит в Java: List.of неизменяем, но не персистентен, и версия с новым элементом требует полной копии; Collections.unmodifiableList лишь обёртка над изменяемым списком; CopyOnWriteArrayList копирует массив на каждую запись. Персистентные коллекции есть в сторонних библиотеках, например в Vavr.
Где спотыкаются
Путают неизменяемость с Collections.unmodifiableList. Исходный список по-прежнему можно поменять, и обёртка это изменение покажет.
Считают копирование пути копированием всего дерева и делают вывод, что неизменяемые деревья всегда медленные.
Не могут переписать решение на перестановку ссылок, когда интервьюер просит убрать лишнюю память. Разворот списка тремя указателями prev, curr, next нужно писать без подсказки.