Succinct Representation of Data Structures:Arrays

Arrays

Resizable Arrays

A basic problem that arises in many applications is accumulating elements into a list when the number of elements is unknown ahead of time. The operations needed from such a structure are the ability to append elements to the end of the structure, removing the last element from the structure (in applications such as implementing a stack) and some method of accessing the elements currently in the structure.

One simple solution is a linked list which can easily grow and shrink, and supports sequential access. But this does not support random access to the elements. Moreover, its space overhead is O(n) pointers to store n elements.

Another standard solution is the doubling technique [3]. Here the elements are stored in an array. Whenever the array becomes full, an array of double its size allocated and all the elements are copied to it. Similarly, whenever the array shrinks so that it is only one-fourth full, an array of half its size is allocated and all the elements are copied to it. The advantage of this solution over the linked lists is that random access to the elements takes only O(1) time (as opposed to O(n) for linked lists). The amortized update time is O(1), though the worst-case update time is O(n). The space overhead of this solution is O(n).

Sitarski [56] has proposed a solution whose space overhead is only O(√n). The idea is to divide the given list of n elements into sublists of size l nl, store them in separate arrays, and store an array (of length O(√n)) of pointers to these sublists (in order). Whenever l nl changes, the entire structure is reconstructed with the new size. Thus the amortized update time is O(1) (though the worst-case time is O(n)). This also supports random access in O(1) time.

Brodnik et al. [4] gave a structure that takes O(√n) extra locations, where n is the current size of the array, and supports the operations in O(1) time. One advantage of this structure is that elements are never re-allocated. They have also shown that any such structure requires Ω(√n) extra locations even if there are no constraints on the access time.

Dynamic Arrays

A resizable array supports adding/deleting elements only at the end of the list, but does not support insertion/deletion of elements at arbitrary positions in the array. A dynamic array is data structure that maintains a sequence of records under the following operations:

• access(i): return the i-th record in the sequence,

• insert(r, i): insert the record r at position i in the sequence, and

• delete(i): delete the i-th record in the sequence.

A standard way of implementing a dynamic array is to store the records in an array and maintain it using the doubling technique. This supports access in O(1) but requires O(n) time to support insert and delete operations.

Goodrich and Kloss [24] gave a structure, the tiered vector , that takes n + O(√n) words of space to represent a sequence of length n, where each record fits in a word. This structure supports access in O(1) time and updates in O(√n) amortized time. The major component of a tiered vector is a set of indexable circular deques. A deque is a linear list which provides constant time insert and delete operations at either the head or the tail of the list [35]. A circular deque is a list which is stored in a sequential section of memory of fixed size. An indexable circular deque maintains pointers h and t, which reference the index in memory of the head and tail of this list. A tiered vector is a set of indexable circular deques. Insertions and deletions in an arbitrary indexable circular deque require time linear in its size, but inserting/deleting at either the head or the tail of the list takes O(1) time.

Thus, by maintaining the given sequence of n elements using O(√n) indexable circular deques each of size O(√n), one can support access in O(1) time and updates in O(√n) amortized time. One can easily generalize this structure to one that supports access in O(1/E) time and updates in O(nE) time, for any parameter 0 < E ≤ 1.

Using this structure to represent a block of O(lgO(1) n) records, Raman et al. [49] gave a structure that supports access and updates in O(lg n/ lg lg n) amortized time, using o(n) bits of extra space. The main idea is to divide the given list of length n into sublists of length between 1 lg4 n and 2 lg4 n, and store the sublists using the above dynamic array structure. One can maintain these sublists as the leaves of a weight-balanced B-tree with branching factor O(√lg n), and hence height O(lg n/ lg lg n).

By restricting the length of the array, Raman and Rao [51] obtained a dynamic array structure that maintains a sequence of l = O(wO(1) ) records of r = O(w) bits each, where w is the word size. This structure supports access in O(1) time and updates in O(1 + lr/kw) amortized time, and uses lr + O(k lg l) bits, for any parameter k ≤ l. The data structure also requires a precomputed table of size O(2Ew ) bits, for any fixed E > 0. The main idea is to store the newly added elements separately from the existing elements, and store a structure to indicate all the positions of the ‘updated’ elements. The structure is rebuilt after every k updates.