Growing a Language

Higher-Order and Symbolic Computation -     

Random access in a list environment

A memory allocation scheme for list structures (ral system) is proposed, which allows random access and search for the elements of the structure. A comparative study of classical list systems and ral systems is given, for the basic operations of search, insertion, deletion and sorting of the structure elements. It is shown that, in general, ral systems exhibit lower order expected time complexities for such operations, possibly at the expense of a reasonable increase in memory occupation. Allocation and processing of linear ordered lists and trees are discussed in particular.     

Maintaining order in a generalized linked list

Summary We give a representation for linked lists which allows to efficiently insert and delete objects in the list and to quickly determine the order of two list elements. The basic data structure, called an indexed BB []-tree, allows to do n insertions and deletions in O(n log n) steps and determine the order in constant time, assuming that the locations of the elements worked at are given. The improved algorithm does n insertions and deletions in O(n) steps and determines the order in constant time. An application of this provides an algorithm which determines the ancestor relationship of two given nodes in a dynamic tree structure of bounded degree in time O(1) and performs n arbitrary insertions and deletions at given positions in time O(n) using linear space.