A new representation for linear lists

Abstract

We present a new data structure for maintaining a set of records in a linear list according to their key values. This data structure has the property that we can keep a number of fingers at points of interest in the key space (e.g., the beginning or the end of the list), so that access and modification in the neighborhood of a finger is very efficient.