Let the position of a list element in a list be the number of
elements preceding it plus one.
An indexed list supports the following operations on a list:
Insert; delete; return the position of
an element; and return the element at a certain position.
The order in which the
elements appear in the list is completely determined by where the
insertions take place; we do not require the presence of
any keys that induce the ordering.
We consider approximate indexed lists, and show that
a tiny relaxation in precision of the query operations allows
a considerable improvement in time complexity.
The new data structure has applications in two other
problems; namely, list labeling and subset rank.