= Persistent data structure
{wiki}
A <data structure> whose previous versions remain usable after an update. An immutable representation can return a new root while retaining old roots. Persistence is a version-availability property; it does not require copying the whole structure, and it does not by itself guarantee a particular <time complexity> or <space complexity>.
Path copying in a balanced <tree> can preserve old versions while allocating only the updated root-to-leaf path. A <linked list> can share an unchanged suffix but may copy a long prefix for a positional edit. Retained versions extend the lifetime of their reachable data, which matters when comparing snapshot history with edit-specific inverse commands.
Back to article page
