LRU Cache

Source

• lintcode: LRU Cache

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.

Java

public class Solution {
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head=null;
    Node tail=null;
    int capacity=0;

    // @param capacity, an integer
    public Solution(int capacity) {
        this.capacity=capacity;
    }

    // @return an integer
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        Node preNode = node.pre;
        Node nextNode = node.next;

        //if node is not the last one
        if(nextNode!=null){
            //if node is the first node in the list
            if(preNode==null){
                head=nextNode;
                nextNode.pre=null;
            }
            else{
                preNode.next=nextNode;
                nextNode.pre = preNode;
            }


            //put node to the end of the list
            tail.next=node;
            node.pre=tail;
            node.next=null;
            tail=node;            
        }
        return node.value;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        if(map.containsKey(key)){
            //just put node to the end of the list
            get(key);
            map.get(key).value=value;
        }
        else{
            Node node = new Node(key, value);
            //if map is full, then remove head;
            if(map.size()==this.capacity){
                if(head!=null){
                    Node oldHead = head;
                    head=head.next;
                    if(head!=null){
                        head.pre=null;
                    }
                    //oldHead.next=null;
                    map.remove(oldHead.key);
                }
            }
            if(head==null){
                head=node;
                tail=node;
            }else{
                tail.next=node;
                node.pre=tail;
                tail=node;
            }
            map.put(key, node);
        }
    }

    class Node{
        int key;
        int value;
        Node pre=null;
        Node next=null;

        public Node(int key, int value){
            this.key=key;
            this.value=value;
        }
    }
}