LRU Cache with TTL (Java)

A thread-safe, in-memory LRU cache supporting optional per-entry time-to-live expiry. Built to demonstrate core data structure design and concurrency handling, not to depend on any external library.

Why this design

HashMap + doubly linked list. The HashMap gives O(1) key lookup; the linked list tracks recency order so the least-recently-used entry can be evicted in O(1) instead of scanning. This is the standard LRU pattern, but the implementation is written from scratch rather than wrapping LinkedHashMap (which technically already provides this) — the goal was to show the mechanics, not hide behind a built-in.

Lazy + opportunistic expiry, not a background thread. Expired entries are treated as absent on get() and are removed from both the map and the list when encountered. A background sweeper thread was considered and rejected for this scope: it adds a second thread, its own shutdown/lifecycle handling, and non-trivial testing surface for a benefit (memory reclaimed slightly sooner) that doesn't matter until the cache is under real memory pressure, which is unmeasured here. Noting the tradeoff explicitly rather than skipping it silently.

Single coarse-grained lock. All mutating operations acquire one ReentrantLock. A striped or lock-free design would give higher throughput under contention, but adds real correctness risk (the linked-list pointer updates on eviction must stay consistent with the map) that isn't justified without a measured throughput requirement. Coarse-grained-but-correct over fine-grained-but-unverified.

Complexity

Operation	Time
get	O(1)
put	O(1)
remove	O(1)

Running it

javac -d out src/main/java/cache/*.java
java -cp out cache.Demo

Demo.java is a runnable check (not a JUnit suite — kept dependency-free) covering: eviction order under capacity pressure, TTL expiry, and that updating an existing key refreshes recency without creating a duplicate node.

What's intentionally out of scope

• Persistence / write-through to a backing store
• Per-key locking for higher concurrent throughput
• Configurable eviction policies beyond LRU (e.g. LFU)

These are natural next steps, left out to keep the core data structure and its correctness the focus.