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.

A programmer trying to find the best solution for LRU Cache

In Simple steps —

1. Create a data structure to hold the cache data with an initial limit.
2. 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.
3. We implement the functionality by mimicking Doubly LinkedList and a Map(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:

LRU Cache visualized as map and LinkedList

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 it 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
4. 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!

Top 5 things to consider when creating an Angular library