Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

In this paper we consider the problem of efficiently implementing a set of side-effect-free procedures for manipulating lists. These procedures are:

makelist(d): Create and return a new list of length 1 whose first and only element is d.

first(X): Return the first element of list X.

pop(X): Return a new list that is the same as list X with its first element deleted. This operation does not effect X.

catenate(X,Y ): Return a new list that is the result of catenating list X and list Y , with X first, followed by Y (X and Y may be the same list). This operation has no effect on X or Y .

We show how to implement these operations so that makelist(d) runs in constant time and consumes constant space, and catenate(X,Y ) runs in time (and consumes space) proportional to log log k, where k is the number of list operations done up to the time of the catenation. All of these time and space bounds are amortized over the sequence of operations.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/665

[2] http://www.cs.princeton.edu/research/techreps/author/465

[3] http://www.cs.princeton.edu/research/techreps/author/384

[4] ftp://ftp.cs.princeton.edu/techreports/1990/299.pdf