Examples of Persistent Data Structures
Perhaps the simplest 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. So long as the contents of the tail are immutable, this sharing will be invisible to the program.
Many common reference-based data structures, such as red-black trees, and stacks, can easily be adapted to create a persistent version. Some others need slightly more effort, for example: Queue, Double-ended queues (dequeue), Min-Dequeue (which have additional operation min returning minimal element in constant time without incurring additional complexity on standard operations of queuing and dequeuing on both ends), Random access list (with constant cons/head as single linked list, but with additional operation of random access with sub-linear, most often logarithmic, complexity), Random access queue, Random access double-ended queue and Random access stack (as well Random access Min-List, Min-Queue, Min-Dequeue, Min-Stack).
There also exist persistent data structures which use destructible operations, making them impossible to implement efficiently in purely functional languages (like Haskell), but possible in languages like C or Java. These types of data structures can be avoided with proper design. One primary advantage to using purely persistent data structures is that they often behave better in multi-threaded environments.
Read more about this topic: Persistent Data Structure
Famous quotes containing the words examples of, examples, persistent, data and/or structures:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“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)
“This city is neither a jungle nor the moon.... In long shot: a cosmic smudge, a conglomerate of bleeding energies. Close up, it is a fairly legible printed circuit, a transistorized labyrinth of beastly tracks, a data bank for asthmatic voice-prints.”
—Susan Sontag (b. 1933)
“The American who has been confined, in his own country, to the sight of buildings designed after foreign models, is surprised on entering York Minster or St. Peter’s at Rome, by the feeling that these structures are imitations also,—faint copies of an invisible archetype.”
—Ralph Waldo Emerson (1803–1882)