# LRU Cache Implementation Using Object-Oriented Design Principles: Python Guide > Learn LRU cache implementation with object-oriented Python. Achieve O(1) retrieval and insertion using a hash map and doubly-linked list, with automatic eviction. - Repository: [Donne Martin/system-design-primer](https://github.com/donnemartin/system-design-primer) - Tags: deep-dive - Published: 2026-02-24 --- **An LRU cache implementation using object-oriented design principles achieves O(1) performance for both retrieval and insertion by combining a hash map with a doubly-linked list, automatically evicting the least recently used entries when capacity is reached.** The System Design Primer repository provides a canonical example of an LRU cache implementation using object-oriented design principles that demonstrates how to balance algorithmic constraints with clean software architecture. This design appears in [`solutions/object_oriented_design/lru_cache/lru_cache.py`](https://github.com/donnemartin/system-design-primer/blob/main/solutions/object_oriented_design/lru_cache/lru_cache.py) and serves as a foundation for high-performance caching layers in distributed systems. The implementation separates data storage from access ordering through three distinct classes that collaborate to maintain constant-time operations. ## Core Architecture Components The implementation relies on three distinct classes working in concert to guarantee O(1) time complexity for all operations. ### The Node Class The `Node` class serves as the container for cached values within the doubly-linked list. Each instance stores the payload in a `results` attribute and maintains `next` and `prev` pointers to neighboring nodes. This bidirectional linking enables the `Cache` class to remove and reposition arbitrary nodes in constant time without traversing the entire structure. ### The LinkedList Class The `LinkedList` class manages access ordering through explicit **head** and **tail** pointers. The most recently used item resides at the head, while the least recently used item sits at the tail awaiting eviction. Critical methods include `move_to_front` for promoting accessed nodes, `append_to_front` for new insertions, and `remove_from_tail` for evicting the oldest entry when capacity is exceeded. ### The Cache Class The `Cache` class orchestrates the data structures and exposes the public API through `get` and `set` methods. It maintains a `lookup` dictionary (hash map) that maps keys directly to `Node` references, providing immediate access to any cached item. This dictionary eliminates search penalties, while the `LinkedList` instance handles recency tracking and eviction policy enforcement. ## How Insertion and Lookup Work Understanding the operational flow reveals why this design guarantees constant-time performance regardless of cache size. ### Insertion via set() When `set(key, value)` is called, the implementation first checks the `lookup` dictionary. If the key exists, the corresponding node's `results` are updated and `move_to_front` promotes it to the head. For new keys when the cache is at capacity, `remove_from_tail` evicts the oldest entry from both the linked list and the dictionary. Finally, `append_to_front` adds the new node and updates the lookup reference, maintaining synchronized state between both data structures. ### Lookup via get() The `get(key)` method retrieves the `Node` from the hash map in O(1) time. Before returning the stored `results`, it calls `move_to_front` to reposition the node at the head, marking it as recently used. This automatic promotion ensures that frequently accessed items remain in cache, while untouched items naturally migrate toward the tail for eventual eviction. ## Complete Implementation Example The following runnable example demonstrates the LRU cache behavior using the actual implementation from the repository at [`solutions/object_oriented_design/lru_cache/lru_cache.py`](https://github.com/donnemartin/system-design-primer/blob/main/solutions/object_oriented_design/lru_cache/lru_cache.py): ```python from solutions.object_oriented_design.lru_cache.lru_cache import Cache # Initialize cache with capacity of 3 cache = Cache(MAX_SIZE=3) # Populate to capacity cache.set('SELECT * FROM users', ['Alice', 'Bob']) cache.set('SELECT * FROM orders', ['Order1', 'Order2']) cache.set('SELECT * FROM products', ['ProductA', 'ProductB']) # Access moves item to front (marking as recently used) users = cache.get('SELECT * FROM users') # Returns ['Alice', 'Bob'] # Insertion beyond capacity triggers eviction of least recently used item cache.set('SELECT * FROM categories', ['Cat1', 'Cat2']) # The "orders" query was evicted print(cache.get('SELECT * FROM orders')) # Returns None ``` This example illustrates automatic promotion on access and the eviction of the oldest entry when exceeding `MAX_SIZE`, demonstrating the cache's self-managing properties. ## Integration in System Design Beyond the isolated implementation, the System Design Primer applies this LRU cache to real-world database optimization scenarios in [`solutions/system_design/query_cache/query_cache_snippets.py`](https://github.com/donnemartin/system-design-primer/blob/main/solutions/system_design/query_cache/query_cache_snippets.py). Here, the cache stores expensive database query results, reducing load on backend systems by serving frequent lookups from memory. The object-oriented structure allows the `Cache` class to integrate cleanly with larger request-handling pipelines while maintaining strict O(1) performance guarantees for both hits and misses. ## Summary - The **LRU cache implementation** in `donnemartin/system-design-primer` combines a hash map and doubly-linked list to achieve O(1) operations for `get` and `set`. - The **`Node`** class stores values and linkage pointers, **`LinkedList`** manages recency ordering with head/tail operations, and **`Cache`** coordinates both structures via a `lookup` dictionary. - **`get`** automatically promotes items via `move_to_front`, while **`set`** handles eviction through `remove_from_tail` when capacity is reached. - Source files are located in [`solutions/object_oriented_design/lru_cache/lru_cache.py`](https://github.com/donnemartin/system-design-primer/blob/main/solutions/object_oriented_design/lru_cache/lru_cache.py) with production usage examples in [`solutions/system_design/query_cache/query_cache_snippets.py`](https://github.com/donnemartin/system-design-primer/blob/main/solutions/system_design/query_cache/query_cache_snippets.py). ## Frequently Asked Questions ### What makes an LRU cache implementation using object-oriented design principles efficient? The efficiency stems from separating concerns between data storage and access ordering. The hash map provides immediate key lookup, while the doubly-linked list enables constant-time node repositioning and deletion. By delegating specific responsibilities to the `Node`, `LinkedList`, and `Cache` classes, the implementation avoids the O(n) traversal costs associated with array-based or naive approaches. ### How does the Cache class handle eviction when reaching maximum capacity? When `set` is called on a full cache, the implementation first calls `remove_from_tail` on the `LinkedList` to extract the least recently used node. It then deletes the corresponding key from the `lookup` dictionary before inserting the new entry via `append_to_front`. This dual removal ensures both data structures remain synchronized and the memory footprint stays bounded by `MAX_SIZE`. ### Can this LRU cache implementation be used in production systems? Yes, the `donnemartin/system-design-primer` implementation provides a solid algorithmic foundation, though production deployments may require additional thread-safety mechanisms for concurrent access. The current design assumes single-threaded operation, so integrating locks or using atomic operations would be necessary for multi-threaded environments. The core O(1) guarantees and object-oriented structure remain valid for high-throughput caching layers. ### Why use a doubly-linked list instead of a singly-linked list for the LRU cache? A doubly-linked list is essential because removing arbitrary nodes when updating existing keys requires access to the previous node to adjust pointers. The `prev` reference allows `move_to_front` and removal operations to execute in O(1) time without traversing from the head. A singly-linked list would require O(n) traversal to find the predecessor, defeating the performance goals of the cache.