1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
        return size() > capacity ;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class LRUCache {
    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;
    public LRUCache(int capacity) {
        cache = new LinkedHashMap();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        int val = cache.get(key);
        Recent(key);
        return val;
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            cache.put(key, value);
            Recent(key);
            return;
        }

        if(capacity == cache.size()){
            int old = cache.keySet().iterator().next();
            cache.remove(old);
        }
        cache.put(key, value);
    }

    public void Recent(int key){
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key, val);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

class LRUCache {
    class Node{
        private int key, value;
        private Node pre, next;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    class DoubleList{
        private Node head, tail;
        private int size;

        public DoubleList(){
            head = new Node(-1,-1);
            tail = new Node(-1,-1);
            head.next = tail;
            tail.pre = head;
        }

        public void addFirst(Node n){
            n.next = head.next;
            n.pre = head;
            head.next = n;
            n.next.pre = n;
            size++;
        }

        public void remove(Node n){
            n.pre.next = n.next;
            n.next.pre = n.pre;
            size--;
        }

        public Node removeLast(){
            Node last = tail.pre;
            remove(last);
            return last;
        }
        public int size(){
            return size;
        }
    }
    private Map<Integer, Node> map;
    private DoubleList cache;
    private int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer ,Node>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        int val = map.get(key).value;
        put(key, val);
        return val;
    }
    
    public void put(int key, int value) {
        Node n = new Node(key, value);
        if(map.containsKey(key)){
            cache.remove(map.get(key));
            cache.addFirst(n);
            map.put(key, n);
        }else{
            if(cache.size() == capacity){
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(n);
            map.put(key, n);
        }
    }
}