Implementing LRU cache in JavaScript
LRU is the acronym of Least Recently Used cache. The cache is used everywhere, let’s try to implement that in Javascript.
In Simple steps —
- Create a data structure to hold the cache data with an 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 LinkedList
and aMap(Object)
Read and write operations have to be O(1) in time complexity.
DoublyLinkedList for write/remove and Map(object) for read makes this possible.
Identifying least recently used item from the cache:
In a Doubly Linked list make head as most recently used and tail as least recently used.
- Do every insertion at the head.
- On every read or update operation detach the node from its position and attach it at the head of the LinkedList. Remember, LRU is indicated in terms of both read and write operations to the cache.
- When cache limit exceeds remove a node from the tail
- Store
key: Node
relation in an object, so that retrieval is possible in O(1).
Usage
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 the LRU cache with a time limit. When no read and write operations are performed on LRU for a certain time invalidate the cache, Even better invalidate only a specific node when there is no operation on that node for a certain time.
Note: This article is cross-posted on Dev.to
Note: If you liked the article, make sure to 👏 below. For more updates on JavaScript, Angular and React connect on LinkedIn and GitHub. Happy coding!