Guided Project: O(1) Least Recently Used (LRU) Cache
Construct a generic Least Recently Used (LRU) Cache achieving strict O(1) get and put performance via hash maps and doubly linked lists.
By the end, you’ll be able to…
- Design an internal doubly linked list with dummy head and tail sentinel nodes.
- Integrate a HashMap to index nodes for constant-time O(1) key lookups.
- Implement LRU eviction logic that removes the least recently accessed node when capacity is breached.
01Algorithmic Architecture of an LRU Cache
An LRU (Least Recently Used) Cache is one of the most celebrated and frequently deployed data structures in systems design. When storage capacity is constrained, the cache must discard the item that has not been queried for the longest time.
To support high-throughput operations, both get(K key) and put(K key, V value) must execute in strict O(1) constant time. A HashMap provides O(1) lookup, but does not track usage order. A linked list tracks order, but requires O(N) linear search to locate items. Combining them creates the optimal solution: a HashMap paired with a Doubly Linked List.
In enterprise systems running on the Java Virtual Machine, clean architecture and predictable memory dynamics directly influence operational stability. By establishing strict access boundaries, validating preconditions, and managing object lifecycles deliberately, engineers ensure that high-throughput applications remain stable under heavy load without degrading garbage collection metrics.
02Sentinel Nodes: Simplifying Linked List Pointer Mechanics
Manipulating pointers in a doubly linked list often produces brittle null checks for head and tail updates. A proven systems pattern is introducing dummy sentinel nodes: a dummy head and dummy tail that always exist.
With sentinels, every real data node is guaranteed to have non-null prev and next references. Inserting a node at the front or detaching a node from the middle requires uniform pointer swaps without special-casing boundary conditions.
Furthermore, designing with interface contracts and encapsulation shields internal implementation details from external changes. When downstream services rely on abstractions, engineering teams can optimize underlying algorithms and internal structures without introducing breaking changes across distributed microservice boundaries.
03Implementing O(1) Get and Put Operations
When get(key) is invoked, the cache checks the map. If missing, it returns null. If present, it detaches the node from its current position and moves it to the front directly behind head, marking it as most recently used.
When put(key, value) is invoked, if the key already exists, its value is updated and moved to the front. If the key is new, a new node is inserted at the front. If total entries exceed capacity, the least recently used node directly before tail is evicted from both the list and the map.
04Assembling the Complete Generic LRU Cache
Now we assemble the complete generic class, adding size tracking and thread synchronization locks. We test edge cases, verifying that repeatedly accessing an item keeps it alive while older untouched entries are purged.
This project demonstrates how combining primitive data structures yields industrial-grade caching components.
The ideas worth keeping.
- Combining a HashMap with a Doubly Linked List enables O(1) lookups and O(1) evictions.
- Sentinel head and tail nodes eliminate tedious null boundary conditions in linked list mutations.
- LRU caching is the industry-standard algorithm for managing constrained memory pools.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Cache Hit Rate Calculator
Write a class CacheStats with int hits and int misses, and a method double hitRatio() returning hits / (hits + misses).
Explore a worked solution
public class CacheStats { private int hits = 0; private int misses = 0; public void recordHit() { hits++; } public void recordMiss() { misses++; } public double hitRatio() { int total = hits + misses; return total == 0 ? 0.0 : (double) hits / total; }}Tracking hit ratios is essential for tuning cache capacities and validating eviction efficiency in production services.
Clear Cache Utility
Write a method void clear() for LruCache that empties the map and resets the head and tail sentinel links.
Explore a worked solution
public synchronized void clear() { map.clear(); head.next = tail; tail.prev = head;}Resetting sentinel pointers detaches all interior nodes, allowing the JVM garbage collector to reclaim node memory immediately.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Cache Hit Rate Calculator
Write a class CacheStats with int hits and int misses, and a method double hitRatio() returning hits / (hits + misses).
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this chapter, when you want a second angle or the full details.
Pause. Put the pieces together.
You’ve reached the end of Collections, Generics & Data Structures. Before moving on, use this task to check what you can do independently.
Deliver an operational LRU cache with verified O(1) get and put operations.
Try it in your own environment and write down the result. This is a self-check; reading completion does not evaluate your code.
Review this moduleOne chapter closer.
Reading is a start. Trying it yourself makes the connection.