How LRU Cache Achieves O(1) Get and Put with Hash Map and Doubly Linked List

An LRU (Least Recently Used) cache must support two operations in O(1) average time: finding a value by key, and identifying the least recently used item when the cache is full and a new entry must be inserted. The article demonstrates how a hash map and a doubly linked list work together to achieve this.

What Order Does LRU Maintain?

Starting with an empty cache of capacity 3, the sequence put(A,1), put(B,2), put(C,3) yields the order C → B → A from most-recent to least-recent. A successful get(A) returns 1 and moves A to the front, making the order A → C → B. A subsequent put(D,4) evicts the tail node B (not A, which was just accessed), resulting in D → A → C. The article emphasizes that "use" includes successful reads as well as writes or updates of existing keys; a cache miss does not change the order.

Hash Map for Lookup, Doubly Linked List for Order

The hash map stores key → node mappings, giving average O(1) key lookup. The doubly linked list arranges nodes from head (most recent) to tail (least recent). Two sentinel nodes head and tail simplify boundary conditions: head.next is the most recent real node, tail.prev is the least recent. Each list node holds prev and next pointers plus the key and value. Because the node is directly addressable, moving it to the front requires only pointer updates — no traversal — which is why a doubly linked list is chosen over a singly linked list.

get : Find Value and Move Node to Front

For get(A) when the list is C → B → A, the hash map locates A's node in O(1), the value 1 is returned, and the node is unlinked from its current position and inserted after head. The new order becomes A → C → B. The same node object is reused; the hash map entry remains valid. A miss (e.g., get(X)) returns -1 and leaves the list untouched. A hit performs one hash lookup, one unlink, and one front insertion — all O(1) on average.

put : Insert New Key or Update Existing Key

put(key, value)

first checks the hash map. If the key exists (e.g., put(C,30) when order is A → C → B), the node's value is updated and the node is moved to the front, yielding C → A → B. If the key is new, a node is created, added to the hash map, and inserted at the front (e.g., put(C,3) into B → A gives C → B → A). When the cache is at capacity, the tail node ( tail.prev) is removed from both the list and the hash map before the new node is inserted. The article stresses that both structures must be updated together; otherwise a stale hash entry could return an evicted node.

Why Eviction Can Directly Remove the Tail

Because the list is kept in strict recency order, the least recently used node is always at tail.prev. No scan is needed. Eviction unlinks that node from the list and deletes its key from the hash map — both O(1) average. The node's stored key is used for the hash map deletion.

Python Implementation and Complexity Verification

The article provides a complete, runnable Python implementation. The Node class holds key, value, prev, next. LRUCache initializes capacity, the hash map nodes, and the sentinel nodes head and tail linked to each other. Helper methods _remove(node) and _add_front(node) each adjust a constant number of pointers. _move_to_front composes them. get and put reuse these helpers. The code handles capacity 0 by performing no storage. A test sequence at the end demonstrates the behavior:

cache = LRUCache(3)
cache.put("A", 1)
cache.put("B", 2)
cache.put("C", 3)
print(cache.get("A"))  # 1; order A → C → B
cache.put("D", 4)      # evicts B; order D → A → C
cache.put("C", 30)     # order C → D → A
print(cache.get("C"))  # 30
print(cache.get("B"))  # -1

Because _remove and _add_front touch only a fixed number of pointers, they run in O(1). Hash map operations ( get , insertion, deletion) are average O(1). Therefore both get and put have average time complexity O(1); worst case depends on hash collisions. Space usage is O(capacity + 1) for the hash map and list nodes plus the two sentinels.

Summary

The LRU cache divides responsibilities cleanly: the hash map finds nodes by key, the doubly linked list records recency order. Every successful access or write moves the corresponding node to the head. When space is needed, the tail node is evicted. This design delivers O(1) average time for queries, updates, and eviction-triggering inserts.