Hello there

My name’s Norm Ovenseri and I studied Statistics with a good mix of Computer Science because it is my belief that technology and statistics envelopes the world whether you like it or not. :}

Most Recent Post

Efficient LRU Cache in Java

 

Fun fun stuff to do in lintcode. I mean we can always incur a linear traversal using a LinkedList if one wanted a simple way to do LRU, but why not challenge myself.


 


public class LRUCache {
    
    public class LRUNode {
        
        Integer key;
        Integer data;
        LRUNode prev;
        LRUNode next;
        
        public LRUNode(int key, int data) {
            
            this.key = key;
            this.data = data;
        }
    }
    
    LRUNode head;
    LRUNode tail;
    Map nodeMap = new HashMap();
    int maxCap;
    
    
    /*
    * @param capacity: An integer
    */public LRUCache(int capacity) {
        // do intialization if necessary
        
        this.maxCap = capacity;
    }

    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        // write your code here
    
        LRUNode node = nodeMap.get(key);
        
        if(node != null) {
            
            this.remove(node);
            this.push(node);
            
            return node.data;
        }
        
        return -1;
    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // write your code here
        
        if(nodeMap.containsKey(key)) {
            
            LRUNode oldNode = this.nodeMap.get(key);
            this.remove(oldNode);
        }
        
        LRUNode node = new LRUNode(key, value);
        
        this.push(node);
        
        if(nodeMap.size() > this.maxCap) {
            
            this.removeOld();
        }
    }
    
    private void push(LRUNode newHead) {
        
        if(this.head != null) {
            
            newHead.prev = null;
            newHead.next = this.head;
            this.head.prev = newHead;
        }
        
        if(this.tail == null) {
            
            this.tail = newHead;
        }
        
        this.head = newHead;
        this.nodeMap.put(newHead.key, newHead);
    }
    
    private void removeOld() {
        
        if(this.tail == null) {
            
            return;
        }
        
        this.remove(this.tail);
        
    }
    
    private void remove(LRUNode node) {
        
        if(node.prev != null) {
            
            node.prev.next = node.next;
        }
        
        if(node.next != null) {
            
            node.next.prev = node.prev;
        }
        
        if(node.equals(this.head)) {
            
            this.head = node.next;
        }
        
        if(node.equals(this.tail)) {
            
            this.tail = node.prev;
        }
        
        node.next = null;
        node.prev = null;
        this.nodeMap.remove(node.key);
    }
}

You just read Efficient LRU Cache in Java. Please share if you've liked it.
You may find related posts by clicking on the tags and/or categories above.