go 58 lines · 8 steps

Building a generic LRU cache in Go

A doubly linked list plus a map gives O(1) lookups while tracking which entries are least recently used.

Explained by highlit
Intermediate lru-cache generics linked-list concurrency data-structures
1package cache
2 
3import (
4 "container/list"
5 "sync"
6)
7 
8type entry[K comparable, V any] struct {
9 key K
10 value V
11}
12 
13type LRU[K comparable, V any] struct {
14 mu sync.Mutex
15 capacity int
16 ll *list.List
17 items map[K]*list.Element
18}
19 
20func New[K comparable, V any](capacity int) *LRU[K, V] {
21 if capacity <= 0 {
22 panic("cache: capacity must be positive")
23 }
24 return &LRU[K, V]{
25 capacity: capacity,
26 ll: list.New(),
27 items: make(map[K]*list.Element, capacity),
28 }
29}
30 
31func (c *LRU[K, V]) Get(key K) (V, bool) {
32 c.mu.Lock()
33 defer c.mu.Unlock()
34 if el, ok := c.items[key]; ok {
35 c.ll.MoveToFront(el)
36 return el.Value.(*entry[K, V]).value, true
37 }
38 var zero V
39 return zero, false
40}
41 
42func (c *LRU[K, V]) Put(key K, value V) {
43 c.mu.Lock()
44 defer c.mu.Unlock()
45 if el, ok := c.items[key]; ok {
46 el.Value.(*entry[K, V]).value = value
47 c.ll.MoveToFront(el)
48 return
49 }
50 c.items[key] = c.ll.PushFront(&entry[K, V]{key, value})
51 if c.ll.Len() > c.capacity {
52 oldest := c.ll.Back()
53 if oldest != nil {
54 c.ll.Remove(oldest)
55 delete(c.items, oldest.Value.(*entry[K, V]).key)
56 }
57 }
58}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Pairing a map for lookup with a linked list for ordering gives both O(1) access and O(1) recency updates.
  2. 2Touching an entry means moving it to the front, so the back of the list is always the eviction candidate.
  3. 3A single mutex around every operation keeps the two coupled structures consistent under concurrent access.

Related explainers

go 
package streaming
 
import (
	"bufio"

Streaming NDJSON logs over HTTP in Go

http-streaming channels select
Advanced 10 steps
go 
package api
 
import (
	"crypto/sha256"

ETag conditional requests in Gin

http-caching etag conditional-requests
Intermediate 6 steps
go 
func (w *Watcher) resetDebounce(d time.Duration) {
	if !w.timer.Stop() {
		select {
		case <-w.timer.C:

Debouncing a stream of events in Go

debounce timers channels
Advanced 7 steps
go 
package logging
 
import (
	"context"

Deduplicating log attributes in Go's slog

decorator-pattern structured-logging immutability
Intermediate 8 steps
rust 
use std::collections::VecDeque;
use std::sync::{Arc, Condvar, Mutex};
use std::time::{Duration, Instant};
 

Building a counting semaphore in Rust

concurrency synchronization condition-variable
Advanced 9 steps
go 
package middleware
 
import (
	"net/http"

Per-plan export limits in Gin middleware

middleware rate-limiting authorization
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Building a generic LRU cache in Go — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code