Succinct List Indexing in Optimal Time

An indexed list supports (efficient) access to both the offsets and the items of an arbitrarily ordered set under the effect of insertions and deletions. Existing solutions are engaged in a space-time trade-off. On the one hand, time efficient solutions are composed as a package of data structures: a linked-list, a hash table and a tree-type structure to support indexing. This arrangement observes a memory commitment that is outside the information theoretic lower bound (for ordered sets) by a factor of 12. On the other hand, the memory lower bound can be satisfied, up to an additive lower order term, trivially with an array. However, operations incur time costs proportional to the length of the array. We revisit the list indexing problem by attempting to balance the competing demands of space and time efficiency. We prepare the first succinct indexed list that supports efficient query and update operations. To implement an ordered set of size n, drawn from the universe {1, …, m}, the solution occupies n(log m + o(log n)) bits (with high probability) and admits all operations optimally in 𝒪(log n/log log n) time.