Skip to content

Instantly share code, notes, and snippets.

@motss
Last active April 18, 2024 17:48
Show Gist options
  • Save motss/edacf551a3d1b4c01f43af6cfc690587 to your computer and use it in GitHub Desktop.
Save motss/edacf551a3d1b4c01f43af6cfc690587 to your computer and use it in GitHub Desktop.
MRU in JavaScript using Doubly linked list
class Node {
constructor(value) {
this.prev = null;
this.next = null;
this.value = value;
}
}
class MRU {
constructor(size) {
this.size = size;
this.head = null;
this.tail = null;
this.map = new Map();
}
add(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
if (this.head.next) {
this.head.next.prev = this.head;
}
if (this.tail == null) {
this.tail = node;
} else if (this.tail.prev == null) {
this.tail.prev = node;
}
this.map.set(value, node);
return this.head;
}
remove(node) {
if (node === this.head) {
this.head = node.next;
node.next.prev = null;
node.next = null;
} else if (node === this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
node.prev = null;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = node.next = null;
}
this.map.delete(node.value);
return node;
}
put(value) {
if (this.map.has(value)) {
if (this.size !== 1) {
this.remove(this.map.get(value));
return this.add(value);
}
} else {
if (this.map.size === this.size) {
this.remove(this.tail);
}
return this.add(value);
}
}
list() {
const a = [];
let n = this.head;
while (n) {
a.push(n.value);
n = n.next;
}
return a;
}
}
const c = new MRU(3);
console.clear();
c.put(1);
console.debug(c.list());
c.put(2);
console.debug(c.list());
c.put(3);
console.debug(c.list());
c.put(4);
console.debug(c.list());
c.put(5);
console.debug(c.list());
c.put(4);
console.debug(c.list());
c.put(3);
console.debug(c.list());
c.put(6);
console.debug(c.list());
// Space complexity: O(n)
// Time complexity: put-O(1),list-O(n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment