LRU Cache Using a Doubly Linked List (Trace)

Starting with an empty LRU cache of capacity c, process a sequence of accessed keys (get-or-insert). After all accesses print the cache contents from most recently used to least recently used.

1 <= c <= 1000 1 <= n <= 10^5