In computing, a persistent data structure is a data structure that 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. (A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent.")
A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral.
These types of data structures are particularly common in logical and functional programming, and in a purely functional program all data is immutable, so all data structures are automatically fully persistent. Persistent data structures can also be created using in-place updating of data and these may, in general, use less time or storage space than their purely functional counterparts.
While persistence can be achieved by simple copying, this is inefficient in CPU and RAM usage, 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.
Read more about Persistent Data Structure: Partially Persistent, Fully Persistent, Confluently Persistent, Examples of Persistent Data Structures, Reference Cycles
Famous quotes containing the words persistent, data and/or structure:
“The country needs and, unless I mistake its temper, the country demands bold, persistent experimentation. It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something. The millions who are in want will not stand idly by silently forever while the things to satisfy their needs are within easy reach.”
—Franklin D. Roosevelt (1882–1945)
“To write it, it took three months; to conceive it three minutes; to collect the data in it—all my life.”
—F. Scott Fitzgerald (1896–1940)
“The structure was designed by an old sea captain who believed that the world would end in a flood. He built a home in the traditional shape of the Ark, inverted, with the roof forming the hull of the proposed vessel. The builder expected that the deluge would cause the house to topple and then reverse itself, floating away on its roof until it should land on some new Ararat.”
—For the State of New Jersey, U.S. public relief program (1935-1943)