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

Report ID:

TR-423-93

Authors:

Date:

May 1993

Pages:

90

Download Formats:

The {em list} is a fundamental data structure. It stores a linearly

ordered collection of elements and allows access only to the front and

rear elements of the list. {em Catenation} can be applied to lists,

unifying the rear of one list with the front of another. Absent other

requirements, the basic list operations, including catenation, have

straightforward implementations. If the list has certain secondary

properties, however, the operations, particularly catenation, become

more difficult.

{em Non-destructive lists}, for example, support side-effect-free

list operations and are fundamental in high-level programming

languages such as LISP, ML, and Scheme. Actual implementations of

non-destructive lists usually apply simple copying methods directly to

the lists or to trees representing the lists. These copying methods

have high space and time overhead, however. {em Persistent data

structures} allow operations on old versions, and therefore techniques

for designing persistent data structures might be useful in devising

non-destructive lists. Current persistence techniques, however, can

be applied to only one version of a data structure at a time and

therefore do not accommodate list catenation. {em Heap-ordered

lists}, which provide access to minimum elements, also have efficient

implementations that do not allow catenation. These two data

structures are related: in both cases, the addition of a secondary

property complicates list catenation. In this thesis, we develop a

technique called {em data-structural bootstrapping} to address these

problems.

Bootstrapping uses two basic ideas. First, we {em abstract} a data

structure by representing it in terms of its own secondary property.

Inserting the abstracted data structure as an element into the same

type of non-catenable data structure on a higher level effects

catenation. Second, we homogeneously {em decompose} a data structure

into a group of smaller data structures. This produces an efficient,

recursive implementation.

Data-structural bootstrapping yields efficient implementations of both

non-de-struc-tive lists ($O(log^*n)$ worst-case time and space per

operation on a list of $n$ elements) and catenable heap-ordered lists

($O(1)$ amortized time per operation). The latter have applications

in pagination, network sensitivity analysis, and VLSI river routing.

Catenable heap-ordered lists derive their efficiency from a special

case of path compression that we prove takes only linear time.