James Postadan | Oct2025-2 | Module Complexity | Sprint 2 | Implement an LRU cache in Python - #16

🎯 Summary

• Implemented an LRU (Least Recently Used) cache in Python with O(1) get and set
• LruCache(limit) — raises ValueError when limit is 0
• get(key) — returns value or None; counts as a use and promotes entry to most-recent
• set(key, value) — stores entry; updates and promotes if key exists; evicts least-recently-used when over limit

🧾 Changelist

• Data structure: dict + doubly linked list. The dict maps key → Node for O(1) lookup. The doubly linked list tracks recency — head is most recently used, tail is least recently used. Both structures are needed: without the dict, finding a node by key is O(n); without the list, moving a node to the front or evicting the tail is O(n).
• get: look up the node in the dict (O(1)), move it to the head of the list (O(1)), return its value.
• set: if the key already exists, update the value and move the node to the head (O(1)). If new, create a node, push to head, add to dict — then if len(store) > limit, evict the tail: delete from dict by tail.key and unlink from list (all O(1)).
• Internal list operations: _push_head, _unlink, _move_to_head, _evict_tail — each does only pointer reassignment, all O(1).

❓ Questions

• get returns None for a missing key. Should it raise a KeyError instead (dict-like behaviour), or is returning None the right API for a cache where misses are expected?

🙌 Notes for Reviewers

• Upstream issue: Implement an LRU cache in Python CodeYourFuture/Module-Complexity#10
• Tests: python3 -m unittest lru_cache_test -v from Sprint-2/implement_lru_cache/ — 5/5 pass
• Covers: basic get/set, limit enforcement, eviction order with inserts only, eviction order after mixed get/set usage