202407260918
tags: #linked-list

class Node {
	constructor(key, value) {
		this.prev = null;
		this.next = null;
		this.key = key;
		this.value = value;
	}
}

var LRUCache = function(capacity) {
	this.head = new Node(0, 0);
	this.tail = new Node(0, 0);
	this.head.next = this.tail;
	this.tail.prev = this.head;
	this.map = new Map();
	this.capacity = capacity;
};

LRUCache.prototype.get = function(key) {
	if (this.map.has(key)) {
		const node = this.map.get(key);
		this.remove(node);
		this.insert(node);
		return node.value;
	} else {
		return -1;
	}
};

LRUCache.prototype.put = function(key, value) {
	if (this.map.has(key)) {
		this.remove(this.map.get(key));
	}
	if (this.map.size === this.capacity) {
		this.remove(this.tail.prev);
	}
	this.insert(new Node(key, value));
};

LRUCache.prototype.insert = function(node) {
	this.map.set(node.key, node);
	const headNext = this.head.next;
	this.head.next = node;
	node.prev = this.head;
	headNext.prev = node;
	node.next = headNext;
}

LRUCache.prototype.remove = function(node) {
	this.map.delete(node.key);
	node.prev.next = node.next;
	node.next.prev = node.prev;
}

Reference

https://leetcode.com/problems/lru-cache