Created
November 12, 2021 14:33
-
-
Save ishwarrimal/aad19c667db27c34aefdece3841ef9a6 to your computer and use it in GitHub Desktop.
implementation of LRU cache using Map and doubly linked list in JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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