Прочитав этот вопрос Неизменяемый или не неизменяемый?] и чтение ответов на мой предварительный Если у меня есть вопросы о неизменяемости, я все еще немного озадачен эффективной реализацией простого неизменяемого LinkedList. С точки зрения массива это кажется простым - скопируйте массив и верните новую структуру на основе этой копии.
Предположительно, у нас есть общий класс Node:
class Node{
private Object value;
private Node next;
}
И класс LinkedList, основанный на вышеизложенном, позволяющий пользователю добавлять, удалять и т. д.Теперь, как мы можем гарантировать неизменность? Должны ли мы рекурсивно копировать все ссылки в список при вставке элемента?
Меня также интересуют ответы в Immutable or not immutable?, в которых упоминается определенная оптимизация, приводящая к log(n) времени и пространству с помощью бинарного дерева. Кроме того, я где-то читал, что добавление элемента на передний план также равно 0 (1). Это меня очень озадачивает, как будто мы не предоставляем копию ссылок, тогда на самом деле мы модифицируем одни и те же структуры данных в двух разных источниках, что нарушает неизменность...
Будет ли какой-либо из ваших ответов работать над двусвязные списки? Я с нетерпением жду любых ответов/указателей на любые другие вопросы/решения. Заранее спасибо за помощь.