HashMap + Doubly Linked List

The recognizable HashMap plus doubly linked list pattern is an LRU cache. The map gives O(1) access from key to node; the list gives O(1) removal and promotion. Use head and tail sentinel nodes so insert and removal never need special cases for an empty or one-item cache. get returns a missing value when absent; when present it moves that node to the most-recent end. put updates and promotes an existing node, or creates a node and, if capacity is exceeded, evicts the node immediately before the least-recent sentinel and deletes its key from the map. State the invariant that every mapped node appears exactly once in the list. Test capacity zero or one, repeated updates, eviction after a get, and removal pointers. Each operation is O(1) time and the cache uses O(capacity) space.