Fully persistent lists with catenation
James R. Driscoll, Daniel D. Sleator, Robert Endre Tarjan · Journal of the ACM · 1994
This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O(log log k ) time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.