⌘K

Designing a Data Structure

EditorialUpdated Nov 9, 2026

A cache that slows down as it grows

A cache keeps the answers you asked for recently, so the next ask is fast. When it's full, it throws out the one nobody has asked for in the longest time: that's least recently used, LRU. The first version everyone writes keeps the keys in a list, least recent first, and every get or put moves its key to the end. Here it is beside a map into a doubly linked list, on the same 100,000 calls, one put in three, at capacities 1,000 and 4,000:

import time


def workload(capacity, ops):                  # the same calls in every language: one put in three
    x, calls = 7, []
    for _ in range(ops):
        x = x * 48271 % 2147483647
        put = x % 3 == 0
        x = x * 48271 % 2147483647
        calls.append((put, x % (2 * capacity)))
    return calls


class ListLRU:                                # keys in a list, least recent first: every touch searches it
    def __init__(self, capacity):
        self.capacity, self.order, self.values = capacity, [], {}

    def get(self, key):
        if key not in self.values:
            return -1
        self.order.remove(key)                # find it, then shift everything after it
        self.order.append(key)
        return self.values[key]

    def put(self, key, value):
        if key in self.values:
            self.order.remove(key)
        elif len(self.values) == self.capacity:
            del self.values[self.order.pop(0)]  # the least recent is first: shift everything left
        self.order.append(key)
        self.values[key] = value


class Node:
    def __init__(self, key, value):
        self.key, self.value, self.prev, self.next = key, value, None, None


class LinkedLRU:                              # a map into a doubly linked list, most recent first
    def __init__(self, capacity):
        self.capacity, self.nodes = capacity, {}
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self.unlink(node)
        self.push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self.unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                oldest = self.tail.prev
                self.unlink(oldest)
                del self.nodes[oldest.key]
            node = Node(key, value)
            self.nodes[key] = node
        self.push_front(node)


for cache_type in (ListLRU, LinkedLRU):
    for capacity in (1000, 4000):
        calls = workload(capacity, 100000)
        start = time.perf_counter()
        cache, hits = cache_type(capacity), 0
        for put, key in calls:
            if put:
                cache.put(key, key)
            elif cache.get(key) != -1:
                hits += 1
        ms = (time.perf_counter() - start) * 1000
        print(f"{cache_type.__name__:9} capacity {capacity}: {hits} hits in {ms:.0f} ms")

# ListLRU   capacity 1000: 32678 hits in 470 ms
# ListLRU   capacity 4000: 30947 hits in 1409 ms
# LinkedLRU capacity 1000: 32678 hits in 41 ms
# LinkedLRU capacity 4000: 30947 hits in 48 ms

import java.util.*;

public class Main {
    static int[][] workload(int capacity, int ops) {    // the same calls in every language: one put in three
        long x = 7;
        int[][] calls = new int[ops][2];
        for (int i = 0; i < ops; i++) {
            x = x * 48271 % 2147483647;
            calls[i][0] = x % 3 == 0 ? 1 : 0;
            x = x * 48271 % 2147483647;
            calls[i][1] = (int) (x % (2L * capacity));
        }
        return calls;
    }

    interface Cache {
        int get(int key);
        void put(int key, int value);
    }

    static class ListLRU implements Cache {      // keys in a list, least recent first: every touch searches it
        final int capacity;
        final List<Integer> order = new ArrayList<>();
        final Map<Integer, Integer> values = new HashMap<>();

        ListLRU(int capacity) { this.capacity = capacity; }

        public int get(int key) {
            Integer value = values.get(key);
            if (value == null) return -1;
            order.remove(Integer.valueOf(key));    // find it, then shift everything after it
            order.add(key);
            return value;
        }

        public void put(int key, int value) {
            if (values.containsKey(key)) order.remove(Integer.valueOf(key));
            else if (values.size() == capacity) values.remove(order.remove(0));   // shift everything left
            order.add(key);
            values.put(key, value);
        }
    }

    static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    static class LinkedLRU implements Cache {    // a map into a doubly linked list, most recent first
        final int capacity;
        final Map<Integer, Node> nodes = new HashMap<>();
        final Node head = new Node(0, 0), tail = new Node(0, 0);

        LinkedLRU(int capacity) {
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }

        void pushFront(Node n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }

        public int get(int key) {
            Node n = nodes.get(key);
            if (n == null) return -1;
            unlink(n);
            pushFront(n);
            return n.value;
        }

        public void put(int key, int value) {
            Node n = nodes.get(key);
            if (n != null) {
                n.value = value;
                unlink(n);
            } else {
                if (nodes.size() == capacity) {
                    Node oldest = tail.prev;
                    unlink(oldest);
                    nodes.remove(oldest.key);
                }
                n = new Node(key, value);
                nodes.put(key, n);
            }
            pushFront(n);
        }
    }

    public static void main(String[] args) {
        for (String type : new String[] {"ListLRU", "LinkedLRU"}) {
            for (int capacity : new int[] {1000, 4000}) {
                int[][] calls = workload(capacity, 100000);
                long start = System.nanoTime();
                Cache cache = type.equals("ListLRU") ? new ListLRU(capacity) : new LinkedLRU(capacity);
                int hits = 0;
                for (int[] c : calls) {
                    if (c[0] == 1) cache.put(c[1], c[1]);
                    else if (cache.get(c[1]) != -1) hits++;
                }
                long ms = (System.nanoTime() - start) / 1000000;
                System.out.printf("%-9s capacity %d: %d hits in %d ms%n", type, capacity, hits, ms);
            }
        }
    }
}

// ListLRU   capacity 1000: 32678 hits in 95 ms
// ListLRU   capacity 4000: 30947 hits in 164 ms
// LinkedLRU capacity 1000: 32678 hits in 15 ms
// LinkedLRU capacity 4000: 30947 hits in 16 ms

#include <bits/stdc++.h>
using namespace std;

vector<pair<bool, int>> workload(int capacity, int ops) {   // the same calls in every language: one put in three
    long long x = 7;
    vector<pair<bool, int>> calls;
    for (int i = 0; i < ops; i++) {
        x = x * 48271 % 2147483647;
        bool put = x % 3 == 0;
        x = x * 48271 % 2147483647;
        calls.push_back({put, (int) (x % (2LL * capacity))});
    }
    return calls;
}

struct ListLRU {                              // keys in a list, least recent first: every touch searches it
    int capacity;
    vector<int> order;
    unordered_map<int, int> values;

    ListLRU(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = values.find(key);
        if (it == values.end()) return -1;
        order.erase(find(order.begin(), order.end(), key));   // find it, then shift everything after it
        order.push_back(key);
        return it->second;
    }

    void put(int key, int value) {
        if (values.count(key)) {
            order.erase(find(order.begin(), order.end(), key));
        } else if ((int) values.size() == capacity) {
            values.erase(order.front());
            order.erase(order.begin());           // the least recent is first: shift everything left
        }
        order.push_back(key);
        values[key] = value;
    }
};

struct Node {
    int key, value;
    Node *prev = nullptr, *next = nullptr;
};

struct LinkedLRU {                            // a map into a doubly linked list, most recent first
    int capacity;
    unordered_map<int, Node*> nodes;
    Node head{0, 0}, tail{0, 0};

    LinkedLRU(int capacity) : capacity(capacity) { head.next = &tail; tail.prev = &head; }
    ~LinkedLRU() { for (auto& [key, n] : nodes) delete n; }

    void unlink(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void pushFront(Node* n) { n->prev = &head; n->next = head.next; head.next->prev = n; head.next = n; }

    int get(int key) {
        auto it = nodes.find(key);
        if (it == nodes.end()) return -1;
        unlink(it->second);
        pushFront(it->second);
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = nodes.find(key);
        Node* n;
        if (it != nodes.end()) {
            n = it->second;
            n->value = value;
            unlink(n);
        } else {
            if ((int) nodes.size() == capacity) {
                Node* oldest = tail.prev;
                unlink(oldest);
                nodes.erase(oldest->key);
                delete oldest;
            }
            n = new Node{key, value};
            nodes[key] = n;
        }
        pushFront(n);
    }
};

template <class Cache> void timed(const char* name, int capacity) {
    auto calls = workload(capacity, 100000);
    auto start = chrono::steady_clock::now();
    Cache cache(capacity);
    int hits = 0;
    for (auto [put, key] : calls) {
        if (put) cache.put(key, key);
        else if (cache.get(key) != -1) hits++;
    }
    long long ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
    printf("%-9s capacity %d: %d hits in %lld ms\n", name, capacity, hits, ms);
}

int main() {
    for (int capacity : {1000, 4000}) timed<ListLRU>("ListLRU", capacity);
    for (int capacity : {1000, 4000}) timed<LinkedLRU>("LinkedLRU", capacity);
}

// ListLRU   capacity 1000: 32678 hits in 24 ms
// ListLRU   capacity 4000: 30947 hits in 75 ms
// LinkedLRU capacity 1000: 32678 hits in 4 ms
// LinkedLRU capacity 4000: 30947 hits in 4 ms

function workload(capacity, ops) {            // the same calls in every language: one put in three
    let x = 7;
    const calls = [];
    for (let i = 0; i < ops; i++) {
        x = x * 48271 % 2147483647;
        const put = x % 3 === 0;
        x = x * 48271 % 2147483647;
        calls.push([put, x % (2 * capacity)]);
    }
    return calls;
}

class ListLRU {                               // keys in a list, least recent first: every touch searches it
    constructor(capacity) {
        this.capacity = capacity;
        this.order = [];
        this.values = new Map();
    }
    get(key) {
        if (!this.values.has(key)) return -1;
        this.order.splice(this.order.indexOf(key), 1);   // find it, then shift everything after it
        this.order.push(key);
        return this.values.get(key);
    }
    put(key, value) {
        if (this.values.has(key)) this.order.splice(this.order.indexOf(key), 1);
        else if (this.values.size === this.capacity) this.values.delete(this.order.shift());   // shift everything left
        this.order.push(key);
        this.values.set(key, value);
    }
}

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LinkedLRU {                             // a map into a doubly linked list, most recent first
    constructor(capacity) {
        this.capacity = capacity;
        this.nodes = new Map();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }
    pushFront(n) { n.prev = this.head; n.next = this.head.next; this.head.next.prev = n; this.head.next = n; }
    get(key) {
        const n = this.nodes.get(key);
        if (n === undefined) return -1;
        this.unlink(n);
        this.pushFront(n);
        return n.value;
    }
    put(key, value) {
        let n = this.nodes.get(key);
        if (n !== undefined) {
            n.value = value;
            this.unlink(n);
        } else {
            if (this.nodes.size === this.capacity) {
                const oldest = this.tail.prev;
                this.unlink(oldest);
                this.nodes.delete(oldest.key);
            }
            n = new Node(key, value);
            this.nodes.set(key, n);
        }
        this.pushFront(n);
    }
}

for (const Cache of [ListLRU, LinkedLRU]) {
    for (const capacity of [1000, 4000]) {
        const calls = workload(capacity, 100000);
        const start = performance.now();
        const cache = new Cache(capacity);
        let hits = 0;
        for (const [put, key] of calls) {
            if (put) cache.put(key, key);
            else if (cache.get(key) !== -1) hits++;
        }
        const ms = Math.round(performance.now() - start);
        console.log(`${Cache.name.padEnd(9)} capacity ${capacity}: ${hits} hits in ${ms} ms`);
    }
}

// ListLRU   capacity 1000: 32678 hits in 54 ms
// ListLRU   capacity 4000: 30947 hits in 107 ms
// LinkedLRU capacity 1000: 32678 hits in 33 ms
// LinkedLRU capacity 4000: 30947 hits in 36 ms

function workload(capacity: number, ops: number): [boolean, number][] {   // the same calls in every language
    let x = 7;
    const calls: [boolean, number][] = [];
    for (let i = 0; i < ops; i++) {
        x = x * 48271 % 2147483647;
        const put = x % 3 === 0;
        x = x * 48271 % 2147483647;
        calls.push([put, x % (2 * capacity)]);
    }
    return calls;
}

interface Cache {
    get(key: number): number;
    put(key: number, value: number): void;
}

class ListLRU implements Cache {              // keys in a list, least recent first: every touch searches it
    order: number[] = [];
    values = new Map<number, number>();
    constructor(private capacity: number) {}

    get(key: number): number {
        const value = this.values.get(key);
        if (value === undefined) return -1;
        this.order.splice(this.order.indexOf(key), 1);   // find it, then shift everything after it
        this.order.push(key);
        return value;
    }

    put(key: number, value: number): void {
        if (this.values.has(key)) this.order.splice(this.order.indexOf(key), 1);
        else if (this.values.size === this.capacity) this.values.delete(this.order.shift()!);   // shift everything left
        this.order.push(key);
        this.values.set(key, value);
    }
}

class Node {
    prev: Node | null = null;
    next: Node | null = null;
    constructor(public key: number, public value: number) {}
}

class LinkedLRU implements Cache {            // a map into a doubly linked list, most recent first
    nodes = new Map<number, Node>();
    head = new Node(0, 0);
    tail = new Node(0, 0);

    constructor(private capacity: number) {
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    unlink(n: Node): void { n.prev!.next = n.next; n.next!.prev = n.prev; }

    pushFront(n: Node): void { n.prev = this.head; n.next = this.head.next; this.head.next!.prev = n; this.head.next = n; }

    get(key: number): number {
        const n = this.nodes.get(key);
        if (n === undefined) return -1;
        this.unlink(n);
        this.pushFront(n);
        return n.value;
    }

    put(key: number, value: number): void {
        let n = this.nodes.get(key);
        if (n !== undefined) {
            n.value = value;
            this.unlink(n);
        } else {
            if (this.nodes.size === this.capacity) {
                const oldest = this.tail.prev!;
                this.unlink(oldest);
                this.nodes.delete(oldest.key);
            }
            n = new Node(key, value);
            this.nodes.set(key, n);
        }
        this.pushFront(n);
    }
}

const kinds: [string, (capacity: number) => Cache][] = [
    ["ListLRU", c => new ListLRU(c)],
    ["LinkedLRU", c => new LinkedLRU(c)],
];
for (const [name, make] of kinds) {
    for (const capacity of [1000, 4000]) {
        const calls = workload(capacity, 100000);
        const start = performance.now();
        const cache = make(capacity);
        let hits = 0;
        for (const [put, key] of calls) {
            if (put) cache.put(key, key);
            else if (cache.get(key) !== -1) hits++;
        }
        const ms = Math.round(performance.now() - start);
        console.log(`${name.padEnd(9)} capacity ${capacity}: ${hits} hits in ${ms} ms`);
    }
}

// ListLRU   capacity 1000: 32678 hits in 57 ms
// ListLRU   capacity 4000: 30947 hits in 106 ms
// LinkedLRU capacity 1000: 32678 hits in 33 ms
// LinkedLRU capacity 4000: 30947 hits in 47 ms

using System;
using System.Collections.Generic;
using System.Diagnostics;

interface ICache {
    int Get(int key);
    void Put(int key, int value);
}

class ListLRU : ICache {                      // keys in a list, least recent first: every touch searches it
    readonly int capacity;
    readonly List<int> order = new List<int>();
    readonly Dictionary<int, int> values = new Dictionary<int, int>();

    public ListLRU(int capacity) { this.capacity = capacity; }

    public int Get(int key) {
        if (!values.TryGetValue(key, out int value)) return -1;
        order.Remove(key);                     // find it, then shift everything after it
        order.Add(key);
        return value;
    }

    public void Put(int key, int value) {
        if (values.ContainsKey(key)) order.Remove(key);
        else if (values.Count == capacity) {
            values.Remove(order[0]);
            order.RemoveAt(0);                 // the least recent is first: shift everything left
        }
        order.Add(key);
        values[key] = value;
    }
}

class Node {
    public int Key, Value;
    public Node Prev, Next;
    public Node(int key, int value) { Key = key; Value = value; }
}

class LinkedLRU : ICache {                    // a map into a doubly linked list, most recent first
    readonly int capacity;
    readonly Dictionary<int, Node> nodes = new Dictionary<int, Node>();
    readonly Node head = new Node(0, 0), tail = new Node(0, 0);

    public LinkedLRU(int capacity) {
        this.capacity = capacity;
        head.Next = tail;
        tail.Prev = head;
    }

    void Unlink(Node n) { n.Prev.Next = n.Next; n.Next.Prev = n.Prev; }

    void PushFront(Node n) { n.Prev = head; n.Next = head.Next; head.Next.Prev = n; head.Next = n; }

    public int Get(int key) {
        if (!nodes.TryGetValue(key, out Node n)) return -1;
        Unlink(n);
        PushFront(n);
        return n.Value;
    }

    public void Put(int key, int value) {
        if (nodes.TryGetValue(key, out Node n)) {
            n.Value = value;
            Unlink(n);
        } else {
            if (nodes.Count == capacity) {
                Node oldest = tail.Prev;
                Unlink(oldest);
                nodes.Remove(oldest.Key);
            }
            n = new Node(key, value);
            nodes[key] = n;
        }
        PushFront(n);
    }
}

class Program {
    static List<(bool put, int key)> Workload(int capacity, int ops) {   // the same calls in every language
        long x = 7;
        var calls = new List<(bool, int)>();
        for (int i = 0; i < ops; i++) {
            x = x * 48271 % 2147483647;
            bool put = x % 3 == 0;
            x = x * 48271 % 2147483647;
            calls.Add((put, (int) (x % (2L * capacity))));
        }
        return calls;
    }

    static void Main() {
        foreach (string type in new[] {"ListLRU", "LinkedLRU"}) {
            foreach (int capacity in new[] {1000, 4000}) {
                var calls = Workload(capacity, 100000);
                var watch = Stopwatch.StartNew();
                ICache cache = type == "ListLRU" ? new ListLRU(capacity) : new LinkedLRU(capacity);
                int hits = 0;
                foreach (var (put, key) in calls) {
                    if (put) cache.Put(key, key);
                    else if (cache.Get(key) != -1) hits++;
                }
                Console.WriteLine($"{type,-9} capacity {capacity}: {hits} hits in {watch.ElapsedMilliseconds} ms");
            }
        }
    }
}

// ListLRU   capacity 1000: 32678 hits in 20 ms
// ListLRU   capacity 4000: 30947 hits in 33 ms
// LinkedLRU capacity 1000: 32678 hits in 5 ms
// LinkedLRU capacity 4000: 30947 hits in 6 ms

package main

import (
	"fmt"
	"time"
)

type call struct {
	put bool
	key int
}

func workload(capacity, ops int) []call { // the same calls in every language: one put in three
	x := int64(7)
	calls := make([]call, ops)
	for i := range calls {
		x = x * 48271 % 2147483647
		put := x%3 == 0
		x = x * 48271 % 2147483647
		calls[i] = call{put, int(x % int64(2*capacity))}
	}
	return calls
}

type Cache interface {
	Get(key int) int
	Put(key, value int)
}

type ListLRU struct { // keys in a list, least recent first: every touch searches it
	capacity int
	order    []int
	values   map[int]int
}

func (c *ListLRU) remove(key int) { // find it, then shift everything after it
	for i, k := range c.order {
		if k == key {
			c.order = append(c.order[:i], c.order[i+1:]...)
			return
		}
	}
}

func (c *ListLRU) Get(key int) int {
	value, ok := c.values[key]
	if !ok {
		return -1
	}
	c.remove(key)
	c.order = append(c.order, key)
	return value
}

func (c *ListLRU) Put(key, value int) {
	if _, ok := c.values[key]; ok {
		c.remove(key)
	} else if len(c.values) == c.capacity {
		delete(c.values, c.order[0])
		c.order = append(c.order[:0], c.order[1:]...) // the least recent is first: shift everything left
	}
	c.order = append(c.order, key)
	c.values[key] = value
}

type Node struct {
	key, value int
	prev, next *Node
}

type LinkedLRU struct { // a map into a doubly linked list, most recent first
	capacity   int
	nodes      map[int]*Node
	head, tail *Node
}

func NewLinkedLRU(capacity int) *LinkedLRU {
	c := &LinkedLRU{capacity: capacity, nodes: map[int]*Node{}, head: &Node{}, tail: &Node{}}
	c.head.next, c.tail.prev = c.tail, c.head
	return c
}

func (c *LinkedLRU) unlink(n *Node) { n.prev.next, n.next.prev = n.next, n.prev }

func (c *LinkedLRU) pushFront(n *Node) {
	n.prev, n.next = c.head, c.head.next
	c.head.next.prev = n
	c.head.next = n
}

func (c *LinkedLRU) Get(key int) int {
	n, ok := c.nodes[key]
	if !ok {
		return -1
	}
	c.unlink(n)
	c.pushFront(n)
	return n.value
}

func (c *LinkedLRU) Put(key, value int) {
	n, ok := c.nodes[key]
	if ok {
		n.value = value
		c.unlink(n)
	} else {
		if len(c.nodes) == c.capacity {
			oldest := c.tail.prev
			c.unlink(oldest)
			delete(c.nodes, oldest.key)
		}
		n = &Node{key: key, value: value}
		c.nodes[key] = n
	}
	c.pushFront(n)
}

func main() {
	for _, kind := range []string{"ListLRU", "LinkedLRU"} {
		for _, capacity := range []int{1000, 4000} {
			calls := workload(capacity, 100000)
			start := time.Now()
			var cache Cache
			if kind == "ListLRU" {
				cache = &ListLRU{capacity: capacity, values: map[int]int{}}
			} else {
				cache = NewLinkedLRU(capacity)
			}
			hits := 0
			for _, c := range calls {
				if c.put {
					cache.Put(c.key, c.key)
				} else if cache.Get(c.key) != -1 {
					hits++
				}
			}
			fmt.Printf("%-9s capacity %d: %d hits in %d ms\n", kind, capacity, hits, time.Since(start).Milliseconds())
		}
	}
}

// ListLRU   capacity 1000: 32678 hits in 18 ms
// ListLRU   capacity 4000: 30947 hits in 52 ms
// LinkedLRU capacity 1000: 32678 hits in 5 ms
// LinkedLRU capacity 4000: 30947 hits in 5 ms

Both caches found the same hits, 32,678 at capacity 1,000 and 30,947 at 4,000, in all seven languages. Four times the capacity made the list 1.6 to 3.1 times slower: 470 then 1,409 ms in Python, 24 then 75 ms in C++. The linked cache stayed level, 41 and 48 ms in Python, 4 ms both times in C++, and at 4,000 it was 2 to 29 times faster.

The list's trouble is the search: to move a key to the end it first has to find it, and that walks the list. The map finds the key's node at once, and the linked list moves a node it already holds in a few pointer writes. Neither structure could do it alone. This lesson is how to design a class like that: write down what each operation must do and how fast, give each need a structure, and join the structures with a shared key.

An LRU cache holding keys 4, 1 and 3, most recent first, as two structures: a map whose entries point at their nodes in a doubly linked list between a head and a tail sentinel. For get(3): 1, the map finds node 3 in one step; 2, the node is unlinked from the back; 3, it is linked in again after the head, so the order becomes 3, 4, 1. Focal line: the map finds the node, the list keeps the order. Title: one key, two structures.

Write the operations down first

Before any code, list the operations the class must offer, and next to each the cost it must meet. Then ask what each one needs, and which structure gives exactly that. For the LRU cache:

Operation	What it needs	Cost	Structure
get(key)	find the key's entry	O(1)	hash map: key → node
get(key)	mark it most recent	O(1)	linked list: unlink, relink at the front
put(key, value)	add or update the entry, mark it most recent	O(1)	the same map and list
put(key, value) when full	find and drop the least recent	O(1)	the list's back, then the map's entry

The map alone has no order; the list alone has to be walked to find a key. Joined, the map's values are the list's nodes, so a lookup lands on the node and the list does the rest. Then one rule holds the two together: every operation updates every structure. The map holds exactly the keys in the list, and each points at its key's node. Almost every bug in these problems is an operation that changed one structure and forgot the other.

Hash maps are Introduction to Hash Tables; doubly linked lists and the sentinel nodes at their ends are Introduction to Linked Lists. This lesson is about joining them.

Delete from an array by moving the last value in

Insert Delete GetRandom O(1) asks for a set that inserts, removes and returns a random member, each in O(1) on average. A hash set inserts and removes in O(1), but it has no k-th element to pick at random. An array has one, any index from 0 to n − 1, but deleting from its middle shifts everything after the hole. Keep both: the values in an array, and a map from each value to its index. To delete, move the array's last value into the hole and pop the end, O(1), and tell the map where that value went. Order is lost, and a set doesn't need it:

import random


class RandomizedSet:
    def __init__(self):
        self.values = []                      # the values, in no order: any index can be picked
        self.where = {}                       # value -> its index in values

    def insert(self, val):
        if val in self.where:
            return False
        self.where[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val):
        if val not in self.where:
            return False
        i, last = self.where.pop(val), self.values.pop()
        if i < len(self.values):              # val wasn't last: the last value moves into its slot
            self.values[i] = last
            self.where[last] = i
        return True

    def get_random(self):
        return self.values[random.randrange(len(self.values))]


def show(s):
    return " ".join(map(str, s.values)) + " | " + " ".join(f"{v}->{i}" for v, i in sorted(s.where.items()))


s = RandomizedSet()
for v in (40, 10, 70, 20):
    s.insert(v)
print("after 4 inserts:", show(s))
print("remove 10:", str(s.remove(10)).lower(), "|", show(s))
print("remove 10 again:", str(s.remove(10)).lower())
print("insert 70 again:", str(s.insert(70)).lower())
counts = {v: 0 for v in s.values}
for _ in range(30000):
    counts[s.get_random()] += 1
print("30000 picks, each value 9000 to 11000 times:", str(all(9000 <= c <= 11000 for c in counts.values())).lower())

# after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
# remove 10: true | 40 20 70 | 20->1 40->0 70->2
# remove 10 again: false
# insert 70 again: false
# 30000 picks, each value 9000 to 11000 times: true

import java.util.*;

public class Main {
    static class RandomizedSet {
        final List<Integer> values = new ArrayList<>();       // the values, in no order: any index can be picked
        final Map<Integer, Integer> where = new HashMap<>();   // value -> its index in values
        final Random rng = new Random();

        boolean insert(int val) {
            if (where.containsKey(val)) return false;
            where.put(val, values.size());
            values.add(val);
            return true;
        }

        boolean remove(int val) {
            Integer i = where.remove(val);
            if (i == null) return false;
            int last = values.remove(values.size() - 1);
            if (i < values.size()) {           // val wasn't last: the last value moves into its slot
                values.set(i, last);
                where.put(last, i);
            }
            return true;
        }

        int getRandom() {
            return values.get(rng.nextInt(values.size()));
        }

        String show() {
            StringJoiner vs = new StringJoiner(" "), ws = new StringJoiner(" ");
            for (int v : values) vs.add(String.valueOf(v));
            for (Map.Entry<Integer, Integer> e : new TreeMap<>(where).entrySet()) ws.add(e.getKey() + "->" + e.getValue());
            return vs + " | " + ws;
        }
    }

    public static void main(String[] args) {
        RandomizedSet s = new RandomizedSet();
        for (int v : new int[] {40, 10, 70, 20}) s.insert(v);
        System.out.println("after 4 inserts: " + s.show());
        System.out.println("remove 10: " + s.remove(10) + " | " + s.show());
        System.out.println("remove 10 again: " + s.remove(10));
        System.out.println("insert 70 again: " + s.insert(70));
        Map<Integer, Integer> counts = new HashMap<>();
        for (int k = 0; k < 30000; k++) counts.merge(s.getRandom(), 1, Integer::sum);
        boolean even = counts.size() == 3;
        for (int c : counts.values()) even &= c >= 9000 && c <= 11000;
        System.out.println("30000 picks, each value 9000 to 11000 times: " + even);
    }
}

// after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
// remove 10: true | 40 20 70 | 20->1 40->0 70->2
// remove 10 again: false
// insert 70 again: false
// 30000 picks, each value 9000 to 11000 times: true

#include <bits/stdc++.h>
using namespace std;

class RandomizedSet {
public:
    vector<int> values;                       // the values, in no order: any index can be picked
    unordered_map<int, int> where;            // value -> its index in values
    mt19937 rng{random_device{}()};

    bool insert(int val) {
        if (where.count(val)) return false;
        where[val] = values.size();
        values.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = where.find(val);
        if (it == where.end()) return false;
        int i = it->second, last = values.back();
        where.erase(it);
        values.pop_back();
        if (i < (int) values.size()) {         // val wasn't last: the last value moves into its slot
            values[i] = last;
            where[last] = i;
        }
        return true;
    }

    int getRandom() {
        return values[uniform_int_distribution<int>(0, (int) values.size() - 1)(rng)];
    }

    string show() {
        string vs, ws;
        for (int v : values) vs += (vs.empty() ? "" : " ") + to_string(v);
        for (auto& [v, i] : map<int, int>(where.begin(), where.end()))
            ws += (ws.empty() ? "" : " ") + to_string(v) + "->" + to_string(i);
        return vs + " | " + ws;
    }
};

string tf(bool b) { return b ? "true" : "false"; }

int main() {
    RandomizedSet s;
    for (int v : {40, 10, 70, 20}) s.insert(v);
    cout << "after 4 inserts: " << s.show() << "\n";
    bool removed = s.remove(10);
    cout << "remove 10: " << tf(removed) << " | " << s.show() << "\n";
    cout << "remove 10 again: " << tf(s.remove(10)) << "\n";
    cout << "insert 70 again: " << tf(s.insert(70)) << "\n";
    map<int, int> counts;
    for (int k = 0; k < 30000; k++) counts[s.getRandom()]++;
    bool even = counts.size() == 3;
    for (auto& [v, c] : counts) even = even && c >= 9000 && c <= 11000;
    cout << "30000 picks, each value 9000 to 11000 times: " << tf(even) << "\n";
}

// after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
// remove 10: true | 40 20 70 | 20->1 40->0 70->2
// remove 10 again: false
// insert 70 again: false
// 30000 picks, each value 9000 to 11000 times: true

class RandomizedSet {
    constructor() {
        this.values = [];                     // the values, in no order: any index can be picked
        this.where = new Map();               // value -> its index in values
    }
    insert(val) {
        if (this.where.has(val)) return false;
        this.where.set(val, this.values.length);
        this.values.push(val);
        return true;
    }
    remove(val) {
        if (!this.where.has(val)) return false;
        const i = this.where.get(val), last = this.values.pop();
        this.where.delete(val);
        if (i < this.values.length) {         // val wasn't last: the last value moves into its slot
            this.values[i] = last;
            this.where.set(last, i);
        }
        return true;
    }
    getRandom() {
        return this.values[Math.floor(Math.random() * this.values.length)];
    }
    show() {
        const where = [...this.where].sort((a, b) => a[0] - b[0]).map(([v, i]) => `${v}->${i}`);
        return this.values.join(" ") + " | " + where.join(" ");
    }
}

const s = new RandomizedSet();
for (const v of [40, 10, 70, 20]) s.insert(v);
console.log("after 4 inserts:", s.show());
console.log("remove 10:", s.remove(10), "|", s.show());
console.log("remove 10 again:", s.remove(10));
console.log("insert 70 again:", s.insert(70));
const counts = new Map();
for (let k = 0; k < 30000; k++) {
    const v = s.getRandom();
    counts.set(v, (counts.get(v) || 0) + 1);
}
const even = counts.size === 3 && [...counts.values()].every(c => c >= 9000 && c <= 11000);
console.log("30000 picks, each value 9000 to 11000 times:", even);

// after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
// remove 10: true | 40 20 70 | 20->1 40->0 70->2
// remove 10 again: false
// insert 70 again: false
// 30000 picks, each value 9000 to 11000 times: true

class RandomizedSet {
    values: number[] = [];                    // the values, in no order: any index can be picked
    where = new Map<number, number>();        // value -> its index in values

    insert(val: number): boolean {
        if (this.where.has(val)) return false;
        this.where.set(val, this.values.length);
        this.values.push(val);
        return true;
    }

    remove(val: number): boolean {
        const i = this.where.get(val);
        if (i === undefined) return false;
        const last = this.values.pop()!;
        this.where.delete(val);
        if (i < this.values.length) {         // val wasn't last: the last value moves into its slot
            this.values[i] = last;
            this.where.set(last, i);
        }
        return true;
    }

    getRandom(): number {
        return this.values[Math.floor(Math.random() * this.values.length)];
    }

    show(): string {
        const where = [...this.where].sort((a, b) => a[0] - b[0]).map(([v, i]) => `${v}->${i}`);
        return this.values.join(" ") + " | " + where.join(" ");
    }
}

const s = new RandomizedSet();
for (const v of [40, 10, 70, 20]) s.insert(v);
console.log("after 4 inserts:", s.show());
console.log("remove 10:", s.remove(10), "|", s.show());
console.log("remove 10 again:", s.remove(10));
console.log("insert 70 again:", s.insert(70));
const counts = new Map<number, number>();
for (let k = 0; k < 30000; k++) {
    const v = s.getRandom();
    counts.set(v, (counts.get(v) ?? 0) + 1);
}
const even = counts.size === 3 && [...counts.values()].every(c => c >= 9000 && c <= 11000);
console.log("30000 picks, each value 9000 to 11000 times:", even);

// after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
// remove 10: true | 40 20 70 | 20->1 40->0 70->2
// remove 10 again: false
// insert 70 again: false
// 30000 picks, each value 9000 to 11000 times: true

using System;
using System.Collections.Generic;
using System.Linq;

class RandomizedSet {
    readonly List<int> values = new List<int>();                       // the values, in no order: any index can be picked
    readonly Dictionary<int, int> where = new Dictionary<int, int>();  // value -> its index in values
    readonly Random rng = new Random();

    public bool Insert(int val) {
        if (where.ContainsKey(val)) return false;
        where[val] = values.Count;
        values.Add(val);
        return true;
    }

    public bool Remove(int val) {
        if (!where.TryGetValue(val, out int i)) return false;
        int last = values[values.Count - 1];
        values.RemoveAt(values.Count - 1);
        where.Remove(val);
        if (i < values.Count) {                // val wasn't last: the last value moves into its slot
            values[i] = last;
            where[last] = i;
        }
        return true;
    }

    public int GetRandom() => values[rng.Next(values.Count)];

    public string Show() =>
        string.Join(" ", values) + " | " + string.Join(" ", where.OrderBy(e => e.Key).Select(e => $"{e.Key}->{e.Value}"));
}

class Program {
    static string Tf(bool b) => b ? "true" : "false";

    static void Main() {
        var s = new RandomizedSet();
        foreach (int v in new[] {40, 10, 70, 20}) s.Insert(v);
        Console.WriteLine("after 4 inserts: " + s.Show());
        Console.WriteLine("remove 10: " + Tf(s.Remove(10)) + " | " + s.Show());
        Console.WriteLine("remove 10 again: " + Tf(s.Remove(10)));
        Console.WriteLine("insert 70 again: " + Tf(s.Insert(70)));
        var counts = new Dictionary<int, int>();
        for (int k = 0; k < 30000; k++) {
            int v = s.GetRandom();
            counts[v] = counts.GetValueOrDefault(v) + 1;
        }
        bool even = counts.Count == 3 && counts.Values.All(c => c >= 9000 && c <= 11000);
        Console.WriteLine("30000 picks, each value 9000 to 11000 times: " + Tf(even));
    }
}

// after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
// remove 10: true | 40 20 70 | 20->1 40->0 70->2
// remove 10 again: false
// insert 70 again: false
// 30000 picks, each value 9000 to 11000 times: true

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"strings"
)

type RandomizedSet struct {
	values []int       // the values, in no order: any index can be picked
	where  map[int]int // value -> its index in values
}

func (s *RandomizedSet) Insert(val int) bool {
	if _, ok := s.where[val]; ok {
		return false
	}
	s.where[val] = len(s.values)
	s.values = append(s.values, val)
	return true
}

func (s *RandomizedSet) Remove(val int) bool {
	i, ok := s.where[val]
	if !ok {
		return false
	}
	last := s.values[len(s.values)-1]
	s.values = s.values[:len(s.values)-1]
	delete(s.where, val)
	if i < len(s.values) { // val wasn't last: the last value moves into its slot
		s.values[i] = last
		s.where[last] = i
	}
	return true
}

func (s *RandomizedSet) GetRandom() int {
	return s.values[rand.Intn(len(s.values))]
}

func (s *RandomizedSet) Show() string {
	vs := []string{}
	for _, v := range s.values {
		vs = append(vs, fmt.Sprint(v))
	}
	keys := []int{}
	for v := range s.where {
		keys = append(keys, v)
	}
	sort.Ints(keys)
	ws := []string{}
	for _, v := range keys {
		ws = append(ws, fmt.Sprintf("%d->%d", v, s.where[v]))
	}
	return strings.Join(vs, " ") + " | " + strings.Join(ws, " ")
}

func main() {
	s := &RandomizedSet{where: map[int]int{}}
	for _, v := range []int{40, 10, 70, 20} {
		s.Insert(v)
	}
	fmt.Println("after 4 inserts:", s.Show())
	removed := s.Remove(10)
	fmt.Println("remove 10:", removed, "|", s.Show())
	fmt.Println("remove 10 again:", s.Remove(10))
	fmt.Println("insert 70 again:", s.Insert(70))
	counts := map[int]int{}
	for k := 0; k < 30000; k++ {
		counts[s.GetRandom()]++
	}
	even := len(counts) == 3
	for _, c := range counts {
		even = even && c >= 9000 && c <= 11000
	}
	fmt.Println("30000 picks, each value 9000 to 11000 times:", even)
}

// after 4 inserts: 40 10 70 20 | 10->1 20->3 40->0 70->2
// remove 10: true | 40 20 70 | 20->1 40->0 70->2
// remove 10 again: false
// insert 70 again: false
// 30000 picks, each value 9000 to 11000 times: true

The array 40, 10, 70, 20 with its map of indexes. Removing 10: 1, the map says 10 is at index 1; 2, the last value, 20, moves into index 1 and the array shrinks to 40, 20, 70; 3, the map's entry for 20 changes from 3 to 1, and 10's entry goes. Focal line: every delete is O(1), since no value after the hole has to shift. Title: swap with the last.

40 20 70 after removing 10: 20 filled its slot, and the map now says 20 → 1. The second remove and the repeated insert return false without touching anything. Every value's index is in the map, so getRandom is one random index into the array, and 30,000 picks gave each of the three values between 9,000 and 11,000 times. Each operation is O(1) on average: a map lookup and a write at a known index or at the end.

A map into a linked list: the LRU cache

LRU Cache is the design above in full. The list runs most recent first, between two sentinels, head and tail, so it's never empty and no move needs a special case. get finds the node through the map, unlinks it and links it in again after head. put updates a node it finds the same way, or makes a new one; when the cache is full, it first unlinks the node before tail, the least recent, and deletes that key from the map. A capacity of 3:

class Node:
    def __init__(self, key, value):
        self.key, self.value, self.prev, self.next = key, value, None, None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}                       # key -> its node in the list
        self.head, self.tail = Node(0, 0), Node(0, 0)   # sentinels: the list is never empty
        self.head.next, self.tail.prev = self.tail, self.head

    def unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def push_front(self, node):               # most recent: right after head
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self.unlink(node)                     # used just now: move it to the front
        self.push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self.unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                oldest = self.tail.prev       # least recent: right before tail
                self.unlink(oldest)
                del self.nodes[oldest.key]    # the map lets go of it too
            node = Node(key, value)
            self.nodes[key] = node
        self.push_front(node)

    def recent_first(self):
        keys, node = [], self.head.next
        while node is not self.tail:
            keys.append(str(node.key))
            node = node.next
        return " ".join(keys)


cache = LRUCache(3)
steps = [("put", 1, 10), ("put", 2, 20), ("put", 3, 30), ("get", 1), ("put", 4, 40),
         ("get", 2), ("get", 3), ("put", 1, 11), ("get", 1)]
for op, key, *value in steps:
    if op == "put":
        cache.put(key, value[0])
        print(f"put({key}, {value[0]}) -> {cache.recent_first()}")
    else:
        got = cache.get(key)
        print(f"get({key}) = {got} -> {cache.recent_first()}")
print("the map holds", *sorted(cache.nodes))

# put(1, 10) -> 1
# put(2, 20) -> 2 1
# put(3, 30) -> 3 2 1
# get(1) = 10 -> 1 3 2
# put(4, 40) -> 4 1 3
# get(2) = -1 -> 4 1 3
# get(3) = 30 -> 3 4 1
# put(1, 11) -> 1 3 4
# get(1) = 11 -> 1 3 4
# the map holds 1 3 4

import java.util.*;

public class Main {
    static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    static class LRUCache {
        final int capacity;
        final Map<Integer, Node> nodes = new HashMap<>();            // key -> its node in the list
        final Node head = new Node(0, 0), tail = new Node(0, 0);     // sentinels: the list is never empty

        LRUCache(int capacity) {
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        void unlink(Node n) {
            n.prev.next = n.next;
            n.next.prev = n.prev;
        }

        void pushFront(Node n) {                 // most recent: right after head
            n.prev = head;
            n.next = head.next;
            head.next.prev = n;
            head.next = n;
        }

        int get(int key) {
            Node n = nodes.get(key);
            if (n == null) return -1;
            unlink(n);                           // used just now: move it to the front
            pushFront(n);
            return n.value;
        }

        void put(int key, int value) {
            Node n = nodes.get(key);
            if (n != null) {
                n.value = value;
                unlink(n);
            } else {
                if (nodes.size() == capacity) {
                    Node oldest = tail.prev;     // least recent: right before tail
                    unlink(oldest);
                    nodes.remove(oldest.key);    // the map lets go of it too
                }
                n = new Node(key, value);
                nodes.put(key, n);
            }
            pushFront(n);
        }

        String recentFirst() {
            StringJoiner keys = new StringJoiner(" ");
            for (Node n = head.next; n != tail; n = n.next) keys.add(String.valueOf(n.key));
            return keys.toString();
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        int[][] steps = {{1, 1, 10}, {1, 2, 20}, {1, 3, 30}, {0, 1}, {1, 4, 40}, {0, 2}, {0, 3}, {1, 1, 11}, {0, 1}};
        for (int[] s : steps) {                  // 1 is a put, 0 a get
            if (s[0] == 1) {
                cache.put(s[1], s[2]);
                System.out.println("put(" + s[1] + ", " + s[2] + ") -> " + cache.recentFirst());
            } else {
                int got = cache.get(s[1]);
                System.out.println("get(" + s[1] + ") = " + got + " -> " + cache.recentFirst());
            }
        }
        StringJoiner held = new StringJoiner(" ");
        for (int key : new TreeSet<>(cache.nodes.keySet())) held.add(String.valueOf(key));
        System.out.println("the map holds " + held);
    }
}

// put(1, 10) -> 1
// put(2, 20) -> 2 1
// put(3, 30) -> 3 2 1
// get(1) = 10 -> 1 3 2
// put(4, 40) -> 4 1 3
// get(2) = -1 -> 4 1 3
// get(3) = 30 -> 3 4 1
// put(1, 11) -> 1 3 4
// get(1) = 11 -> 1 3 4
// the map holds 1 3 4

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key, value;
    Node *prev = nullptr, *next = nullptr;
};

class LRUCache {
public:
    int capacity;
    unordered_map<int, Node*> nodes;          // key -> its node in the list
    Node head{0, 0}, tail{0, 0};              // sentinels: the list is never empty

    LRUCache(int capacity) : capacity(capacity) { head.next = &tail; tail.prev = &head; }
    ~LRUCache() { for (auto& [key, n] : nodes) delete n; }

    void unlink(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }

    void pushFront(Node* n) {                 // most recent: right after head
        n->prev = &head;
        n->next = head.next;
        head.next->prev = n;
        head.next = n;
    }

    int get(int key) {
        auto it = nodes.find(key);
        if (it == nodes.end()) return -1;
        unlink(it->second);                   // used just now: move it to the front
        pushFront(it->second);
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = nodes.find(key);
        Node* n;
        if (it != nodes.end()) {
            n = it->second;
            n->value = value;
            unlink(n);
        } else {
            if ((int) nodes.size() == capacity) {
                Node* oldest = tail.prev;     // least recent: right before tail
                unlink(oldest);
                nodes.erase(oldest->key);     // the map lets go of it too
                delete oldest;
            }
            n = new Node{key, value};
            nodes[key] = n;
        }
        pushFront(n);
    }

    string recentFirst() {
        string keys;
        for (Node* n = head.next; n != &tail; n = n->next) keys += (keys.empty() ? "" : " ") + to_string(n->key);
        return keys;
    }
};

int main() {
    LRUCache cache(3);
    vector<vector<int>> steps = {{1, 1, 10}, {1, 2, 20}, {1, 3, 30}, {0, 1}, {1, 4, 40}, {0, 2}, {0, 3}, {1, 1, 11}, {0, 1}};
    for (auto& s : steps) {                   // 1 is a put, 0 a get
        if (s[0] == 1) {
            cache.put(s[1], s[2]);
            cout << "put(" << s[1] << ", " << s[2] << ") -> " << cache.recentFirst() << "\n";
        } else {
            int got = cache.get(s[1]);
            cout << "get(" << s[1] << ") = " << got << " -> " << cache.recentFirst() << "\n";
        }
    }
    set<int> held;
    for (auto& [key, n] : cache.nodes) held.insert(key);
    cout << "the map holds";
    for (int key : held) cout << " " << key;
    cout << "\n";
}

// put(1, 10) -> 1
// put(2, 20) -> 2 1
// put(3, 30) -> 3 2 1
// get(1) = 10 -> 1 3 2
// put(4, 40) -> 4 1 3
// get(2) = -1 -> 4 1 3
// get(3) = 30 -> 3 4 1
// put(1, 11) -> 1 3 4
// get(1) = 11 -> 1 3 4
// the map holds 1 3 4

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.nodes = new Map();               // key -> its node in the list
        this.head = new Node(0, 0);           // sentinels: the list is never empty
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    unlink(n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    pushFront(n) {                            // most recent: right after head
        n.prev = this.head;
        n.next = this.head.next;
        this.head.next.prev = n;
        this.head.next = n;
    }
    get(key) {
        const n = this.nodes.get(key);
        if (n === undefined) return -1;
        this.unlink(n);                       // used just now: move it to the front
        this.pushFront(n);
        return n.value;
    }
    put(key, value) {
        let n = this.nodes.get(key);
        if (n !== undefined) {
            n.value = value;
            this.unlink(n);
        } else {
            if (this.nodes.size === this.capacity) {
                const oldest = this.tail.prev;   // least recent: right before tail
                this.unlink(oldest);
                this.nodes.delete(oldest.key);   // the map lets go of it too
            }
            n = new Node(key, value);
            this.nodes.set(key, n);
        }
        this.pushFront(n);
    }
    recentFirst() {
        const keys = [];
        for (let n = this.head.next; n !== this.tail; n = n.next) keys.push(n.key);
        return keys.join(" ");
    }
}

const cache = new LRUCache(3);
const steps = [["put", 1, 10], ["put", 2, 20], ["put", 3, 30], ["get", 1], ["put", 4, 40],
               ["get", 2], ["get", 3], ["put", 1, 11], ["get", 1]];
for (const [op, key, value] of steps) {
    if (op === "put") {
        cache.put(key, value);
        console.log(`put(${key}, ${value}) -> ${cache.recentFirst()}`);
    } else {
        const got = cache.get(key);
        console.log(`get(${key}) = ${got} -> ${cache.recentFirst()}`);
    }
}
console.log("the map holds", [...cache.nodes.keys()].sort((a, b) => a - b).join(" "));

// put(1, 10) -> 1
// put(2, 20) -> 2 1
// put(3, 30) -> 3 2 1
// get(1) = 10 -> 1 3 2
// put(4, 40) -> 4 1 3
// get(2) = -1 -> 4 1 3
// get(3) = 30 -> 3 4 1
// put(1, 11) -> 1 3 4
// get(1) = 11 -> 1 3 4
// the map holds 1 3 4

class Node {
    prev: Node | null = null;
    next: Node | null = null;
    constructor(public key: number, public value: number) {}
}

class LRUCache {
    nodes = new Map<number, Node>();          // key -> its node in the list
    head = new Node(0, 0);                    // sentinels: the list is never empty
    tail = new Node(0, 0);

    constructor(private capacity: number) {
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    unlink(n: Node): void {
        n.prev!.next = n.next;
        n.next!.prev = n.prev;
    }

    pushFront(n: Node): void {                // most recent: right after head
        n.prev = this.head;
        n.next = this.head.next;
        this.head.next!.prev = n;
        this.head.next = n;
    }

    get(key: number): number {
        const n = this.nodes.get(key);
        if (n === undefined) return -1;
        this.unlink(n);                       // used just now: move it to the front
        this.pushFront(n);
        return n.value;
    }

    put(key: number, value: number): void {
        let n = this.nodes.get(key);
        if (n !== undefined) {
            n.value = value;
            this.unlink(n);
        } else {
            if (this.nodes.size === this.capacity) {
                const oldest = this.tail.prev!;  // least recent: right before tail
                this.unlink(oldest);
                this.nodes.delete(oldest.key);   // the map lets go of it too
            }
            n = new Node(key, value);
            this.nodes.set(key, n);
        }
        this.pushFront(n);
    }

    recentFirst(): string {
        const keys: number[] = [];
        for (let n = this.head.next; n !== this.tail; n = n!.next) keys.push(n!.key);
        return keys.join(" ");
    }
}

const cache = new LRUCache(3);
const steps: [string, number, number?][] = [["put", 1, 10], ["put", 2, 20], ["put", 3, 30], ["get", 1], ["put", 4, 40],
                                            ["get", 2], ["get", 3], ["put", 1, 11], ["get", 1]];
for (const [op, key, value] of steps) {
    if (op === "put") {
        cache.put(key, value!);
        console.log(`put(${key}, ${value}) -> ${cache.recentFirst()}`);
    } else {
        const got = cache.get(key);
        console.log(`get(${key}) = ${got} -> ${cache.recentFirst()}`);
    }
}
console.log("the map holds", [...cache.nodes.keys()].sort((a, b) => a - b).join(" "));

// put(1, 10) -> 1
// put(2, 20) -> 2 1
// put(3, 30) -> 3 2 1
// get(1) = 10 -> 1 3 2
// put(4, 40) -> 4 1 3
// get(2) = -1 -> 4 1 3
// get(3) = 30 -> 3 4 1
// put(1, 11) -> 1 3 4
// get(1) = 11 -> 1 3 4
// the map holds 1 3 4

using System;
using System.Collections.Generic;
using System.Linq;

class Node {
    public int Key, Value;
    public Node Prev, Next;
    public Node(int key, int value) { Key = key; Value = value; }
}

class LRUCache {
    readonly int capacity;
    public readonly Dictionary<int, Node> Nodes = new Dictionary<int, Node>();   // key -> its node in the list
    readonly Node head = new Node(0, 0), tail = new Node(0, 0);                  // sentinels: the list is never empty

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.Next = tail;
        tail.Prev = head;
    }

    void Unlink(Node n) {
        n.Prev.Next = n.Next;
        n.Next.Prev = n.Prev;
    }

    void PushFront(Node n) {                  // most recent: right after head
        n.Prev = head;
        n.Next = head.Next;
        head.Next.Prev = n;
        head.Next = n;
    }

    public int Get(int key) {
        if (!Nodes.TryGetValue(key, out Node n)) return -1;
        Unlink(n);                            // used just now: move it to the front
        PushFront(n);
        return n.Value;
    }

    public void Put(int key, int value) {
        if (Nodes.TryGetValue(key, out Node n)) {
            n.Value = value;
            Unlink(n);
        } else {
            if (Nodes.Count == capacity) {
                Node oldest = tail.Prev;      // least recent: right before tail
                Unlink(oldest);
                Nodes.Remove(oldest.Key);     // the map lets go of it too
            }
            n = new Node(key, value);
            Nodes[key] = n;
        }
        PushFront(n);
    }

    public string RecentFirst() {
        var keys = new List<int>();
        for (Node n = head.Next; n != tail; n = n.Next) keys.Add(n.Key);
        return string.Join(" ", keys);
    }
}

class Program {
    static void Main() {
        var cache = new LRUCache(3);
        int[][] steps = { new[] {1, 1, 10}, new[] {1, 2, 20}, new[] {1, 3, 30}, new[] {0, 1}, new[] {1, 4, 40},
                          new[] {0, 2}, new[] {0, 3}, new[] {1, 1, 11}, new[] {0, 1} };
        foreach (var s in steps) {            // 1 is a put, 0 a get
            if (s[0] == 1) {
                cache.Put(s[1], s[2]);
                Console.WriteLine($"put({s[1]}, {s[2]}) -> {cache.RecentFirst()}");
            } else {
                int got = cache.Get(s[1]);
                Console.WriteLine($"get({s[1]}) = {got} -> {cache.RecentFirst()}");
            }
        }
        Console.WriteLine("the map holds " + string.Join(" ", cache.Nodes.Keys.OrderBy(k => k)));
    }
}

// put(1, 10) -> 1
// put(2, 20) -> 2 1
// put(3, 30) -> 3 2 1
// get(1) = 10 -> 1 3 2
// put(4, 40) -> 4 1 3
// get(2) = -1 -> 4 1 3
// get(3) = 30 -> 3 4 1
// put(1, 11) -> 1 3 4
// get(1) = 11 -> 1 3 4
// the map holds 1 3 4

package main

import (
	"fmt"
	"sort"
	"strings"
)

type Node struct {
	key, value int
	prev, next *Node
}

type LRUCache struct {
	capacity   int
	nodes      map[int]*Node // key -> its node in the list
	head, tail *Node         // sentinels: the list is never empty
}

func NewLRUCache(capacity int) *LRUCache {
	c := &LRUCache{capacity: capacity, nodes: map[int]*Node{}, head: &Node{}, tail: &Node{}}
	c.head.next, c.tail.prev = c.tail, c.head
	return c
}

func (c *LRUCache) unlink(n *Node) {
	n.prev.next, n.next.prev = n.next, n.prev
}

func (c *LRUCache) pushFront(n *Node) { // most recent: right after head
	n.prev, n.next = c.head, c.head.next
	c.head.next.prev = n
	c.head.next = n
}

func (c *LRUCache) Get(key int) int {
	n, ok := c.nodes[key]
	if !ok {
		return -1
	}
	c.unlink(n) // used just now: move it to the front
	c.pushFront(n)
	return n.value
}

func (c *LRUCache) Put(key, value int) {
	n, ok := c.nodes[key]
	if ok {
		n.value = value
		c.unlink(n)
	} else {
		if len(c.nodes) == c.capacity {
			oldest := c.tail.prev // least recent: right before tail
			c.unlink(oldest)
			delete(c.nodes, oldest.key) // the map lets go of it too
		}
		n = &Node{key: key, value: value}
		c.nodes[key] = n
	}
	c.pushFront(n)
}

func (c *LRUCache) RecentFirst() string {
	keys := []string{}
	for n := c.head.next; n != c.tail; n = n.next {
		keys = append(keys, fmt.Sprint(n.key))
	}
	return strings.Join(keys, " ")
}

func main() {
	cache := NewLRUCache(3)
	steps := [][]int{{1, 1, 10}, {1, 2, 20}, {1, 3, 30}, {0, 1}, {1, 4, 40}, {0, 2}, {0, 3}, {1, 1, 11}, {0, 1}}
	for _, s := range steps { // 1 is a put, 0 a get
		if s[0] == 1 {
			cache.Put(s[1], s[2])
			fmt.Printf("put(%d, %d) -> %s\n", s[1], s[2], cache.RecentFirst())
		} else {
			got := cache.Get(s[1])
			fmt.Printf("get(%d) = %d -> %s\n", s[1], got, cache.RecentFirst())
		}
	}
	held := []int{}
	for key := range cache.nodes {
		held = append(held, key)
	}
	sort.Ints(held)
	fmt.Println("the map holds", strings.Trim(fmt.Sprint(held), "[]"))
}

// put(1, 10) -> 1
// put(2, 20) -> 2 1
// put(3, 30) -> 3 2 1
// get(1) = 10 -> 1 3 2
// put(4, 40) -> 4 1 3
// get(2) = -1 -> 4 1 3
// get(3) = 30 -> 3 4 1
// put(1, 11) -> 1 3 4
// get(1) = 11 -> 1 3 4
// the map holds 1 3 4

get(1) = 10 moved 1 to the front: 1 3 2. Then put(4, 40) found the cache full and evicted the key before tail, 2, so the order became 4 1 3 and get(2) returned −1. put(1, 11) on a key it already holds updated the value and moved it to the front, with nothing evicted, and at the end the map holds 1 3 4, the same keys as the list. Each call is a map lookup and a few pointer writes: O(1), with O(capacity) memory.

Run the LRU Cache. Do the moves yourself: each get and put asks you to find the node, unlink it, relink it at the front and evict from the back. Skip a step and the map points at a node the list no longer has.

Run the LRU Cache: move each node yourself, and see the map left pointing at an evicted node

Buckets by count

Some designs order their keys by how often they're used, not by when. Maximum Frequency Stack pops the most frequent value, and of those the most recent. A heap could keep the most frequent on top, at O(log n) a call. A simpler join is O(1): count each value, and keep one stack per count. A push raises the value's count to c and adds it to stack c; a pop takes from the stack of the highest count:

class FreqStack:
    def __init__(self):
        self.count = {}                       # value -> how many copies are in the stack
        self.stacks = {}                      # count c -> the values that reached c, in push order
        self.top = 0                          # the highest count

    def push(self, val):
        c = self.count.get(val, 0) + 1
        self.count[val] = c
        self.stacks.setdefault(c, []).append(val)
        self.top = max(self.top, c)

    def pop(self):
        val = self.stacks[self.top].pop()     # the most frequent, and of those the most recent
        self.count[val] -= 1
        if not self.stacks[self.top]:
            self.top -= 1
        return val


s = FreqStack()
for v in (4, 6, 4, 6, 4, 9):
    s.push(v)
for c in range(1, s.top + 1):
    print(f"count {c}:", *s.stacks[c])
print("pops:", *(s.pop() for _ in range(6)))

# count 1: 4 6 9
# count 2: 4 6
# count 3: 4
# pops: 4 6 4 9 6 4

import java.util.*;

public class Main {
    static class FreqStack {
        final Map<Integer, Integer> count = new HashMap<>();          // value -> how many copies are in the stack
        final Map<Integer, List<Integer>> stacks = new HashMap<>();   // count c -> the values that reached c, in push order
        int top = 0;                                                   // the highest count

        void push(int val) {
            int c = count.merge(val, 1, Integer::sum);
            stacks.computeIfAbsent(c, k -> new ArrayList<>()).add(val);
            top = Math.max(top, c);
        }

        int pop() {
            List<Integer> stack = stacks.get(top);
            int val = stack.remove(stack.size() - 1);   // the most frequent, and of those the most recent
            count.merge(val, -1, Integer::sum);
            if (stack.isEmpty()) top--;
            return val;
        }
    }

    public static void main(String[] args) {
        FreqStack s = new FreqStack();
        for (int v : new int[] {4, 6, 4, 6, 4, 9}) s.push(v);
        for (int c = 1; c <= s.top; c++) {
            StringJoiner line = new StringJoiner(" ", "count " + c + ": ", "");
            for (int v : s.stacks.get(c)) line.add(String.valueOf(v));
            System.out.println(line);
        }
        StringJoiner pops = new StringJoiner(" ", "pops: ", "");
        for (int k = 0; k < 6; k++) pops.add(String.valueOf(s.pop()));
        System.out.println(pops);
    }
}

// count 1: 4 6 9
// count 2: 4 6
// count 3: 4
// pops: 4 6 4 9 6 4

#include <bits/stdc++.h>
using namespace std;

class FreqStack {
public:
    unordered_map<int, int> count;            // value -> how many copies are in the stack
    unordered_map<int, vector<int>> stacks;   // count c -> the values that reached c, in push order
    int top = 0;                              // the highest count

    void push(int val) {
        int c = ++count[val];
        stacks[c].push_back(val);
        top = max(top, c);
    }

    int pop() {
        int val = stacks[top].back();         // the most frequent, and of those the most recent
        stacks[top].pop_back();
        count[val]--;
        if (stacks[top].empty()) top--;
        return val;
    }
};

int main() {
    FreqStack s;
    for (int v : {4, 6, 4, 6, 4, 9}) s.push(v);
    for (int c = 1; c <= s.top; c++) {
        cout << "count " << c << ":";
        for (int v : s.stacks[c]) cout << " " << v;
        cout << "\n";
    }
    cout << "pops:";
    for (int k = 0; k < 6; k++) cout << " " << s.pop();
    cout << "\n";
}

// count 1: 4 6 9
// count 2: 4 6
// count 3: 4
// pops: 4 6 4 9 6 4

class FreqStack {
    constructor() {
        this.count = new Map();               // value -> how many copies are in the stack
        this.stacks = new Map();              // count c -> the values that reached c, in push order
        this.top = 0;                         // the highest count
    }
    push(val) {
        const c = (this.count.get(val) || 0) + 1;
        this.count.set(val, c);
        if (!this.stacks.has(c)) this.stacks.set(c, []);
        this.stacks.get(c).push(val);
        this.top = Math.max(this.top, c);
    }
    pop() {
        const stack = this.stacks.get(this.top);
        const val = stack.pop();              // the most frequent, and of those the most recent
        this.count.set(val, this.count.get(val) - 1);
        if (stack.length === 0) this.top--;
        return val;
    }
}

const s = new FreqStack();
for (const v of [4, 6, 4, 6, 4, 9]) s.push(v);
for (let c = 1; c <= s.top; c++) console.log(`count ${c}:`, s.stacks.get(c).join(" "));
const pops = [];
for (let k = 0; k < 6; k++) pops.push(s.pop());
console.log("pops:", pops.join(" "));

// count 1: 4 6 9
// count 2: 4 6
// count 3: 4
// pops: 4 6 4 9 6 4

class FreqStack {
    count = new Map<number, number>();        // value -> how many copies are in the stack
    stacks = new Map<number, number[]>();     // count c -> the values that reached c, in push order
    top = 0;                                  // the highest count

    push(val: number): void {
        const c = (this.count.get(val) ?? 0) + 1;
        this.count.set(val, c);
        if (!this.stacks.has(c)) this.stacks.set(c, []);
        this.stacks.get(c)!.push(val);
        this.top = Math.max(this.top, c);
    }

    pop(): number {
        const stack = this.stacks.get(this.top)!;
        const val = stack.pop()!;             // the most frequent, and of those the most recent
        this.count.set(val, this.count.get(val)! - 1);
        if (stack.length === 0) this.top--;
        return val;
    }
}

const s = new FreqStack();
for (const v of [4, 6, 4, 6, 4, 9]) s.push(v);
for (let c = 1; c <= s.top; c++) console.log(`count ${c}:`, s.stacks.get(c)!.join(" "));
const pops: number[] = [];
for (let k = 0; k < 6; k++) pops.push(s.pop());
console.log("pops:", pops.join(" "));

// count 1: 4 6 9
// count 2: 4 6
// count 3: 4
// pops: 4 6 4 9 6 4

using System;
using System.Collections.Generic;

class FreqStack {
    readonly Dictionary<int, int> count = new Dictionary<int, int>();                      // value -> how many copies are in the stack
    public readonly Dictionary<int, List<int>> Stacks = new Dictionary<int, List<int>>();  // count c -> the values that reached c, in push order
    public int Top;                                                                         // the highest count

    public void Push(int val) {
        int c = count.GetValueOrDefault(val) + 1;
        count[val] = c;
        if (!Stacks.ContainsKey(c)) Stacks[c] = new List<int>();
        Stacks[c].Add(val);
        Top = Math.Max(Top, c);
    }

    public int Pop() {
        List<int> stack = Stacks[Top];
        int val = stack[stack.Count - 1];     // the most frequent, and of those the most recent
        stack.RemoveAt(stack.Count - 1);
        count[val]--;
        if (stack.Count == 0) Top--;
        return val;
    }
}

class Program {
    static void Main() {
        var s = new FreqStack();
        foreach (int v in new[] {4, 6, 4, 6, 4, 9}) s.Push(v);
        for (int c = 1; c <= s.Top; c++) Console.WriteLine($"count {c}: " + string.Join(" ", s.Stacks[c]));
        var pops = new List<int>();
        for (int k = 0; k < 6; k++) pops.Add(s.Pop());
        Console.WriteLine("pops: " + string.Join(" ", pops));
    }
}

// count 1: 4 6 9
// count 2: 4 6
// count 3: 4
// pops: 4 6 4 9 6 4

package main

import (
	"fmt"
	"strings"
)

type FreqStack struct {
	count  map[int]int   // value -> how many copies are in the stack
	stacks map[int][]int // count c -> the values that reached c, in push order
	top    int           // the highest count
}

func (s *FreqStack) Push(val int) {
	s.count[val]++
	c := s.count[val]
	s.stacks[c] = append(s.stacks[c], val)
	if c > s.top {
		s.top = c
	}
}

func (s *FreqStack) Pop() int {
	stack := s.stacks[s.top]
	val := stack[len(stack)-1] // the most frequent, and of those the most recent
	s.stacks[s.top] = stack[:len(stack)-1]
	s.count[val]--
	if len(s.stacks[s.top]) == 0 {
		s.top--
	}
	return val
}

func join(xs []int) string {
	return strings.Trim(fmt.Sprint(xs), "[]")
}

func main() {
	s := &FreqStack{count: map[int]int{}, stacks: map[int][]int{}}
	for _, v := range []int{4, 6, 4, 6, 4, 9} {
		s.Push(v)
	}
	for c := 1; c <= s.top; c++ {
		fmt.Printf("count %d: %s\n", c, join(s.stacks[c]))
	}
	pops := []int{}
	for k := 0; k < 6; k++ {
		pops = append(pops, s.Pop())
	}
	fmt.Println("pops:", join(pops))
}

// count 1: 4 6 9
// count 2: 4 6
// count 3: 4
// pops: 4 6 4 9 6 4

After pushing 4, 6, 4, 6, 4, 9 the stacks were 1: 4 6 9, 2: 4 6 and 3: 4, and the pops came out 4 6 4 9 6 4. A value with count 3 sits in stacks 1, 2 and 3 at once, one copy per count it reached, so popping it from the top stack leaves it right where it should be in the one below. When the top stack empties, the highest count drops by one: no count can be skipped, because every value passed through every count on its way up.

All O`one Data Structure and LFU Cache go one step further and keep the counts themselves in a doubly linked list of buckets, in increasing order, with a map from each key to its bucket. A touch moves a key one bucket over, creating the next bucket when it isn't there and dropping a bucket that empties, so the smallest and largest counts are always at the two ends.

All O`one's keys in buckets by count, a doubly linked list in increasing order: count 1 holds c and d, count 2 holds a, count 4 holds b. inc(a): 1, a leaves the count 2 bucket; 2, a new bucket for count 3 is linked in right after it; 3, the empty count 2 bucket is unlinked. The first bucket gives a key with the smallest count, the last a key with the largest. Focal line: a key moves one bucket over, so every step is O(1). Title: buckets by count.

LFU adds one thing: inside each bucket the keys are in recency order, because a tie on the count is broken by evicting the least recent, and it keeps the smallest count, which goes up by one when its bucket empties and back to 1 when a new key arrives.

Six designs, one method

Every problem in this lesson is the same three moves on different needs. Side by side:

Problem	Structures	Joined by	Cost per call
Insert Delete GetRandom O(1)	array + map	value → index	O(1) average
LRU Cache	doubly linked list + map	key → node	O(1)
Maximum Frequency Stack	a stack per count + map	value → count	O(1)
All O`one Data Structure	list of count buckets + map	key → bucket	O(1)
LFU Cache	count buckets, recency inside + map	key → node	O(1)
Max Stack	stack + heap	an id per push	O(log n) amortized

Max Stack is the one that can't reach O(1). It pops the top and also pops the largest value, the top-most of equal ones. A stack alone gives the top; a heap of the same values gives the largest. Give every push an id and put it in both. popMax takes the heap's top and only marks that id as removed in the stack; pop takes the stack's top and marks it in the heap. Each side throws its marked entries away when they reach its top, once each, so every call is O(log n) amortized. It's Introduction to Stacks' min stack with a heap in place of the second stack, and heaps are Introduction to Heaps.

Spotting it

The clues: "design" or "implement the … class", a list of methods to support, and a cost for each, often "O(1) average" or "each in O(1)"; most and least recently used, most and least frequent, a random member, a maximum that can be removed. Then write the operations down and look for a need no single structure meets. Near misses:

A class that is one structure with a twist: Implement Queue using Stacks and the min stack (Introduction to Stacks), Design Circular Queue (Introduction to Queues), Implement Trie (Tries).
Values that change over time and are read at an earlier time or version: Designing with History, the next lesson.
One ordered structure is enough: a top k on a stream is a heap (Top K and the Kth Element).

Mistakes that cost an interview

The evicted key left in the map. The LRU above with one line missing: put unlinks the least recent node and never deletes its key from the map:

class Node:
    def __init__(self, key, value):
        self.key, self.value, self.prev, self.next = key, value, None, None


class LRUCache:
    def __init__(self, capacity):
        self.capacity, self.nodes = capacity, {}
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self.unlink(node)
        self.push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self.unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                self.unlink(self.tail.prev)   # off the list, but the map still holds it
            node = Node(key, value)
            self.nodes[key] = node
        self.push_front(node)

    def recent_first(self):
        keys, node = [], self.head.next
        while node is not self.tail:
            keys.append(str(node.key))
            node = node.next
        return " ".join(keys)


cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.put(3, 3)                               # evicts 1, the least recent
print("get(1) =", cache.get(1), "where the answer is -1")
cache.put(4, 4)
print("recent first:", cache.recent_first(), "|", len(cache.nodes), "keys in a cache of 2")

# get(1) = 1 where the answer is -1
# recent first: 4 1 3 2 | 4 keys in a cache of 2

import java.util.*;

public class Main {
    static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    static class LRUCache {
        final int capacity;
        final Map<Integer, Node> nodes = new HashMap<>();
        final Node head = new Node(0, 0), tail = new Node(0, 0);

        LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; }

        void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }

        void pushFront(Node n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }

        int get(int key) {
            Node n = nodes.get(key);
            if (n == null) return -1;
            unlink(n);
            pushFront(n);
            return n.value;
        }

        void put(int key, int value) {
            Node n = nodes.get(key);
            if (n != null) {
                n.value = value;
                unlink(n);
            } else {
                if (nodes.size() == capacity) unlink(tail.prev);   // off the list, but the map still holds it
                n = new Node(key, value);
                nodes.put(key, n);
            }
            pushFront(n);
        }

        String recentFirst() {
            StringJoiner keys = new StringJoiner(" ");
            for (Node n = head.next; n != tail; n = n.next) keys.add(String.valueOf(n.key));
            return keys.toString();
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);                         // evicts 1, the least recent
        System.out.println("get(1) = " + cache.get(1) + " where the answer is -1");
        cache.put(4, 4);
        System.out.println("recent first: " + cache.recentFirst() + " | " + cache.nodes.size() + " keys in a cache of 2");
    }
}

// get(1) = 1 where the answer is -1
// recent first: 4 1 3 2 | 4 keys in a cache of 2

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key, value;
    Node *prev = nullptr, *next = nullptr;
};

class LRUCache {
public:
    int capacity;
    unordered_map<int, Node*> nodes;
    Node head{0, 0}, tail{0, 0};

    LRUCache(int capacity) : capacity(capacity) { head.next = &tail; tail.prev = &head; }
    ~LRUCache() { for (auto& [key, n] : nodes) delete n; }

    void unlink(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void pushFront(Node* n) { n->prev = &head; n->next = head.next; head.next->prev = n; head.next = n; }

    int get(int key) {
        auto it = nodes.find(key);
        if (it == nodes.end()) return -1;
        unlink(it->second);
        pushFront(it->second);
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = nodes.find(key);
        Node* n;
        if (it != nodes.end()) {
            n = it->second;
            n->value = value;
            unlink(n);
        } else {
            if ((int) nodes.size() == capacity) unlink(tail.prev);   // off the list, but the map still holds it
            n = new Node{key, value};
            nodes[key] = n;
        }
        pushFront(n);
    }

    string recentFirst() {
        string keys;
        for (Node* n = head.next; n != &tail; n = n->next) keys += (keys.empty() ? "" : " ") + to_string(n->key);
        return keys;
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cache.put(3, 3);                          // evicts 1, the least recent
    cout << "get(1) = " << cache.get(1) << " where the answer is -1\n";
    cache.put(4, 4);
    cout << "recent first: " << cache.recentFirst() << " | " << cache.nodes.size() << " keys in a cache of 2\n";
}

// get(1) = 1 where the answer is -1
// recent first: 4 1 3 2 | 4 keys in a cache of 2

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.nodes = new Map();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }
    pushFront(n) { n.prev = this.head; n.next = this.head.next; this.head.next.prev = n; this.head.next = n; }
    get(key) {
        const n = this.nodes.get(key);
        if (n === undefined) return -1;
        this.unlink(n);
        this.pushFront(n);
        return n.value;
    }
    put(key, value) {
        let n = this.nodes.get(key);
        if (n !== undefined) {
            n.value = value;
            this.unlink(n);
        } else {
            if (this.nodes.size === this.capacity) this.unlink(this.tail.prev);   // off the list, but the map still holds it
            n = new Node(key, value);
            this.nodes.set(key, n);
        }
        this.pushFront(n);
    }
    recentFirst() {
        const keys = [];
        for (let n = this.head.next; n !== this.tail; n = n.next) keys.push(n.key);
        return keys.join(" ");
    }
}

const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);                              // evicts 1, the least recent
console.log("get(1) =", cache.get(1), "where the answer is -1");
cache.put(4, 4);
console.log("recent first:", cache.recentFirst(), "|", cache.nodes.size, "keys in a cache of 2");

// get(1) = 1 where the answer is -1
// recent first: 4 1 3 2 | 4 keys in a cache of 2

class Node {
    prev: Node | null = null;
    next: Node | null = null;
    constructor(public key: number, public value: number) {}
}

class LRUCache {
    nodes = new Map<number, Node>();
    head = new Node(0, 0);
    tail = new Node(0, 0);

    constructor(private capacity: number) {
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    unlink(n: Node): void { n.prev!.next = n.next; n.next!.prev = n.prev; }

    pushFront(n: Node): void { n.prev = this.head; n.next = this.head.next; this.head.next!.prev = n; this.head.next = n; }

    get(key: number): number {
        const n = this.nodes.get(key);
        if (n === undefined) return -1;
        this.unlink(n);
        this.pushFront(n);
        return n.value;
    }

    put(key: number, value: number): void {
        let n = this.nodes.get(key);
        if (n !== undefined) {
            n.value = value;
            this.unlink(n);
        } else {
            if (this.nodes.size === this.capacity) this.unlink(this.tail.prev!);   // off the list, but the map still holds it
            n = new Node(key, value);
            this.nodes.set(key, n);
        }
        this.pushFront(n);
    }

    recentFirst(): string {
        const keys: number[] = [];
        for (let n = this.head.next; n !== this.tail; n = n!.next) keys.push(n!.key);
        return keys.join(" ");
    }
}

const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);                              // evicts 1, the least recent
console.log("get(1) =", cache.get(1), "where the answer is -1");
cache.put(4, 4);
console.log("recent first:", cache.recentFirst(), "|", cache.nodes.size, "keys in a cache of 2");

// get(1) = 1 where the answer is -1
// recent first: 4 1 3 2 | 4 keys in a cache of 2

using System;
using System.Collections.Generic;

class Node {
    public int Key, Value;
    public Node Prev, Next;
    public Node(int key, int value) { Key = key; Value = value; }
}

class LRUCache {
    readonly int capacity;
    public readonly Dictionary<int, Node> Nodes = new Dictionary<int, Node>();
    readonly Node head = new Node(0, 0), tail = new Node(0, 0);

    public LRUCache(int capacity) { this.capacity = capacity; head.Next = tail; tail.Prev = head; }

    void Unlink(Node n) { n.Prev.Next = n.Next; n.Next.Prev = n.Prev; }

    void PushFront(Node n) { n.Prev = head; n.Next = head.Next; head.Next.Prev = n; head.Next = n; }

    public int Get(int key) {
        if (!Nodes.TryGetValue(key, out Node n)) return -1;
        Unlink(n);
        PushFront(n);
        return n.Value;
    }

    public void Put(int key, int value) {
        if (Nodes.TryGetValue(key, out Node n)) {
            n.Value = value;
            Unlink(n);
        } else {
            if (Nodes.Count == capacity) Unlink(tail.Prev);   // off the list, but the map still holds it
            n = new Node(key, value);
            Nodes[key] = n;
        }
        PushFront(n);
    }

    public string RecentFirst() {
        var keys = new List<int>();
        for (Node n = head.Next; n != tail; n = n.Next) keys.Add(n.Key);
        return string.Join(" ", keys);
    }
}

class Program {
    static void Main() {
        var cache = new LRUCache(2);
        cache.Put(1, 1);
        cache.Put(2, 2);
        cache.Put(3, 3);                      // evicts 1, the least recent
        Console.WriteLine("get(1) = " + cache.Get(1) + " where the answer is -1");
        cache.Put(4, 4);
        Console.WriteLine("recent first: " + cache.RecentFirst() + " | " + cache.Nodes.Count + " keys in a cache of 2");
    }
}

// get(1) = 1 where the answer is -1
// recent first: 4 1 3 2 | 4 keys in a cache of 2

package main

import (
	"fmt"
	"strings"
)

type Node struct {
	key, value int
	prev, next *Node
}

type LRUCache struct {
	capacity   int
	nodes      map[int]*Node
	head, tail *Node
}

func NewLRUCache(capacity int) *LRUCache {
	c := &LRUCache{capacity: capacity, nodes: map[int]*Node{}, head: &Node{}, tail: &Node{}}
	c.head.next, c.tail.prev = c.tail, c.head
	return c
}

func (c *LRUCache) unlink(n *Node) { n.prev.next, n.next.prev = n.next, n.prev }

func (c *LRUCache) pushFront(n *Node) {
	n.prev, n.next = c.head, c.head.next
	c.head.next.prev = n
	c.head.next = n
}

func (c *LRUCache) Get(key int) int {
	n, ok := c.nodes[key]
	if !ok {
		return -1
	}
	c.unlink(n)
	c.pushFront(n)
	return n.value
}

func (c *LRUCache) Put(key, value int) {
	n, ok := c.nodes[key]
	if ok {
		n.value = value
		c.unlink(n)
	} else {
		if len(c.nodes) == c.capacity {
			c.unlink(c.tail.prev) // off the list, but the map still holds it
		}
		n = &Node{key: key, value: value}
		c.nodes[key] = n
	}
	c.pushFront(n)
}

func (c *LRUCache) RecentFirst() string {
	keys := []string{}
	for n := c.head.next; n != c.tail; n = n.next {
		keys = append(keys, fmt.Sprint(n.key))
	}
	return strings.Join(keys, " ")
}

func main() {
	cache := NewLRUCache(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	cache.Put(3, 3) // evicts 1, the least recent
	fmt.Println("get(1) =", cache.Get(1), "where the answer is -1")
	cache.Put(4, 4)
	fmt.Println("recent first:", cache.RecentFirst(), "|", len(cache.nodes), "keys in a cache of 2")
}

// get(1) = 1 where the answer is -1
// recent first: 4 1 3 2 | 4 keys in a cache of 2

All seven printed get(1) = 1 where the answer is −1: the map still found the evicted node and put it back. Then nothing could ever be evicted again. The map held 3 keys for a capacity of 2, so the check for a full cache, the map's size equal to the capacity, was never true again, and the cache grew without end: 4 1 3 2, 4 keys in a cache of 2. Delete the key in the same step that unlinks its node.

Forgetting where the moved value went. In Insert Delete GetRandom O(1)'s remove, the last value moves into the hole, and the map has to learn its new index. Leave it at the old one, past the end of the array, and the next remove of that value pops whatever is last instead.

A get that doesn't move the key. A get is a use. Returning the value and leaving the node where it is keeps the keys in the order they were put, so the cache throws out a key that's read all the time.

LFU's smallest count. After a key leaves the smallest bucket and the bucket empties, the smallest count goes up by one; a new key brings it back to 1. Miss either and the next eviction looks in an empty bucket.

Check yourself

Quiz

1 / 6

Multiple choice

An LRU cache with capacity 2 runs put(1, 1), put(2, 2), get(1), put(3, 3). Which key does put(3, 3) evict?

Practice

In this section, easy to hard:

LRU Page Replacement: count page faults with the same recency order.
LRU Cache: a map into a doubly linked list.
Insert Delete GetRandom O(1): a map into an array, delete by moving the last value in.
LFU Cache: count buckets, recency inside each, and the smallest count.
Maximum Frequency Stack: one stack per count.
Max Stack: a heap beside the stack, entries removed lazily.
All O`one Data Structure: count buckets with the smallest and largest at the two ends.

Next: Designing with History, where a value is read as it was at an earlier time.