# 0146. LRU Cache
###### tags: `Leetcode` `Medium` `Linked List` `HashMap`
Link: https://leetcode.com/problems/lru-cache/
## 思路
非常繁琐的一道题
HashMap+双向链表
- 为什么要用双向链表？
因为找到一个node之后，有可能需要删除他，删除他的这个工作如果想在O(1)完成就需要双向链表
- 每个函数的作用
* addToHead 加到head后面
* RemoveNode 删掉这个node，但**不能把key从map里面删掉**，因为moveToHead会调用它
* moveToHead 先删掉这个node，再把它加到head后面
* removeTail 这时候才是确定要从list里面真正拿走这个node，从map里面remove key 然后removeNode(tail)
## Code

class LRUCache {
    class DLinkedNode{
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    Map<Integer,DLinkedNode> keyValue = new HashMap<Integer, DLinkedNode>();
    private int capacity;
    private int size;
    private DLinkedNode head, tail;
    public LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLinkedNode node = keyValue.get(key);
        if(node == null) return -1;
        else{
            //move the node to head
            moveToHead(node);
            return node.value;
        }
    }
    
    public void put(int key, int value) {
        DLinkedNode node = keyValue.get(key);
        if(node != null){
            //update value and move to head
            node.value = value;
            moveToHead(node);
        }
        else{
            //create a new node, add to the hashmap, check capacity and add to linkedlist
            DLinkedNode newNode = new DLinkedNode(key, value);
            keyValue.put(key, newNode);
            if(this.size<this.capacity){
                addToHead(newNode);
                size++;
            }
            else{
                DLinkedNode removedNode = removeTail();
                keyValue.remove(removedNode.key);
                addToHead(newNode);
            }
            
        }
    }
    
    private void addToHead(DLinkedNode node){
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
    private void removeNode(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    } 
    private DLinkedNode removeTail(){
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
}