LRU Cache

Problem

LRU Cache

Intuition

1. We can use doubly linked list to maintain these numbers in cache. Because it’s very easy to add & delete elements in linked list in O(1) time complexity.
2. Also, it’s required to know where some one element is. So we can use hashmap to record all positions of numbers in cache(Or in linked list).
3. In linked list, we can create two empty objects to mock the head & tail so that it’s easy for us to deal with the insertion and delete ops.

Code

class LRUCache {
    class DataNode{
        int key, val;
        DataNode pre, next;
        public DataNode(int k, int v){
            key = k;
            val = v;
            pre = null;
            next = null;
        }
        public DataNode(){
            key = -1;
            val = -1;
            pre = null;
            next = null;
        }
    }
    
    DataNode head, tail;
    Map<Integer, DataNode> nodes;
    int cap;
    
    private void addNode(DataNode newNode){
        tail.pre.next = newNode;
        newNode.pre = tail.pre;
        newNode.next = tail;
        tail.pre = newNode;
        nodes.put(newNode.key, newNode);
    }
    
    private void delNode(DataNode oldNode){
        oldNode.pre.next = oldNode.next;
        oldNode.next.pre = oldNode.pre;
        nodes.remove(oldNode.key);
    }

    public LRUCache(int capacity) {
        cap = capacity;
        head = new DataNode();
        tail = new DataNode();
        head.next = tail;
        tail.pre = head;
        nodes = new HashMap<>();
    }
    
    public int get(int key) {
        if(nodes.containsKey(key)){
            DataNode oldNode = nodes.get(key);
            delNode(oldNode);
            DataNode newNode = new DataNode(oldNode.key, oldNode.val);
            addNode(newNode);
            return newNode.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        boolean exist = false;
        if(nodes.containsKey(key)){
            DataNode oldNode = nodes.get(key);
            delNode(oldNode);
            exist = true;
        }
        if(nodes.size() == cap){
             if(!exist) {
                delNode(head.next);
            }
        }
        DataNode newNode = new DataNode(key, value);
        addNode(newNode);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */