Allocating Storage for Extendible Arrays
- 1 October 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (4) , 652-670
- https://doi.org/10.1145/321850.321861
Abstract
Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be appended dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of the author's earlier work on data graphs and addressing schemes. A formal analog of the assertion that simplicity of array extension precludes simplicity of traversal (marching along rows/columns) is proved. Two strategies for constructing extendible realizations of arrays are formulated, and certain inherent limitations of such realizations are established.Keywords
This publication has 6 references indexed in Scilit:
- The Design of APLIBM Journal of Research and Development, 1973
- An array grammar programming systemCommunications of the ACM, 1973
- Transitions in extendible arraysPublished by Association for Computing Machinery (ACM) ,1973
- Toward an understanding of data structuresCommunications of the ACM, 1971
- Data graphs and addressing schemesJournal of Computer and System Sciences, 1971
- A model for data structures and its applications. IActa Informatica, 1971