LRU Data Structure Implementation – Python

By March 11, 2016Technology

The other day I was talking to my friend and he asked me this. How would you implement a Least Recently Used Data-structure with a good time complexity. Below is how I came up with my solution to achieve this.

I am using a Dictionary in Python (Hashmap in case of Java) to store the Key and Node information and a Double Linked List to the store the actual data. The time complexity of a ‘get’ function is O(1) for getting the node using the Dictionary. In the double linked list, there is no need of traversing the list, We can directly remove the node and set it as head with a time complexity of O(1). Let me know what you guys think of this.

Leave a Reply