CODEWITHSUNDEEP
java
Kotsos
Kotsos

Reputation: 329

Data structure which offers both insertion/removal from/to both ends and retrieval from middle constant effort?

I was wondering whether is there a data structure that offers constant effort (O(1)) for both insertion/removal from/to both ends, as for example a LinkedList offers, and retrieval from a random index, as for example a HashMap offers.

Or maybe if I can achieve something similar somehow with a combination of data structures.

Upvotes: 3

Views: 379

Answers (2)

Nour
Nour

Reputation: 807

A hashmap is the fastest data structure i think

remove: O(1) size: O(1) values: O(n) (on traversal through iterator)

Upvotes: 1

Marko Topolnik
Marko Topolnik

Reputation: 200206

It seems like ArrayDeque fits all your requirements. Quoting its Javadoc:

Most ArrayDeque operations run in amortized constant time.

Upvotes: 3

Related Questions