How to Implement a Least Recently Used (LRU) Cache

A cache has a fixed capacity. When it is full and a new item must be added, the item that was accessed least recently is removed first. The most recently used item always stays safe.

You need two structures working together. A Hash Map gives you instant lookup of any item. A Doubly Linked List maintains the order of use, with the most recently used item at the front and the least recently used item at the back.

Each node stores a key, a value, a pointer to the next node, and a pointer to the previous node. The previous pointer allows you to remove any node in constant time without traversal.

Create two dummy nodes called HEAD and TAIL and connect them to each other. HEAD represents the most recently used end and TAIL represents the least recently used end. These dummies eliminate NULL edge cases during insertion and deletion.

When a key is requested, check the Hash Map. If the key does not exist, return negative one. If it exists, move that node to the front of the list right after HEAD because it was just accessed and is now the most recently used. Then return its value.

When inserting a key value pair, if the key already exists update its value and move it to the front. If it is new, create a node, insert it at the front, and add it to the Hash Map. Then check if the size exceeds capacity. If it does, remove the node right before TAIL and delete its entry from the Hash Map.

Write a Remove helper that disconnects a node by connecting its previous and next nodes directly to each other. Write an Insert helper that always places a node immediately after the HEAD dummy node. Use these two helpers inside both Get and Put to keep the code clean.