Skip to content

Instantly share code, notes, and snippets.

@jinnyMcKindy
Last active June 28, 2020 21:16
Show Gist options
  • Save jinnyMcKindy/e2bb1cce3018c930651447a77be262d5 to your computer and use it in GitHub Desktop.
Save jinnyMcKindy/e2bb1cce3018c930651447a77be262d5 to your computer and use it in GitHub Desktop.
Implement An LRU Cache algorithm JavaScript
const head = Symbol('head')
const tail = Symbol('tail')
class DoublyLinkedListNode {
constructor(value, index=0) {
this.value = value;
this.previous = null;
this.next = null;
this.index = index;
}
}
class DoublyLinkedListHashTable{
constructor() {
this.nodes = new Map();
}
add(key, val) {
if(!this[head]) {
this[head] = new DoublyLinkedListNode(val, key);
this[tail] = this[head];
this.nodes.set(key, this[head]);
}
else {
if(this.nodes.has(key)) {
this.update(key, val);
} else {
const node = this[head];
this[head] = new DoublyLinkedListNode(val, key);
this[head].next = node;
node.previous = this[head];
this.nodes.set(key, this[head]);
}
}
}
update(key, val) {
const node = this.nodes.get(key);
node.value = val;
this.moveNodeToHead(node);
}
get(key){
const node = this.nodes.get(key);
if(node) {
this.moveNodeToHead(node)
}
return node;
}
moveNodeToHead(node) {
const prev = node.previos;
const next = node.next;
if(prev) prev.next = next;
if(next) next.previous = prev;
const h = this[head];
this[head] = node;
this[head].next = h.next;
}
removeTail() {
const key = this[tail].index;
const node = this.nodes.get(key);
node.previous.next = null;
this[tail] = node.previous;
this.nodes.delete(key)
}
getLength() {
return this.nodes.size;
}
}
function LRUCache() {
const hashTable = new DoublyLinkedListHashTable()
const capacity = 5;
return {
get: function(key) {
return hashTable.get(key)?.value;
},
set: function(key, value) {
hashTable.add(key, value);
if(hashTable.getLength() > capacity){
hashTable.removeTail()
}
},
print: function() {
console.log(hashTable)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment