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

rust 
use std::collections::HashMap;
use std::sync::{Arc, Mutex};
use std::thread;
 

Aggregating metrics across threads in Rust

concurrency shared-state mutex
Intermediate 7 steps
go 
package main
 
import (
	"errors"

Parsing and validating CLI flags in Go

cli-parsing validation error-handling
Intermediate 8 steps
java 
public class ThumbnailProcessor {
 
    private static final int MAX_CONCURRENCY = 4;
 

Bounded parallel thumbnail rendering in Java

concurrency thread-pool futures
Intermediate 7 steps
rust 
use std::sync::{mpsc, Arc, Mutex};
use std::thread;
use std::time::Duration;
 

Building a thread pool in Rust

concurrency channels thread-pool
Advanced 9 steps
go 
package model
 
import (
	"encoding/json"

Custom JSON marshaling in Go

json serialization interfaces
Intermediate 5 steps
rust 
use std::collections::HashMap;
 
pub struct Memoizer<K, V, F> {
    cache: HashMap<K, V>,

A generic memoizer in Rust

memoization generics caching
Intermediate 6 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