Different immutable versions reuse unchanged component <software objects> rather than duplicating them. Sharing a <linked list> suffix or unchanged <subtrees> saves storage while retaining distinct roots. The shared components must remain immutable for old versions to remain trustworthy. Merely sharing a mutable <array> does not create a stable snapshot.

Saving references to before/after versions adds constant reference storage per history entry, but the data reachable through those references may be much larger. With balanced-tree path copying, $h$ small updates to a size-$n$ structure can retain $O(n+h\log n)$ nodes. Whole-array copying can instead retain $\Theta(hn)$ entries. The implementation and update pattern determine which bound applies.


 Structural sharing (source code)