Skip to content

Instantly share code, notes, and snippets.

@ishwarrimal
Created November 12, 2021 14:33
Show Gist options
  • Save ishwarrimal/aad19c667db27c34aefdece3841ef9a6 to your computer and use it in GitHub Desktop.
Save ishwarrimal/aad19c667db27c34aefdece3841ef9a6 to your computer and use it in GitHub Desktop.
implementation of LRU cache using Map and doubly linked list in JS
//A basic doubly linked list structure
class Node {
constructor(val,prev = null, next = null){
this.val = val;
this.prev = prev;
this.next = next;
}
}
class LRUCache {
constructor(limit = 100) {
this.limit = limit;
this.size = 0;
this.head = null;
this.tail = null;
this.LRUMap = new Map();
}
/**
* readData: Fetch the data from the cache, but make sure to move the data if it's not on the of the cache.
*
* @param {number|string} key to identify each data.
* @return {Any} returns cached data.
*/
readData(key){
const cachedData = this.LRUMap.get(key);
if(cachedData){
// if data is present anywhere other than head, moveData to the head
if(this.head !== key){
this.#moveData(key,cachedData);
}
return cachedData?.val;
}
}
/** End of readData */
/**
* insertData: Inserts new data on the cache, if it's not already existing
*
* @param {number|string} key to identify each data.
* @param {Any} Data that needs to be cached.
* @return undefined.
*/
insertData(key, data){
console.log(this.LRUMap.get(key));
if(!this.LRUMap.get(key)){
if(this.size === this.limit){
this.#resetNode(this.tail)
this.LRUMap.delete(this.tail)
this.size--;
}
const oldHead = this.head;
const cacheData = new Node(data, null, oldHead);
if(!oldHead){
this.head = this.tail = key;
}else{
const nextNode = this.LRUMap.get(oldHead);
nextNode.prev = key;
this.head = key;
}
this.LRUMap.set(key, cacheData);
this.size++;
}else{
//Do we move the data if it exists?
}
}
/**End of insertData */
/**
Private method
* moveData: Moves the data to the top of the cache.
*
* @param {number|string} key to identify each data.
* @param {Node} The node containing data, prev and next.
* @returns undefined
*/
#moveData(key,cachedData){
this.#resetNode(key);
this.LRUMap.set(key, cachedData);
this.head = key;
}
/** End of moveData */
/**
* Private Method
* resetNode: Reset the next and previous value of Node to adjust to the deleted node..
*
* @param {number|string} key to identify each Node.
* @returns undefined.
*/
#resetNode(key) {
const node = this.LRUMap.get(key);
if(node.prev !== null){
const prevNode = this.LRUMap.get(node.prev);
prevNode.next = node.next;
}else{
this.head = key;
}
if(node.next !== null){
const nextNode = this.LRUMap.get(node.next);
nextNode.prev = node.prev;
}else{
this.tail = key;
}
}
/** End of resetNode */
}
// const lru = new LRUCache();
// lru.insertData('a','Apple');
// console.log(lru.head, lru.LRUMap);
// lru.insertData('b','Banana');
// lru.insertData('z','Zebra');
// console.log(lru.head, lru.LRUMap);
// console.log(lru.readData('b'));
// console.log(lru.head);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment