LRU Cache With constant time complexity

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"));

}

}