Recently I have attended an interview as backend developer, and I've been asked one the following question:

Design a data structure that can perform insert, update, remove, and contains operation in O(1) time complexity.

It should allay printing all the elements in O(n) time maintaining the insertion order of elements.

Can someone please explain which data structure we can use and how that data structure allows to achieve the required O(1) time complexity?

CodePudding user response：

It seems like your interviewer was talking about a composite data structure which combines a Linked list and a Hash table.

And JDK offers and implementation of such data structure in the form of LinkedHashMap, which is basically a combination of a HashMap and a LinkedList. It's methods almost as fast as HashMap's ones.

LinkedHashMap capable to perform these operations in amortized O(1) time (only if the Key has a proper hash-function, the worst case would be O(n)):

• insertion via put(key, value);
• containsKey(key) check;
• updating the value of via replace(key, value) and replace(key, oldValue, newValue);
• retrieve the values with get(key);

And owing to a LinkedList maintained under the hood is, LinkedHashMap can can track the insertion order of entries (updating the value of an existing entry has no impact on the order).

Here's a quote from the documentation:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).