LRU cache: Data Structures in JavaScript

Cache algorithm which can help to optimize memory usage.

Photo by Christina @ wocintechchat.com on Unsplash

LRU (Least Recently Used) cache is a cache algorithm that computer programs or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer.

Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones.

How the LRU cache algorithm works?

Empty list of items

Let’s say we have an empty list of items (cache elements). The list can contain maximum 4 items.

So first we add our first item. It becomes the most recently used. It stands in front of list.

Add first item to our list

Then we add the second item and it now becomes the most recently used. And now it stands in front of list.

Add second item to our list

We add 2 more items too and the last added item becomes the most recently used.

Add two more items to our list

So now we have 4 items in our list. The most recently used item is the item in front of list and the least recently used item is in the end of list.

Now we want to change or read the item we want.

Changed or read item becomes the most recently used and now it stands in front of a list.

The list view after change of item with id: 1

But what if we want to add one more item to our full list?

The algorithm will choose the least recently used item and remove it from the list and in front of the list it will put the item we want to add.

So that’s the main reason why this cache algorithm called the least recently used.

How to implement LRU caching scheme? What data structures should be used?

We use two data structures to implement an LRU Cache.

1. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of items (frames) available (cache size). The most recently used pages will be near front end and least recently pages will be near the rear end.
2. A Hash with page number as key and address of the corresponding queue node as value.

I tried to implement LRU Cache algorithm with JavaScript and you can see the implementation by navigating to github page with the link below.

LRU Cache Implementation Link

Thanks for reading and i hope i helped you to learn new things today 😉