Below is the code implementation for a LRU cache with constant time complexity. We use a doubly linked list to maintain the access order of the cache entries. Caches are served from in memoryLinkedHasMap. The doubly linked list maintains least recently access nodes from left side and most recently used in right side.
lruEntry -> A ->B ->C ->D ->mruEntry.
package com.test.lrucache;
public class CacheEntry<K, V> {
private CacheEntry<K, V> next;
private CacheEntry<K, V> previous;
private K key;
private V value;
public CacheEntry(CacheEntry<K, V> previous, CacheEntry<K, V> next, K key, V value) {
super();
this.next = next;
this.previous = previous;
this.key = key;
this.value = value;
}
public CacheEntry<K, V> getNext() {
return next;
}
public void setNext(CacheEntry<K, V> next) {
this.next = next;
}
public CacheEntry<K, V> getPrevious() {
return previous;
}
public void setPrevious(CacheEntry<K, V> previous) {
this.previous = previous;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
package com.test.lrucache;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> {
private int maxSize;
private Map<K, CacheEntry<K, V>> listPointerMap;
private CacheEntry<K, V> lruEntry;
private CacheEntry<K, V> mruEntry;
public LRUCache(int maxSize) {
this.maxSize = maxSize;
listPointerMap = new LinkedHashMap<>();
// least recently used entry is null
lruEntry = null;
// most recently used entry is also null
mruEntry = lruEntry;
}
public void putCacheEntry(K key, V value) {
if (isFull()) {
// remove from map the left most node
listPointerMap.remove(lruEntry.getKey());
// remove the leftmost node
lruEntry = lruEntry.getNext();
lruEntry.setPrevious(null);
}
CacheEntry<K, V> newEntry = new CacheEntry<K, V>(mruEntry, null, key, value);
if (mruEntry != null) {
mruEntry.setNext(newEntry);
}
if (lruEntry == null) {
lruEntry = mruEntry;
}
mruEntry = newEntry;
listPointerMap.put(key, newEntry);
}
public V getCacheEntry(K key) {
CacheEntry<K, V> entry = listPointerMap.get(key);
// no entry found
if (entry == null) {
return null;
}
// last or most recently used entry so do nothing
if (entry.getKey() == mruEntry.getKey()) {
return entry.getValue();
}
CacheEntry<K, V> nextEntry = entry.getNext();
CacheEntry<K, V> previousEntry = entry.getPrevious();
// first or least recently used entry
if (entry.getKey() == lruEntry.getKey()) {
nextEntry.setPrevious(null);
lruEntry = nextEntry;
}
// somewhere in between
else if (entry.getKey() != mruEntry.getKey()) {
previousEntry.setNext(nextEntry);
nextEntry.setPrevious(previousEntry);
;
}
// Finally move our item to the MRU
entry.setPrevious(mruEntry);
mruEntry.setNext(entry);
mruEntry = entry;
mruEntry.setNext(null);
return entry.getValue();
}
private boolean isFull() {
return listPointerMap.size() == maxSize ? true : false;
}
}
package com.test.lrucache;
public class MainClass {
public static void main(String[] args) {
LRUCache<String, String> cache = new LRUCache<>(3);
cache.putCacheEntry("1", "One");
cache.putCacheEntry("2", "Two");
cache.putCacheEntry("3", "Three");
System.out.println(cache.getCacheEntry("1"));
System.out.println(cache.getCacheEntry("2"));
cache.putCacheEntry("4", "Four");
System.out.println(cache.getCacheEntry("3"));
System.out.println(cache.getCacheEntry("4"));
}
}
