🏗️ Phase II: Implementation Milestones (The Code Flow)

This phase breaks down the implementation into logical, testable steps.

Milestone 1: Basic Structure and Initialization (Setup)

• Action: Define the Node and LRUCache structs.
• Function: Implement a constructor function (NewLRUCache(capacity int) *LRUCache).
• Check: Initialize the map, set capacity, and ensure the list pointers are nil or correctly pointing to sentinel nodes (optional but robust).

Milestone 2: List Management Helpers (The $O(1)$ Engine)

Before implementing core cache methods, we need helper functions that manage the linked list structure efficiently. This is the most critical step.

• moveToHead(node *Node): Given a node pointer, removes it from its current position in the list and re-links it to be directly after the head. (Complexity: $O(1)$)
• popTail(): Removes the tail node (the LRU item) and returns its key/value. This handles eviction. (Complexity: $O(1)$)

Milestone 3: Implementing Put (Write Operation)

The Put operation must handle three cases atomically:

1. Key Exists (Hit): If the key is in the map, retrieve the node. Call moveToHead() on that node to mark it as recently used. Update its value if necessary.
2. New Key: Create a new Node. Add the key/value pair to the map and insert the node at the head of the list (MRU).
3. Capacity Check & Eviction: If, after adding the new item, the cache size exceeds capacity, call popTail() to remove the LRU node before returning.

Milestone 4: Implementing Get (Read Operation)

The Get operation must also maintain usage order:

1. Lookup: Check if the key exists in the internal map.
2. Miss: If not found, return a zero value/error immediately.
3. Hit: If found, retrieve the node pointer. Call moveToHead() on this node to promote it (marking it as recently used). Return the node's value.

Milestone 5: Concurrency Safety (Polish)

• Action: Wrap all public methods (Get, Put) with lock/unlock logic using sync.Mutex.
• func (c *LRUCache) Get(...) string { c.mu.Lock(); defer c.mu.Unlock(); ... }