🧱 Phase I: Architecture and Data Structures Design (The Blueprint)
A. Core Components Analysis
To achieve $O(1)$ complexity for both lookups and reordering/eviction, we need a combination of two standard computer science structures:
- Hash Map (
map[KeyType] *Node): Used for fast key lookup ($O(1)$). It allows us to immediately access the associated node in our list given any key. - Doubly Linked List: Used to maintain the order of usage (Most Recently Used $\rightarrow$ ... $\rightarrow$ Least Recently Used). Because it is doubly linked, we can move a node from its current position and re-insert it at the head in $O(1)$ time.
B. Proposed Go Data Structures
We will define three primary structs:
1. Node (The element in the list):
Key: The type of the key used for the map lookup.Value: The associated data value stored in the cache.Prev *Node: Pointer to the previous node in the list.Next *Node: Pointer to the next node in the list.
2. LRUCache (The container/cache itself):
capacity int: The maximum number of items the cache can hold.map map[KeyType]*Node: Maps keys to their corresponding Node pointer for $O(1)$ access.head *Node: Pointer to the head of the linked list (MRU - Most Recently Used).tail *Node: Pointer to the tail of the linked list (LRU - Least Recently Used).- Concurrency Control:
mu sync.Mutex: Required mutex to ensure thread safety.