LRU cache design

Idea

The cache is nothing but a circular arrayList. This list contains Entry. Whenever new entries are coming, add at the end of the list. That means least recently used element at the first. Suppose if you are reusing any element then unlink from the list and add at the end.

In order to get any element, we need to traverse the list, which takes \$O(n)\$ time complexity. In order to avoid this, I'm maintaining HashMap>. Here, k is key and IndexNode will contain a pointer to the Entry in the list so we can get the \$O(1)\$ time complexity.

Working solution

```
package lrucache;

import java.util.HashMap;

public class LRUCache {

private transient Entry header = new Entry(null, null, null, null);
public HashMap>> indexMap = new HashMap>>();
private final int CACHE_LIMIT = 3;
private int size;

public LRUCache() {
header.next = header.previous = header;
this.size = 0;
}

public void put(K key,V value){
Entry newEntry = new Entry(key,value,null,null);
addBefore(newEntry, header);
}

private void addBefore(Entry newEntry,Entry entry){
if((size+1)> indexNode = new IndexNode>(newEntry);
indexMap.put(newEntry.key, indexNode);
newEntry.previous.next=newEntry;
newEntry.next.previous=newEntry;
size++;
}else{
Entry entryRemoved = remove(header.next);
indexMap.remove(entryRemoved.key);
addBefore(newEntry, entry);
}
}

public void get(K key){
if(indexMap.containsKey(key)){
Entry newEntry = remove(indexMap.get(key).pointer);
addBefore(newEntry,header);
}else{
System.out.println("No such element was cached. Go and get it from Disk");
}
}

private Entry remove(Entry entry){
entry.previous.next=entry.next;
entry.next.previous = entry.previous;
size--;
return entry;
}

public void

You can instead use a LinkedHashMap, which lets you get the in access order if you made it with the (int, float, boolean) constructor.

Then adding means removing map.entrySet().iterator().next().remove() if it becomes too large.

However LinkedHashMap is specially designed to let a subclass decide when to remove the oldest entry using the removeEldestEntry which gets called on each put:

public class MyLRUCache extends LinkedHashMap {

    private static final int MAX_CACHE = 4;

    public MyLRUCache(){
        super(MAX_CACHE, 1, true); 
        // sets the super class to use access order instead of insertion order.
    }

    @Override
    protected boolean removeEldestEntry(
            java.util.Map.Entry eldest) {
        return size() > MAX_CACHE;
    }
}

StackExchange Code Review Q#80167, answer score: 8