Изменения
→Преобразование списка в персистентный за O(1)
==Преобразование списка в персистентный за O(1)==
Если скомбинировать методы ''path copiyng'' и ''fat node'', то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного логарифма памяти.
Пусть мы имеем [[Список| двусвязный список]] и хотим внести в него какое-то изменение, например, добавить узел <tex>Z</tex> между узлами <tex>X</tex> и <tex>Y</tex>, то есть при переходе из версии <tex>1</tex> в версию <tex>2</tex> добавим в наш двусвязный список узел <tex>Z</tex>.
Применим метод «толстых» узлов. Для этого в узлы <tex>X</tex> и <tex>Y</tex> добавим вторую версию и изменим ссылку, следующую из <tex>X</tex>, и предыдущую перед <tex>Y</tex>, как показано на рисунке.
Эта структура работает так. Например, мы знаем, что текущая первая версия и идем по нашему списку слева направо от первого узла к узлу <tex>X</tex>, а затем хотим перейти к следующему узлу. В «толстом» узле <tex>X</tex> мы выбираем нужную нам версию и далее следуем по ссылкам.
