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 axum::{extract::{Path, State}, http::StatusCode, Json};
use dashmap::DashMap;
use serde::Serialize;
use std::sync::Arc;

Request coalescing in an Axum handler

caching concurrency request-coalescing
Advanced 8 steps
go 
package handlers
 
import (
	"net/http"

Serving embedded static meta files in Gin

embedding static assets http caching
Intermediate 6 steps
go 
package config
 
import (
	"fmt"

A thread-safe config singleton in Go

singleton concurrency environment-variables
Intermediate 7 steps
typescript 
type CsvColumn<T> = {
  header: string;
  value: (row: T) => string | number | boolean | null | undefined;
};

Building a type-safe CSV writer in TypeScript

generics serialization escaping
Intermediate 7 steps
go 
package scheduler
 
import (
	"container/heap"

A priority job queue with Go's container/heap

priority-queue heap interfaces
Intermediate 9 steps
go 
func UploadChunk(c *gin.Context) {
	uploadID := c.Param("uploadID")
	if !validUploadID.MatchString(uploadID) {
		c.JSON(http.StatusBadRequest, gin.H{"error": "invalid upload id"})

Resumable chunked uploads in Gin

file-upload content-range streaming
Advanced 9 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