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:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“The passion of self-aggrandizement is persistent but plastic; it will never disappear from a vigorous mind, but may become morally higher by attaching itself to a larger conception of what constitutes the self.”
—Charles Horton Cooley (1864–1929)
“Mental health data from the 1950’s on middle-aged women showed them to be a particularly distressed group, vulnerable to depression and feelings of uselessness. This isn’t surprising. If society tells you that your main role is to be attractive to men and you are getting crow’s feet, and to be a mother to children and yours are leaving home, no wonder you are distressed.”
—Grace Baruch (20th century)
“If there are people who feel that God wants them to change the structures of society, that is something between them and their God. We must serve him in whatever way we are called. I am called to help the individual; to love each poor person. Not to deal with institutions. I am in no position to judge.”
—Mother Teresa (b. 1910)