An LRU cache is usually a map plus a doubly linked list

The map finds a node by key; the list keeps most-recently-used order. A hit moves its node to the front, and an eviction removes the tail. With expected O(1) map operations and constant-time list updates, get and put take expected O(1).