First, the LRU(least recently used) means we need some data structure to record the order of the last used time of each node. An intuitive solution is a Queue. Because `First-In-First-Out`

is exactly the LRU concept. And a Queue can be implemented using linkedlist.

Second, after we `GET`

a node from cache, we need to move that node to the head of queue, meaning it is most recently used. To achieve it in `O(1)`

time, we need a hashmap to record a key-(node) info for each node. After we identify that node, we just cut it from the queue and attach it to the head.

Third, how about `SET`

? First we try to locate a node with the `KEY`

, if we found a node, we just change the value of that node and move the node to head(means it is most recently used). If we cannot find a node, we will create a new node with (key,val) and attach it to the head. If the size of cache exceeds the capacity, we need to `REMOVE`

the `LAST`

node(last recently used).

In sumary, we basically need 3 operations

- attachToHead: attach an isolated node to head
- moveToHead: move an existing node in the linkedlist to head
- removeLast: remove the last node in the linkedlist

As you can see, to access head and tail in O(1) time, doubly linkedlist is a good choice.

`Node`

prev<=>(key,value)<=>next

` Doubly LinkedList`

(head)<=>(node1)<=>(node2)<=>...<=>(nodex)<=>(tail)

most recently used >>>>>>>>>>>>>> least recently used

`HashMap`

[key1]=>(node1)

[key2]=>(node2)

...

```
/**
* @constructor
*/
var ListNode = function(key,val){
this.prev = null;
this.next = null;
this.val = val;
this.key = key;
}
var LRUCache = function(capacity) {
this.head = new ListNode(-1,-1);
this.tail = new ListNode(-1,-1);
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
this.capacity = capacity;
this.map = new Map();
};
/**
* @param {number} key
* @returns {number}
*/
LRUCache.prototype.get = function(key) {
let node = this.map.get(key);
if(node){
this.moveToHead(node);
return node.val;
}else{
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @returns {void}
*/
LRUCache.prototype.set = function(key, value) {
let node = this.map.get(key);
if(!node){
node = new ListNode(key,value);
this.attachToHead(node);
this.size++;
}else{
node.val = value;
this.moveToHead(node);
}
if(this.size > this.capacity){
this.removeLast();
this.size--;
}
this.map.set(key,node);
};
LRUCache.prototype.attachToHead = function(node){
node.next = this.head.next;
node.next.prev = node;
this.head.next = node;
node.prev = this.head;
}
LRUCache.prototype.moveToHead = function(node){
node.prev.next = node.next;
node.next.prev = node.prev;
this.attachToHead(node);
}
LRUCache.prototype.removeLast = function(){
let last = this.tail.prev;
last.prev.next = this.tail;
this.tail.prev = last.prev;
this.map.delete(last.key);
}
```