Approach: Use a hashmap for O(1) key lookup and a doubly-linked list to track recency (head = most-recent, tail = least). Protect structure with a sync.RWMutex to allow concurrent readers and exclusive writers. For put that updates recency or evicts, use write lock; for get we acquire read lock, but upgrade to write lock when moving node to head.go
package lru
import (
"sync"
)
type entry struct {
key string
value interface{}
prev *entry
next *entry
}
type LRUCache struct {
capacity int
mu sync.RWMutex
items map[string]*entry
head *entry
tail *entry
}
func New(cap int) *LRUCache {
return &LRUCache{
capacity: cap,
items: make(map[string]*entry, cap),
}
}
// moveToHead assumes caller holds write lock and node != nil
func (c *LRUCache) moveToHead(e *entry) {
if c.head == e { return }
// unlink
if e.prev != nil { e.prev.next = e.next }
if e.next != nil { e.next.prev = e.prev }
if c.tail == e { c.tail = e.prev }
// insert at head
e.prev = nil
e.next = c.head
if c.head != nil { c.head.prev = e }
c.head = e
if c.tail == nil { c.tail = e }
}
func (c *LRUCache) Get(key string) (interface{}, bool) {
// fast path: read lock to check presence
c.mu.RLock()
e, ok := c.items[key]
c.mu.RUnlock()
if !ok { return nil, false }
// need to update recency -> acquire write lock
c.mu.Lock()
// re-check in case of races
e2, still := c.items[key]
if still && e2 != nil {
c.moveToHead(e2)
val := e2.value
c.mu.Unlock()
return val, true
}
c.mu.Unlock()
return nil, false
}
func (c *LRUCache) Put(key string, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
if e, ok := c.items[key]; ok {
e.value = value
c.moveToHead(e)
return
}
e := &entry{key: key, value: value}
// insert new at head
e.next = c.head
if c.head != nil { c.head.prev = e }
c.head = e
if c.tail == nil { c.tail = e }
c.items[key] = e
if len(c.items) > c.capacity {
// evict tail
if c.tail != nil {
delete(c.items, c.tail.key)
c.tail = c.tail.prev
if c.tail != nil { c.tail.next = nil } else { c.head = nil }
}
}
}
