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 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 LinkedList and a Map(Object)

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.

Identifying LRU item from the cache:

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

4) Store key: Node relation in the cache map. So that retrieval is possible in O(1).

LRU Implementation

LRU 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 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.

I often write and share about technology! You can follow my updates on LinkedIn and Twitter. Happy coding!

Note: This article was originally published on Medium