LRU, Least Recent Used Cache
LRU is the Cache data structure for fast deletion, insertion and update
LRU can be implemented with LinkedList and HashMap
1. delete() $\mathcal{O}(1)$
2. insert() $\mathcal{O}(1)$
3. contains() $\mathcal{O}(1)$
Implementation insertion:
1. If the HashMap does't contain the Key and the size of LinkedList is less than the Maximum Value.
2. Insert the [Key, Node] to HashMap, Append the Node to LinkedList, increase the count by 1
3. If the HashMap does't contains the Key and the size of LinkedList equals to the Maximum Value,
4. then Delete the oldest Node from LinkedList, and insert [Key, Node] to HashMap and Append the Node to LinkedList
5. If the HashMap contains the Key, then Delete the Node and Append the Node to LinkedList
Note: the Node need to contains the key so that Node can be deleted from the HashMap

class LNode {
    String key;
    Object data;
    public LNode(String key, Object data) {
        this.data = data;
        this.key = key;
    }
}

class LRU {
    final int max;
    int count;
    LinkedList<LNode> list = new LinkedList<LNode>();
    Map<String, LNode> map = new HashMap<String, LNode>();

    public LRU(int max) {
        this.max = max;
        this.count = 0;
    }
    public void insert(String key, LNode node) {
        LNode value = map.get(key);
        if(value != null) {
            list.remove(value);
            list.addLast(node);
            map.put(key, node);
        } else {
            if(count < max) {
                map.put(key, node);
                list.addLast(node);
                count++;
            }else{
                LNode reNode = list.removeFirst();
                list.addLast(node);
                map.remove(reNode.key);
                map.put(key, node);
            }
        }
    }
    public void remove(String key) {
        if(count > 0 && map.containsKey(key)){
            LNode node = map.get(key);
            if(node != null){
                list.remove(node);
                map.remove(key);
                count--;
            }
        }
    }

    public void print(){
        for(Map.Entry<String, LNode> entry : map.entrySet()){
            System.out.println("[" + entry.getKey() + " , " + entry.getValue().data + "]");
        } 
        Aron.line();

        for(LNode node : list){
            System.out.println("["+ node.data + "]");
        }
    }
}
Source Code