A data structure that maintains constant time for addbegin, addend, and random access

Question

I am looking for a data structure that maintains constant time performance for adding an element to the beginning, end, and random access.

I think of a double line. Does the double-ended queue maintain consistent performance over time for random access? If so, how is this achieved?

I know that you can use a double linked list to create a double-ended queue. But how do you create an index for all elements to achieve consistent random access?

Thank you for your help.

Jerry

Answer 1

What you are looking for will be in turn double-ended, but this is only an abstract data structure. Wikipedia discusses several implementation strategies for deques in terms of dynamic arrays; using them, you can get depreciation O (1) and add. The circular buffer strategy seems to be the simplest at first glance.