leetcode146

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private LRUNode head;
    private LRUNode tail;
    private Map<Integer,LRUNode> map;
    private int capacity;
    private int len = 0; 
    public LRUCache(int capacity) {
        map = new  HashMap<Integer,LRUNode>(capacity);
        this.capacity = capacity;
    }
    public int get(int key) {
       LRUNode node =  map.get(key);
       if (node!=null){
            removeNode(node);
            addNodeToHead(node);
            return node.value;
        }
        return -1;
    }
    public void put(int key, int value) {
        LRUNode node =  map.get(key);
        if (node==null){
            len++;
            if (len>capacity){
                map.remove(tail.key);
                removeTail();
                len--;
            }
            node = new LRUNode(key,value);
            addNodeToHead(node);
            map.put(key,node);
        }else{
            node.value =  value;
            removeNode(node);
            addNodeToHead(node);
        }
    }
    private void addNodeToHead(LRUNode node){
        node.next = head;
        node.pre = null;
        if (head!=null){
            head.pre = node;
        }
        head = node;
        if (tail==null){
            tail = node;
        }
    }
    
    private void removeTail(){
        if (tail!=null){
            LRUNode pre = tail.pre;
            if (pre!=null){
                pre.next = null;
                tail = pre;
            }else{
                //说明是head节点
                head = null;
            }
        }
    }
    
    private void removeNode(LRUNode node){
        LRUNode pre = node.pre;
        LRUNode next = node.next;
        if (pre!=null){
            pre.next = next;
        }else{
            head = next;
        }
        if (next!=null){
            next.pre = pre;
        }else{
            tail = pre;
        }
    }
    private class LRUNode{
        int key;
        int value;
        LRUNode next;
        LRUNode pre;
        public LRUNode(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
}