The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable.
Efficient purely functional data structures may require the use of lazy evaluation and memoization.
[citation needed] In the book Purely functional data structures, Okasaki compares destructive updates to master chef's knives.
For example, a data structure using an array and destructive updates may be replaced by a similar data structure where the array is replaced by a map, a random access list, or a balanced tree, which admits a purely functional implementation.
However, if the language is not purely functional, the run-time system may be unable to guarantee immutability.
[citation needed] One of the central challenges in adapting existing code to use purely functional data structures lies in the fact that mutable data structures provide "hidden outputs" for functions that use them.
Therefore, lazy evaluation naturally becomes an important part of the construction of purely functional data structures.
[citation needed] One of the key tools in building efficient, purely functional data structures is memoization.
It is not acceptable either for real-time or for imperative systems, where the user may require the time taken by the operation to be predictable.
[1]: 83 [citation needed] In order to avoid those problems, some data structures allow for the inefficient operation to be postponed—this is called scheduling.
[clarification needed] Amortized queues[1]: 65 [1]: 73 are composed of two singly-linked lists: the front and the reversed rear.