Least Recently Used Cache import java.util.HashMap; import java.util.Map; class Main { public static void main(String[] args) { CacheLRU cache = new CacheLRU(3); cache.put("key1", "value1"); // k1 cache.put("key2", "value2"); // k1 k2 cache.put("key3", "value3"); // k1 k2 k3 cache.put("key1", "value1New"); // k2 k3 k1 cache.get("key2"); // k3 k1 k2 cache.put("key4", "value4"); // k1 k2 k4 print("value1New".equals(cache.get("key1"))); print("value2".equals(cache.get("key2"))); print(null == cache.get("key3")); print("value4".equals(cache.get("key4"))); } private static void print(boolean success) { System.out.println(success ? "Ok" : "Failed!"); } } class CacheLRU { Map<String, CacheNode> cacheMap; DoubleLinkedList cacheList; int cacheMaxSize; public CacheLRU(int size) { cacheMaxSize = size; cacheMap = new HashMap<>(cacheMaxSize); cacheList = new DoubleLinkedList(); } public void put(String key, String value) { if (cacheMap.containsKey(key)) { // The key is already in the cache, // update the value and move the item to head of the list // to make it as most recently used item. CacheNode node = cacheMap.get(key); node.cacheValue = value; cacheList.moveToHead(node); return; } if (cacheMap.size() == cacheMaxSize) { // Cache is full. Remove the least recently used item, // which is in the tail of the list. CacheNode node = cacheList.removeTailNode(); cacheMap.remove(node.cacheKey); } // Add item to cache CacheNode node = cacheList.add(key, value); cacheMap.put(key, node); } public String get(String key) { CacheNode node = cacheMap.get(key); if (node == null) return null; // Move the accessed item to head of the list // to make it as the most recently used item. cacheList.moveToHead(node); return node.cacheValue; } } class CacheNode { String cacheKey, cacheValue; CacheNode backNode, frontNode; } class DoubleLinkedList { CacheNode head = null, tail = null; public CacheNode add(String key, String value) { CacheNode node = new CacheNode(); node.cacheKey = key; node.cacheValue = value; addToHead(node); return node; } public CacheNode removeTailNode() { CacheNode tailNode = tail; detach(tailNode); return tailNode; } public void detach(CacheNode node) { // Remove the node from the list. if (node.frontNode == null) head = node.backNode; else node.frontNode.backNode = node.backNode; if (node.backNode == null) tail = node.frontNode; else node.backNode.frontNode = node.frontNode; node.frontNode = node.backNode = null; } public void moveToHead(CacheNode node) { detach(node); addToHead(node); } public void addToHead(CacheNode node) { if (head != null) head.frontNode = node; node.backNode = head; head = node; if (tail == null) tail = head; } }