Back Estructuras de datos persistentes Spanish ساختار داده‌های ماندگار Persian Structure de données persistante French Varanleg gagnaskipan Icelandic Struttura dati persistente Italian 永続データ構造 Japanese 영속 자료 구조 Korean Vedvarende datastruktur NB Trwała struktura danych Polish Persistência de dados Portuguese

Persistent data structure

Not to be confused with Persistent storage.

In computing, a persistent data structure or not ephemeral 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. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article.[1]

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.[2]

These types of data structures are particularly common in logical and functional programming,[2] as languages in those paradigms discourage (or fully forbid) the use of mutable data.

  1. ^ Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). "Making data structures persistent". Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. pp. 109–121. CiteSeerX 10.1.1.133.4630. doi:10.1145/12130.12142. ISBN 978-0-89791-193-1. S2CID 364871.
  2. ^ a b Kaplan, Haim (2001). "Persistent data structures". Handbook on Data Structures and Applications.

Developed by StudentB