How to Implement a LRU Cache in Go

Implement an LRU cache in Go using container/list to manage order and a map for O(1) lookups.

package main

import (
	"container/list"
)

type LRUCache struct {
	capacity int
	list     *list.List
	cache    map[interface{}]*list.Element
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		list:     list.New(),
		cache:    make(map[interface{}]*list.Element),
	}
}

func (lru *LRUCache) Get(key interface{}) (interface{}, bool) {
	if elem, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(elem)
		return elem.Value.(*entry).value, true
	}
	return nil, false
}

func (lru *LRUCache) Put(key, value interface{}) {
	if elem, ok := lru.cache[key]; ok {
		elem.Value.(*entry).value = value
		lru.list.MoveToFront(elem)
		return
	}
	lru.cache[key] = lru.list.PushFront(&entry{key, value})
	if lru.list.Len() > lru.capacity {
		lru.removeOldest()
	}
}

func (lru *LRUCache) removeOldest() {
	elem := lru.list.Back()
	lru.list.Remove(elem)
	delete(lru.cache, elem.Value.(*entry).key)
}

type entry struct {
	key, value interface{}
}

An LRU cache keeps your most recently used data in memory for fast access while automatically discarding the least used items when space runs out. Think of it like a desk drawer that only holds your current tools; when you add a new tool, you toss out the one you haven't touched in the longest time. This pattern is essential for optimizing performance in applications where data access patterns are predictable.