Elastica a Large Scale Elastic Array Data Structure

摘要

In this paper, we present an elastic array, called Elastica (Elastic Array). The Elastica is the most space efficient resizable array, that is, Elastica allows increment and decrement of an array size. The Elastica is an array-of-array data structure which promotes increment and decrement of an array size dynamically. Most interestingly, the Elastica allocates memory blocks-wise and provides a functionality of accessing an element with O(1) time complexity. The Elastica allows the available memory blocks to be non-contiguous without violating the properties of the conventional single dimensional array. The Elastica offers the most space-efficient resizable array with O (log2n) extra space complexity. The Elastica is used to implement various data structures similar to conventional array. Besides, the Elastica has got other added advantages in implementing the available data structure.