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 added dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of our earlier work on data graphs and addressing schemes A formal analog of the assertion that simplicity of array extension precludes simplicity of transition (marching along rows/columns) is proved.