CacheForRecentlyAccess.java

/*
CacheForRecentlyAccess

[A, B, C, D]
[B, C, D, A]
[C, D, A, F, G]
[C, A, F, G, D]
[A, F, G, D, N]  C evicted
[F, G, D, N, M]  A evicted

add(key, value);
search(key);
changeSize(newSize);

It's basically a LinkedHashMap.
*/

public class Cache{
    private Node first;
    private Node last;
    private int size;
    private int currentSize;
    private HashTable<Key, Node> table;
    
    Cach(int size){
        this.table = new HashTable<Key, Node>()
        this.size = size;
        this.currentSize = 0;
    }
    
    public void add(Key key, Value value){
        if(currentSize == size) deleteRarely();
        
        if(first == null && last == null){
            first = new Node(key, value);
            last = first;
            table.put(key, first);
            currentSize++;
            }
        else{
            Node newNode = Node(key, value);
            last.next = newNode;
            newNode.before = last;
            last = newNode;
            table.put(key, newNode);
            currentSize++;
        }
        
    }
    
    public Value search(Key key){
        if(table.containsKey(key)){
            thisNode = table[key];
            if(thisNode == last);
            else if(thisNode == first){
                deleteRarely();
                add(thisNode.key, thisNode.value);
            }
            else{
                thisNode.before.next = thisNode.next;
                thisNode.next.before = thisNode.before;
                currentSize--;
                add(thisNode.key, thisNode.value);
            }
            
            return table[key].value;
        }
        else return null;
    }
    
    private void deleteRarely(){
        table.remove(first.key);
        
        if(first.next == null){
            first = null;
            last = null;
            currentSize--;
        }
        else{
            Node thisNode = first.next;
            thisNode.before = null;
            first = thisNode;
            currentSize--;
        }
    
    public void changeSize(int newSize){
        if(newSize < size){
            for(int i = 1; i <= size - newSize; i++) deleteRarely();
            size = newSize;
        }
        else size = newSize;
    }
        
        
    }
}

class Node{
    Node next;
    Node before;
    Key key;
    Value value
    
    Node(Key key, Value value){
        this.key = key;
        this.value = value;
    }
}