永続データ構造
よりよい手法は、木構造を使ってバージョン間の類似性を表す方法である。しかし、バージョンが増えるにつれてバージョン間でどの部分が共通なのかを判断することが難しくなり、古いバージョンを捨てられるのが望ましい場合も多いため、ガベージコレクションが可能な環境が必要となる。
最も単純な永続データ構造は片方向連結リストや cons ベースのリストである(リスト上の次のオブジェクトへの参照のある単純なリスト)。このようなリストの尾部を共有し、変更部分だけを先頭のノードとして新たに追加することで永続性を実現できる。尾部がコピーされることはなく、新しいリストと古いリストで共有される。尾部の内容がイミュータブルであれば、この共有は振る舞いとして現れない。
赤黒木やキューのような多くの参照ベースのデータ構造は、容易に永続版にすることができる。配列の永続版として Phil Bagwell が 2002年に示した VList というデータ構造がある。