Java simple HashMap and double linked list solution


  • 0
    A
    public class LRUCache {
    
    private static class Entry {
        public Entry(int k, int v) {
            key = k;
            val = v;
        }
        final int key;
        int val;
        Entry next;
        Entry prev;
        public void remove() {
            next.prev = prev;
            prev.next = next;
        }
        public void add(Entry after) {
            next = after.next;
            prev = after;
            next.prev = this;
            after.next = this;
        }
    }
    
    private int capacity;
    private Entry head = new Entry(0, 0);
    private Entry tail = new Entry(0, 0);
    private HashMap<Integer, Entry> map = new HashMap<>();
    
    public LRUCache(int c) {
        tail.prev = head;
        head.next = tail;
        capacity = c;
    }
    
    public int get(int key) {
        Entry e = map.get(key);
        if (e != null) {
            e.remove();
            e.add(head);
            return e.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        Entry e = map.get(key);
        if (e != null) {
            e.val = value;
            e.remove();
            e.add(head);    
        } else {
            e = new Entry(key, value);
            e.add(head);
            map.put(key, e);
            if (map.size() > capacity) {
              Entry r = tail.prev;
              map.remove(r.key);
              tail.prev = r.prev;
              tail.prev.next = tail;
            }
        }
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.