Content deleted Content added
Add section on converting to use purely functional data structures. |
m The related article 'Persistent data structures' is worth highlighting with the usual 'See also' section |
||
Line 52:
====Example: queue====
[[Amortized queue]]s{{r|Okasaki-book|p=65}}{{r|Okasaki-book|p=73}} are composed of two singly-linked lists: the front and the reversed rear. Elements are added to the rear list and are removed from the front list. Furthermore, whenever the front queue is empty, the rear queue is reversed and becomes the front, while the rear queue becomes empty. The amortized time complexity of each operation is constant. Each cell of the list is added, reversed and removed at most once. In order to avoid an inefficient operation where the rear list is reversed, [[real-time queue]]s add the restriction that the rear list is only as long as the front list. To ensure that the rear list becomes longer than the front list, the front list is appended to the rear list and reversed. Since this operation is inefficient, it is not performed immediately. Instead, it is carried out for each of the operations. Thus, each cell is computed before it is needed, and the new front list is totally computed before a new inefficient operation needs to be called.{{cn|date=December 2018}}
==See also==
* [[Persistent data structure]]
==References==
| |||