LRU Cache

LRU (Least Recently Used) is a cache eviction strategy that optimizes for recency: when the cache reaches its capacity, it evicts the entry that hasn’t been accessed for the longest time. A typical LRU implementation combines two data structures:

• a map for O(1) lookups by key
• a doubly linked list to track usage order (most-recent at the front, least-recent at the back)

Add / Put

When adding a key: If the key already exists, update its value and move the corresponding node to the front of the list (marking it as most recently used).

If the key is new, insert it at the front and store its list node in the map. After insertion, if the cache exceeds its capacity, evict the least recently used entry (the node at the back of the list) and remove it from both the list and the map.

Get

When retrieving a key: If it exists, move it to the front of the list and return its value. If it doesn’t exist, return an empty value. Below is a sample implementation in Go.

package main

import (
	"container/list"
	"fmt"
)

type entry struct {
	key, value string
}

type Cache struct {
	mm       map[string]*list.Element
	ll       *list.List
	capacity int
}

func NewCache(capacity int) *Cache {
	return &Cache{
		mm:       make(map[string]*list.Element),
		ll:       list.New(),
		capacity: capacity,
	}
}

// Add inserts or updates key/value and marks it as most-recently-used.
func (c *Cache) Add(key, value string) {
	if c.capacity <= 0 {
		return // treat as always-empty cache
	}

	// Update existing
	if el, ok := c.mm[key]; ok {
		el.Value.(*entry).value = value
		c.ll.MoveToFront(el)
		return
	}

	// Insert new at front
	el := c.ll.PushFront(&entry{key: key, value: value})
	c.mm[key] = el

	// Evict if over capacity
	if len(c.mm) > c.capacity {
		lru := c.ll.Back()
		if lru != nil {
			ent := lru.Value.(*entry)
			delete(c.mm, ent.key)
			c.ll.Remove(lru)
		}
	}
}

// Get returns (value, true) if present; otherwise ("", false).
// Accessing a key marks it as most-recently-used.
func (c *Cache) Get(key string) (string, bool) {
	if el, ok := c.mm[key]; ok {
		c.ll.MoveToFront(el)
		return el.Value.(*entry).value, true
	}
	return "", false
}

func (c *Cache) Size() int {
	return len(c.mm)
}

func main() {
	lru := NewCache(4)
	lru.Add("1", "1")
	lru.Add("2", "2")
	lru.Add("3", "3")
	lru.Add("4", "4")

	lru.Add("5", "5") // evicts "1"
	lru.Add("5", "6") // update, stays MRU
	lru.Add("7", "7") // evicts "2"

	if _, ok := lru.Get("1"); !ok {
		fmt.Println("1 is evicted")
	}

	if v, ok := lru.Get("2"); ok {
		fmt.Println("2 =", v)
	} else {
		fmt.Println("2 is evicted")
	}

	fmt.Println("size =", lru.Size())
}