LRU Cache Implementation Using Object-Oriented Design Principles: Python Guide

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 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:

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. 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 with production usage examples in 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}