- Create a data structure to hold the cache data with the initial limit.
- Provide functionalities for adding to cache, getting an element from the cache, removing the least used element from the cache and iterating through the cache.
- We implement the functionality by mimicking
Doubly LinkedListand a
Read and write operations has to be in O(1) time complexity.
DoublyLinkedList for write/remove and Map(object) for read operation makes this possible.
In a Doubly Linked list make head as most recently used and tail as least recently used.
1) Do every insertion at the head.
2) On every read or update operation detach the node from its position and attach at the head of the LinkedList. Remember, LRU is indicated in terms of both read and write operations to the cache.
3)When cache limit exceeds remove a node from the tail
key: node relation in the cache map. So that retrieval is possible in O(1).
As we are adding the 4th element in a cache with limit 3, which element do you think is removed ????????????
Yes, it is ‘b’.
Since ‘a’ is read recently and ‘c’ is the last added item. ‘b’ becomes the element that isn’t used recently by either read or write operations and hence available for deletion from the cache.
If you want to take it to the next level implement LRU cache with a time limit. When no read and write operations are performed on LRU for certain time invalidate the cache. Even better invalidate only specific node when there is no operation on that node for a certain time.
Note: This article was originally published on Medium