LRU (Java)

LRU (Least Recently Used) cache allows you to store memory bounded data with auto-eviction policy for least recently used entries once the maximum capacity is reached.

Requirement

Fixed Size
Fast Read
Fast Add
Fast Updates

Internal Data Structure

HashMap is used for O(1) operations on get(key) and put(key, value).
Doubly Linked List is used because it supports fast insertion and deletion of nodes.

Constructor

public LRU(int capacity)

Public Methods

public LRU(int capacity)
public void put(K key, V value)
public V get(K key)
public V remove(K key)
public List<V> getValues()
public Iterator<V> valueIterator()

Private Methods

private void addFront(Entry<K, V> entry)
private void moveFront(Entry<K, V> entry)
private void delete(Entry<K, V> entry)
private void ensureCapacity()

Strength

Fast Access
Fast Updates

Weakness

Space Heavy