POOL - AN UNBOUNDED ARRAY

Abstract

Many collection objects, e.g., stack, can be implemented with tabular representation (an array). Such an implementation provides fast index and saves space on linked structures. However, its space is bounded at creation time. This note presents a hybrid data structure, called pool, which combines tabular and indexed data structures. A pool is a number of segments of contiguous memory space. It provides unbounded space. Its first segment is allocated initially. When more space is needed, a new segment is allocated in double size of previous segment. All segments allocated can be accessed via an index table. The size of index table is log n, where n is the number of elements. A pool can provide index operation in O(log n) and iterations almost as fast as tabular implementation.