classCacheLRU{Map<String,CacheNode>cacheMap;DoubleLinkedListcacheList;intcacheMaxSize;publicCacheLRU(intsize){cacheMaxSize=size;cacheMap=newHashMap<>(cacheMaxSize);cacheList=newDoubleLinkedList();}publicvoidput(Stringkey,Stringvalue){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.CacheNodenode=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.CacheNodenode=cacheList.removeTailNode();cacheMap.remove(node.cacheKey);}// Add item to cacheCacheNodenode=cacheList.add(key,value);cacheMap.put(key,node);}publicStringget(Stringkey){CacheNodenode=cacheMap.get(key);if(node==null)returnnull;// Move the accessed item to head of the list// to make it as the most recently used item.cacheList.moveToHead(node);returnnode.cacheValue;}}
classDoubleLinkedList{CacheNodehead=null,tail=null;publicCacheNodeadd(Stringkey,Stringvalue){CacheNodenode=newCacheNode();node.cacheKey=key;node.cacheValue=value;addToHead(node);returnnode;}publicCacheNoderemoveTailNode(){CacheNodetailNode=tail;detach(tailNode);returntailNode;}publicvoiddetach(CacheNodenode){// Remove the node from the list.if(node.frontNode==null)head=node.backNode;elsenode.frontNode.backNode=node.backNode;if(node.backNode==null)tail=node.frontNode;elsenode.backNode.frontNode=node.frontNode;node.frontNode=node.backNode=null;}publicvoidmoveToHead(CacheNodenode){detach(node);addToHead(node);}publicvoidaddToHead(CacheNodenode){if(head!=null)head.frontNode=node;node.backNode=head;head=node;if(tail==null)tail=head;}}