CODEWITHSUNDEEP
data-structures
CodeMonkey
CodeMonkey

Reputation: 129

Data Structure that supports constant time for addbegin, addend and random access

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

I am thinking double ended queue. Does double ended queue support constant time performance for random access? If so, how does it achieve it?

I know one can use double linked list to build a double ended queue. But How do you build an index on all the elements to achieve constant time random access?

Thank you for your help.

Jerry

Upvotes: 4

Views: 612

Answers (1)

Fred Foo
Fred Foo

Reputation: 363577

What you're looking for would be a double-ended queue by definition, but that's just an abstract data structure. Wikipedia discusses several implementation strategies for deques in terms of dynamic arrays; using these, you can get amortized O(1) prepend and append. The circular buffer strategy seems the easiest to implement, at first glance.

Upvotes: 1

Related Questions