What is a data structure that has O(1) for append, prepend, and retrieve element at any location?

I’m looking for Java solution but any general answer is also OK.

Vector/ArrayList is O(1) for append and retrieve, but O(n) for prepend.

LinkedList (in Java implemented as doubly-linked-list) is O(1) for append and prepend, but O(n) for retrieval.

Deque (ArrayDeque) is O(1) for everything above but cannot retrieve element at arbitrary index.

In my mind a data structure that satisfy the requirement above has 2 growable list inside (one for prepend and one for append) and also stores an offset to determine where to get the element during retrieval.

Answer

You’re looking for a double-ended queue. This is implemented the way you want in the C++ STL, which is you can index into it, but not in Java, as you noted. You could conceivably roll your own from standard components by using two arrays and storing where “zero” is. This could be wasteful of memory if you end up moving a long way from zero, but if you get too far you can rebase and allow the deque to crawl into a new array.

A more elegant solution that doesn’t really require so much fanciness in managing two arrays is to impose a circular array onto a pre-allocated array. This would require implementing push_front, push_back, and the resizing of the array behind it, but the conditions for resizing and such would be much cleaner.

Leave a Reply

Your email address will not be published. Required fields are marked *