Toward an Understanding of (Actual) Data Structures

The myriad data structures provided by contemporary programming languages and data base management systems can no longer be differentiated by affixing a hopefully unique name to each one. Instead it is advisable to concentrate on the basic characteristics and qualities which make one data structure similar to or different from another. This paper proffers a model for common 'aggregate' data structures (including arrays, matrices, n-tuples, sequences, hierarchies, and sets) based upon this idea. The data structure model delineates an ^-dimensional space of possible data structures; each 'axis' of the space records one major characteristic for the class of aggregate data structures. Each axis is expressed as a question and a list of possible answers. The question describes the characteristic and the set of answers list the variations among the popular aggregates. A particular data structuring technique may be concretely defined by determining its value along each axis; thus, the need for individual descriptive names is lessened. Since this model is motivated by an analysis of the variations observed among a collection of actual data structures, it is called an 'analysis' model. This kind of model is useful for selecting, comparing, and teaching data structures, as well as for simply understanding exactly what a data structure is. (Received October 1976)