MARISSA MOLEJON | OCT2025-1 | Module-Complexity | Sprint 2 | feat/lru cache - #5

Summary

Implements LruCache in lru_cache.py, supporting get and set,
both O(1) worst-case, with least-recently-used eviction once the cache
reaches its limit.

Design

Combines two structures:

• A dict (_nodes_by_key) for O(1) key lookup.
• A doubly-linked list tracking usage recency, most-recently-used at
  the head, least-recently-used at the tail.

Every get or set on an existing key moves that entry's node to the
head of the list. When set is called on a new key and the cache is
already at limit, the tail node (least recently used) is evicted from
both the dict and the list before the new entry is inserted at the head.

This mirrors the doubly-linked list design from Issue CodeYourFuture#9 - the same
"give each node enough info to reconnect its own neighbors" idea makes
both moving-to-head and evicting-the-tail O(1), with no searching.

LruCache(limit=0) (or negative) raises ValueError immediately.

Testing

All 5 provided tests pass, including the two that specifically exercise
eviction order:

• test_eviction_order_just_inserts - eviction based on insertion order
• test_eviction_order_after_gets - proves get also refreshes recency,
  not just set

Ran locally via python3 -m pytest lru_cache_test.py -v - all passing.

Learning points

• A dict alone can't track order of use; a linked list alone can't
  jump straight to a key. Combining them is what makes both lookup and
  reordering O(1) - each structure covers the other's weakness.
• The dict and linked list must be kept in sync on every mutation
  (insert, remove, evict) - this is a manual invariant Python won't
  enforce, so eviction updates both together in one method.
• Both get and set must refresh recency, not just set - easy to
  miss if you only think about "writes" as the thing that matters, but
  the README (and test_eviction_order_after_gets) make clear reads
  count too.

Checklist

• get and set are both O(1) worst-case
• All tests pass
• No test files modified
• Self-reviewed for readability, naming, and duplication