Data-Structural Bootstrapping and Catenable Deques (thesis)
Report ID: TR-423-93Author: Buchsbaum, Adam L.
Date: 1993-06-00
Pages: 90
Download Formats: |Postscript|
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.