Thread-Safe LRU Cache with O(1) Get/Put

package main

import (
	"container/list"
	"fmt"
	"sync"
)

type entry struct {
	key   string
	value string
}

type LRUCache struct {
	mu       sync.Mutex
	capacity int
	ll       *list.List
	items    map[string]*list.Element
}

func NewLRUCache(capacity int) *LRUCache {
	if capacity < 1 {
		panic("capacity must be >= 1")
	}
	return &LRUCache{
		capacity: capacity,
		ll:       list.New(),
		items:    make(map[string]*list.Element, capacity),
	}
}

func (c *LRUCache) Get(key string) (string, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()

	el, ok := c.items[key]
	if !ok {
		return "", false
	}
	c.ll.MoveToFront(el)
	return el.Value.(entry).value, true
}

func (c *LRUCache) Put(key, value string) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if el, ok := c.items[key]; ok {
		el.Value = entry{key: key, value: value}
		c.ll.MoveToFront(el)
		return
	}

	el := c.ll.PushFront(entry{key: key, value: value})
	c.items[key] = el

	if c.ll.Len() > c.capacity {
		back := c.ll.Back()
		if back != nil {
			c.ll.Remove(back)
			ev := back.Value.(entry)
			delete(c.items, ev.key)
		}
	}
}

func (c *LRUCache) Len() int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.ll.Len()
}

func main() {
	cache := NewLRUCache(2)
	cache.Put("a", "1")
	cache.Put("b", "2")

	if v, ok := cache.Get("a"); ok {
		fmt.Println("a =", v)
	}

	cache.Put("c", "3")
	_, ok := cache.Get("b")
	fmt.Println("b present?", ok)
	fmt.Println("len =", cache.Len())
}