LRU Cache

Design an LRU (Least Recently Used) cache with O(1) get and put operations. Explain the data structures you'd use and why, and what happens on a cache hit vs. a cache miss when the cache is full.