Давайте попробуем разобраться с этим шаг за шагом.
Как правило, при создании неизменяемого объекта все параметры конструктора должны быть известны в момент его создания, но давайте обманем и передадим параметры конструктора по имени.затем используйте ленивые поля для задержки оценки, чтобы мы могли создать двунаправленную связь между элементами:
// p and n are passed by name
// and won't be evaluated until prev and next are accessed
// for the first time
class Element [T] (val value: T, p : => Element[T], n : => Element [T]) {
lazy val prev = p
lazy val next = n
}
val e1:Element[Int] = new Element [Int] (1,null,e2)
val e2:Element[Int] = new Element [Int] (2,e1,e3)
val e3:Element[Int] = new Element [Int] (3,e2,e4)
val e4:Element[Int] = new Element [Int] (4,e3,null)
Как только мы запустим код, мы получим неизменный список с двойной связью:
null← e1 (1) ↔ e2 (2) ↔ e3 (3) ↔ e4 (4) → null
И сможет пройти его туда-сюда:
println(e1.next.next.next.value)
println(e4.prev.prev.prev.value)
4
1
Теперь,скажем, мы хотим добавить пятый элемент в конец списка, чтобы он выглядел так:
null ← e1 (1) ↔ e2 (2) ↔ e3 (3) ↔ e4 (4) ↔ e5 (5) → null
val e5:Element[Int] = new Element [Int] (5,e4,null)
В какой момент мы получим:
null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null
↖ ↑
e5(5)
Подождите минутку, это выглядит неправильно! e4 должен указывать на e5 вместо того, чтобы указывать на null , но e4 является неизменным, и мы не можем изменить сам элемент,таким образом, похоже, что единственный вариант - сделать копию вместо нее и указать ее на e3 и e5 .Давайте попробуем применить этот новый подход к начальному списку:
ноль ← e1 (1) ↔ e2 (2) ↔ e3 (3) ↔ e4 (4) → нуль
val e4_b: Element[Int] = new Element [Int] (e4.value, // keeping original value
e3,e5)
val e5 : Element[Int] = new Element [Int] (5,e4_b,null)
Это лучше, e4_b приводит к e5 , что приводит к e4_b:
null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null
↖ ↑
e4_b(4) ↔ e5(5)
Но теперь у нас та же самая оригинальная проблема, только с e3 , которая все еще указывает на e4 .Вы видите тенденцию появления?Если бы мы продолжали копировать элементы, чтобы исправить проблему очень скоро, мы бы получили:
null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null
↑ ↑
e1_b(1) ↔ e2_b(2) ↔ e3_b(3) ↔ e4_b(4) ↔ e5(5)
Исходный список немного не изменился (как оказалось, мы не называли «неизменяемый» ни за что), вместо этого мы получили совершенно новый список, хотя и с теми же значениями.Поэтому всякий раз, когда мы пытаемся внести изменения в неизменную структуру данных с двойной связью, нам нужно перестраивать всю вещь с нуля, сохраняя значения .
Давайте вместо этого взглянем на стандартный односвязный неизменяемый список Scala:
e1 (1) → e2 (2) → e3 (3) → e4 (4) → Nil
Мы заметим, что мы можем легче создавать новые списки без необходимости перестраивать всю структуру данных с нуля, например, чтобы удалить второй элемент, нам просто нужно сделать копию первого и указать егок третьему:
e1(1) → e2(2) → e3(3) → e4(4) → Nil
↗
e1_b(1)
И, конечно, поскольку исходный список неизменен, он действительно не изменился.