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

http://blog.csdn.net/linhuanmars/article/details/21310633

public class LRUCache {
    
    public LRUCache(int capacity) {
        map = new HashMap<>();
        head = null;
        tail = null;
        this.size = 0;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Node hit = map.get(key);
        if (hit == null)
            return -1;
        
        // Remove hit from list.
        removeNodeFromList(hit);
        
        // Add hit to the head
        addNodeToHead(hit);
        
        return hit.value;
    }
    
    // Remove some node from the list
    private void removeNodeFromList(Node n)
    {
        if (n == null)
            return;
        
        Node pre = n.pre;
        Node next = n.next;
        
        if (pre == null) // node is head
            head = next;
        else
            pre.next = next;
        
        if (next == null) // node is tail
            tail = pre;
        else
            next.pre = pre;
            
        n.pre = null;
        n.next = null;
        
        size --;
    }
    
    // Add some node to head.
    // The node doesn‘t belongs to the list.
    private void addNodeToHead(Node n)
    {
        if (n == null)
            return;
        
        if (head == null) // Empty list
        {
            head = n;
            tail = n;
        }
        else
        {
            n.next = head;
            head.pre = n;
            head = n;
        }
        
        size ++;
    }
    
    public void set(int key, int value) {
        Node hit = map.get(key);
        if (hit != null)
        {
            hit.value = value;
            map.put(key, hit);
            
            removeNodeFromList(hit);
            addNodeToHead(hit);
        }
        else
        {
            hit = new Node(key, value);
            map.put(key, hit);
            
            if (size == capacity)
            {
                map.remove(tail.key);
                removeNodeFromList(tail);
            }
            addNodeToHead(hit);
        }
    }
    
    public void remove(int key)
    {
        Node hit = map.get(key);
        if (hit == null)
            return;
            
        // Remove from map
        map.remove(hit.key);
        
        // Remove from list
        removeNodeFromList(hit);
    }
    
    private Node head;
    private Node tail;
    private Map<Integer, Node> map;
    private int size;
    private int capacity;

    
    // A doubly linked list node.
    private static class Node
    {
        int key;
        int value;
        Node next;
        Node pre;
        public Node(int key, int value)
        {
            this.key = key;
            this.value = value;
            this.next = null;
            this.pre = null;
        }
    }
}

[LeetCode]146 LRU Cache