DEV Community

Cover image for Implementing LRU cache in JavaScript
Uday Vunnam
Uday Vunnam

Posted on • Edited on • Originally published at Medium

9 3

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 Cache visualized as map and LinkedList

LRU Implementation

class Node {
constructor(key, value, next = null, prev = null) {
this.key = key;
this.value = value;
this.next = next;
this.prev = prev;
}
}
class LRU {
//set default limit of 10 if limit is not passed.
constructor(limit = 10) {
this.size = 0;
this.limit = limit;
this.head = null;
this.tail = null;
this.cacheMap = {};
}
write(key, value) {
const existingNode = this.cacheMap[key];
if (existingNode) {
this.detach(existingNode);
this.size--;
} else if (this.size === this.limit) {
delete this.cacheMap[this.tail.key];
this.detach(this.tail);
this.size--;
}
// Write to head of LinkedList
if (!this.head) {
this.head = this.tail = new Node(key, value);
} else {
const node = new Node(key, value, this.head);
this.head.prev = node;
this.head = node;
}
// update cacheMap with LinkedList key and Node reference
this.cacheMap[key] = this.head;
this.size++;
}
read(key) {
const existingNode = this.cacheMap[key];
if (existingNode) {
const value = existingNode.value;
// Make the node as new Head of LinkedList if not already
if (this.head !== existingNode) {
// write will automatically remove the node from it's position and make it a new head i.e most used
this.write(key, value);
}
return value;
}
console.log(`Item not available in cache for key ${key}`);
}
detach(node) {
if (node.prev !== null) {
node.prev.next = node.next;
} else {
this.head = node.next;
}
if (node.next !== null) {
node.next.prev = node.prev;
} else {
this.tail = node.prev;
}
}
clear() {
this.head = null;
this.tail = null;
this.size = 0;
this.cacheMap = {};
}
// Invokes the callback function with every node of the chain and the index of the node.
forEach(fn) {
let node = this.head;
let counter = 0;
while (node) {
fn(node, counter);
node = node.next;
counter++;
}
}
// To iterate over LRU with a 'for...of' loop
*[Symbol.iterator]() {
let node = this.head;
while (node) {
yield node;
node = node.next;
}
}
}
view raw lru.js hosted with ❤ by GitHub

LRU Usage

const lruCache = new LRU(3);
lruCache.write('a', 123);
lruCache.write('b', 456);
lruCache.write('c', 789); // lru is 'a'
lruCache.read('a'); // lru is 'b'
// Now max limit 3 is reached. Let's add a new element
lruCache.write('d', 0); // lru 'b' is removed
console.log(lruCache);
view raw lru-usage.js hosted with ❤ by GitHub

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

Billboard image

Deploy and scale your apps on AWS and GCP with a world class developer experience

Coherence makes it easy to set up and maintain cloud infrastructure. Harness the extensibility, compliance and cost efficiency of the cloud.

Learn more

Top comments (1)

Collapse
 
mandaputtra profile image
Manda Putra

Why forEach and *[Symbol.iterator] aren't used here? Am I missing something, it doesn't look like it will be called