LRU Cache

A Least Recently Used (LRU) Cache is a cache replacement policy that discards the least recently used items first. This algorithm requires keeping track of what was used when, which can be computationally expensive if not implemented correctly. The challenge is to design a data structure that can support both `get(key)` and `put(key, value)` operations in O(1) time. A `get` operation should retrieve an item and mark it as recently used. A `put` operation should insert or update an item, also marking it as recently used. If the cache is full during a `put`, it must evict the least recently used item before inserting the new one. The optimal way to implement this is by combining two data structures: a hash map and a doubly linked list. The hash map provides O(1) lookup of keys. The value of the hash map will not be the actual data, but a pointer to a node in a doubly linked list. The doubly linked list will be used to maintain the order of usage. The most recently used item will be at the head of the list, and the least recently used item will be at the tail. When an item is accessed (via `get` or `put`), we move its corresponding node to the head of the list. When an eviction is needed, we simply remove the node at the tail of the list. This combination allows all operations to be performed in O(1) time.