Data-Structural Bootstrapping and Catenable Deques (thesis)

Abstract:

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.