Persistent data structure
|
|
In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. These type of data structures are particularly common in functional programming, because in a purely functional program all data is immutable.
While this can be achieved by simple copying, this is inefficient in time and space, because most operations make only small changes to a data structure. A better method is to exploit the similarity between the new and old versions to share structure between them, such as using the same subtree in a number of tree structures. However, because it rapidly becomes infeasible to determine how many previous versions share which parts of the structure, and because it is often desirable to discard old versions, this necessitates an environment with garbage collection.
Among the most primitive type of persistent data structure is the singly-linked list or cons-based list, a simple list of objects formed by each carrying a reference to the next in the list. This is persistent because we can take a tail of the list, meaning the last k items for some k, and add new nodes on to the front of it. The tail will not be duplicated, instead becoming shared between both the old list and the new list.
Many common reference-based data structures can be adapted to create a persistent version, such as red-black trees, splay trees, and queues. More problematic are arrays; no efficient persistent data structure has duplicated all their unique properties.Template:Comp-sci-stub