實現lru 緩存

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

    public class LRUCache {

        static class Node {

            int key;

            int value;


        @Override  
        public String toString() {  
            return "Node{" +  
                    "key=" + key +  
                    ", value=" + value +  
                    '}';  
        }  
    }  


    static private LinkedList<Node> cache;  
    static private int cap;  
    static private Node indexMap[];  

    public LRUCache(int capacity) {  
        cache = new LinkedList<Node>();  
        indexMap = new Node[100000];  
        cap = capacity;  
    }  

    static public boolean isFull() {  
        return cache.size() == cap;  
    }  

    static public Node find(int key) {  
        if (cache.isEmpty())  
            return null;  
        Node tar = null;  

        if ((tar = indexMap[key]) == null)  
            return null;  

        cache.remove(tar);  
        cache.addFirst(tar);  
        return tar;  

    }  

     public int get(int key) {  
        Node node = find(key);  
        if (node == null) {  
            return -1;  
        }  
        return node.value;  
    }  

     public void set(int key, int value) {  
        Node node = null;  
        if ((node = find(key)) != null) {  
            node.value = value;  
            return;  
        }  

        //not find the element  

        if (isFull()) {  
            indexMap[cache.getLast().key] = null;  
            cache.removeLast();  
        }  


        Node newNode = new Node();  
        newNode.key = key;  
        newNode.value = value;  
        cache.addFirst(newNode);  
        indexMap[key] = newNode;  

    }  
}  </pre>