146. LRU Cache

1class LRUCache {
2    capacity: number;
3    map: Map<number, number>;
4    constructor(capacity: number) {
5        this.capacity = capacity;
6        this.map = new Map();
7    }
8
9    get(key: number): number {
10        if (!this.map.has(key)) return -1;
11        const value = this.map.get(key);
12        this.map.delete(key);
13        this.map.set(key, value)
14        return value;
15    }
16
17    put(key: number, value: number): void {
18        if (this.map.has(key)) {
19            this.map.delete(key)
20        }
21
22        this.map.set(key, value);
23        if (this.map.size > this.capacity) {
24            const lru_key = this.map.keys().next().value;
25            this.map.delete(lru_key)
26        }
27    }
28}
29
30/**
31 * Your LRUCache object will be instantiated and called as such:
32 * var obj = new LRUCache(capacity)
33 * var param_1 = obj.get(key)
34 * obj.put(key,value)
35 */

1class Node {
2	key: number;
3	value: number;
4	prev: Node | null = null;
5	next: Node | null = null;
6	constructor(key: number, value: number) {
7		this.key = key;
8		this.value value;	
9	}
10}
11
12class LRUCache {
13	 capacity: number;
14	 cache: Map<number, Node>;
15	 head: Node;
16	 tail: Node;
17	 
18  constructor(capacity: number) {
19      this.capacity = capacity;
20      this.cache = new Map();
21      
22      this.head = new Node(0, 0)
23      this.tail = new Node(0, 0);
24      this.head.next = this.tail;
25      this.tail.prev = this.head;
26  }
27
28  get(key: number): number {
29      const node = this.cache.get(key);
30      if(!node) return -1;
31      this.moveToHead(node);
32      return node.value;
33  }
34
35  put(key: number, value: number): void {
36	    let node = this.cache.get(key);
37	    if(node) {
38		    node.value = value;
39		    this.moveToHead(node);
40	    } else {
41		    node = new Node(key, value)
42		    this.cache.set(key, node)
43		    this.addToHead(node)
44		    if(this.cache.size > this.capacity) {
45			    const tail = this.removeTail();
46			    if(tail) this.cache.delete(tail.key);
47		    }
48	    }
49  }
50  
51  addToHead(node: Node): void {
52	  node.prev = this.head;
53	  node.next = this.head.next;
54	  if(this.head.next) this.head.next.prev = node;
55	  this.head.next = node;
56  }
57  
58  removeNode(node: Node): void {
59	  if(node.prev) node.prev.next = node.next;
60	  if(node.next) node.next.prev = node.prev;
61  }
62  
63  moveToHead(node: Node): void {
64	  this.removeNode(node);
65	  this.addToHead(node);
66  }
67  
68  removeTail(): Node | null {
69	  if(!this.tail.prev || this.tail.preve === this.head) return null;
70	  const node = this.tail.prev;
71	  this.removeNode(node);
72	  return node;
73  }
74}
75
76/**
77 * Your LRUCache object will be instantiated and called as such:
78 * var obj = new LRUCache(capacity)
79 * var param_1 = obj.get(key)
80 * obj.put(key,value)
81	 */