A few days back I came across a problem : Design a system with following APIs :
- put(n) : Puts the value n
- get() : Gets the first added value
Obviously, this was a queue because we want get() operation to return the element added first. Here the order of adding elements is important. So far, things look good. We create a Queue using a doubly linked list with head and tail pointer so that get() and put(n) are both O(1) operations.
How about adding one more operation to this system? We want to add an API – removeElement(n) – that removes an element n from the queue in best possible time. Hmm, we have a problem. What options do we have ?
- Do nothing. Removal of the element from the linkedlist based queue would be O(n) in the worst case.
- Use a self-balancing BST instead of a linkedlist to implement this. In this case, removeElement(n) will be O(log n) but managing the insertion order would be very difficult and hence get() and put(n) would be increasingly difficult.
A bit more consideration would make it very clear that what we are looking for is actual an LRU Cache(a slightly modified) and want to make sure that all operations are as optimal as possible.
There is a way by which we can introduce a bit of hashing with the linked list. Lets have a hashmap where key is the number ‘n’ and the value associated with the key be the address of the node in the linked list. Now our operations look like:
- put(n) : Normally add the node at the head of the doubly linked list and make the entry of ‘n’ as key in the hashmap and store the address of the newly added node as value. This operations is o(1).
- get() : Simply remove the node at the tail in the doubly linked list and remove the node reference from the Hashmap. Again a o(1) operation.
- removeElement(n) : Do a o(1) lookup from hashmap using the key ‘n’ – get the value which is the address of the node in the linked list. Now that you have the node to be removed, removing the node in the doubly linked list is very easy – infact its o(1).
Funny thing is that Java has an interesting collection called – LinkedHashMap that does exactly this.There is a very useful implementation which shows how LinkedHashMap’s logic can be coded using a HashMap and a doubly linked list. After wasting a lot of time I found this little article explaining how LinkedHashMap is implemented. Check the graphic below.
As per the original article – LinkedHashMap provides a convenient data structure that maintains the ordering of entries within the hash-table. This is accomplished by cross-cutting the hash-table with a doubly-linked list, so that entries can be removed or reordered in O(1) time. When operating in access-order an entry is retrieved, unlinked, and relinked at the tail of the list. The result is that the head element is the least recently used and the tail element is the most recently used. When bounded, this class becomes a convenient LRU cache.