Every language
12 linguagens, copy-ready. One at a time with syntax highlighting, or all inline.
JSJavaScript
// Map preserves insertion order — recency IS position, no second structure:
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
}
get(key) {
if (!this.map.has(key)) return undefined;
const value = this.map.get(key);
this.map.delete(key); // the move-to-front:
this.map.set(key, value); // delete + re-set re-inserts at the END
return value;
}
put(key, value) {
this.map.delete(key); // a plain update refreshes recency too
this.map.set(key, value);
if (this.map.size > this.capacity) {
const oldest = this.map.keys().next().value; // FIRST key = least recent
this.map.delete(oldest);
}
}
}Map iterates in insertion order, so delete + set IS the move-to-front — the whole structure is one Map. The eviction idiom is the classic JS trick: map.keys().next().value yields the first key, which after the delete+set discipline is the least recently used. Skip the delete inside get() and reads no longer refresh recency — the cache silently degrades to FIFO with no error anywhere.
TSTypeScript
class LRUCache<K, V> {
private map = new Map<K, V>();
constructor(readonly capacity: number) {}
get(key: K): V | undefined {
if (!this.map.has(key)) return undefined;
const value = this.map.get(key)!;
this.map.delete(key); // SIDE EFFECT: a "read" mutates the
this.map.set(key, value); // recency order — say so at the signature
return value;
}
put(key: K, value: V): void {
this.map.delete(key); // update refreshes recency, same as insert
this.map.set(key, value);
if (this.map.size > this.capacity) {
const oldest = this.map.keys().next().value as K; // least recent
this.map.delete(oldest);
}
}
}Same Map trick, now typed — and the types HIDE the trap: get(key): V | undefined reads like a pure accessor, yet it mutates recency order (delete + set). Document the side effect on the method; a caller who skips repeat gets 'to be safe' changes which entry gets evicted, and no type error will ever flag it.
GoGo
import "container/list"
type entry struct {
key string
value any
}
type LRUCache struct {
capacity int
ll *list.List // front = most recent
items map[string]*list.Element // key → node, both directions O(1)
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{capacity: capacity, ll: list.New(), items: make(map[string]*list.Element)}
}
func (c *LRUCache) Get(key string) (any, bool) {
el, ok := c.items[key]
if !ok {
return nil, false
}
c.ll.MoveToFront(el) // the O(1) dance: a hit MOVES — recency on get AND set
return el.Value.(*entry).value, true
}
func (c *LRUCache) Put(key string, value any) {
if el, ok := c.items[key]; ok {
el.Value.(*entry).value = value
c.ll.MoveToFront(el)
return
}
el := c.ll.PushFront(&entry{key, value})
c.items[key] = el
if c.ll.Len() > c.capacity {
oldest := c.ll.Back() // back() is the victim
c.ll.Remove(oldest)
delete(c.items, oldest.Value.(*entry).key)
}
}This IS the textbook pair made explicit: container/list for order plus map[string]*list.Element so key→node is O(1) — the pointer is stored in the map value, the entry rides in Element.Value. The dance: MoveToFront on hit, PushFront on insert, Back() is the eviction victim, and the map needs its own delete — the list knows nothing about keys. Production takes hashicorp/golang-lru (or ristretto); container/list is the teaching version.
RsRust
// no ordered-map in std — the lru crate IS the answer (LinkedHashMap inside):
use lru::LruCache;
use std::num::NonZeroUsize;
let mut cache: LruCache<&str, i32> = LruCache::new(NonZeroUsize::new(3).unwrap());
cache.put("a", 1);
cache.put("b", 2);
assert_eq!(cache.get("a"), Some(&1)); // "a" touched — now the most recent
cache.put("c", 3);
assert_eq!(cache.put("d", 4), Some(2)); // full: evicts "b", NOT "a"
// minimal std-only shape, honest about its bounds: HashMap<K, V> for lookup
// + VecDeque<K> for recency — O(1) put and evict, but moving a hit to the
// front is an O(n) deque scan. Fine for tiny caches; wrong for hot ones.Hand-rolling the real O(1) structure in pure std means hashbrown + your own intrusive doubly-linked nodes — real code takes the lru crate, a LinkedHashMap with both halves of the pair done right (get returns Option<&V>; put returns the evicted Option<V>). Note the signature honesty: get takes &mut self, because refreshing recency is a mutation — the borrow checker makes the touch-on-read trap impossible to hide, where every other language here smuggles it into a 'read'.
PHPPHP
function lruGet(array &$cache, string $key): mixed
{
if (!array_key_exists($key, $cache)) {
return null;
}
$value = $cache[$key];
unset($cache[$key]); // the move-to-end: PHP arrays preserve
$cache[$key] = $value; // insertion order, so unset+reassign IS it
return $value;
}
function lruPut(array &$cache, string $key, mixed $value, int $capacity): void
{
unset($cache[$key]); // refresh on update, same as insert
$cache[$key] = $value;
if (count($cache) > $capacity) {
$oldest = array_key_first($cache); // PHP 7.3+ — first = least recent
unset($cache[$oldest]);
}
}A PHP array IS an ordered map — insertion order survives everything except sort(), so the same unset + reassign trick as JS works unchanged. array_key_first() (PHP 7.3+) is the eviction pointer: the first key is the least recently used. The pre-7.3 idiom — reset(array_keys($cache)) — rewinds the internal array pointer for no reason; use the built-in.
PyPython
import functools
# the stdlib answer for memoization — bounded, thread-safe, measurable:
@functools.lru_cache(maxsize=128)
def fib(n: int) -> int:
return n if n < 2 else fib(n - 1) + fib(n - 2)
fib(90) # instant; fib.cache_info() shows hits/misses/size
# the manual structure, when the cache IS the product:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data: OrderedDict = OrderedDict()
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key) # recency on READ — the trap
return self.data[key]
def put(self, key, value):
self.data[key] = value # insert or update
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False) # evict the FRONT = least recent@lru_cache IS the stdlib answer for memoization — maxsize bounds it and cache_info() proves the hit rate; reach for OrderedDict only when the cache is the product. The line people forget is move_to_end on every get: skip it and popitem(last=False) evicts in insertion order — a FIFO wearing an LRU's name. And do not confuse it with functools.cache, which is maxsize=None: unbounded.
C#C#
using System.Collections.Generic;
class LRUCache<K, V> where K : notnull
{
private readonly int _capacity;
private readonly Dictionary<K, LinkedListNode<(K key, V value)>> _map = new();
private readonly LinkedList<(K key, V value)> _order = new(); // first = most recent
public LRUCache(int capacity) => _capacity = capacity;
public V? Get(K key)
{
if (!_map.TryGetValue(key, out var node)) return default; // miss
_order.Remove(node); // O(1): the node knows its neighbors
_order.AddFirst(node); // touch-on-read: a GET moves to front
return node.Value.value;
}
public void Put(K key, V value)
{
if (_map.TryGetValue(key, out var node)) // the get-or-create shape
{
node.Value = (key, value);
_order.Remove(node);
_order.AddFirst(node);
return;
}
var fresh = _order.AddFirst((key, value));
_map[key] = fresh;
if (_map.Count > _capacity)
{
var eldest = _order.Last!;
_order.RemoveLast(); // back of the list = victim
_map.Remove(eldest.Value.key);
}
}
}The explicit pair, like Go: Dictionary for lookup, LinkedList for order — and the VALUE in the dictionary is the LinkedListNode itself, which is what makes _order.Remove(node) O(1); calling _order.Remove(key) instead is a hidden O(n) search. The GetOrCreateValue shape (TryGetValue, else create + link) keeps hit and miss on one path per method. In the framework, Microsoft.Extensions.Caching.Memory with SizeLimit + per-entry SetSize is the production answer — it extends to expiration and composite policies.
JvJava
import java.util.LinkedHashMap;
import java.util.Map;
// accessOrder=true (the 3rd ctor arg) is the WHOLE trick:
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LRUCache(int capacity) {
super(16, 0.75f, true); // initialCapacity, loadFactor, accessOrder
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // true ⇒ LinkedHashMap evicts eldest
}
}
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a"); // "a" touched — "b" is now the eldest
cache.put("c", 3);
cache.put("d", 4); // evicts "b", NOT "a"The third constructor argument is the entire implementation: accessOrder=true makes get() reorder the linked list (touch-on-read for free), and removeEldestEntry is the hook LinkedHashMap calls after every put — return size() > capacity and eviction is done. Pass false or use the 2-arg constructor and you get insertion order, a FIFO with the same class name. Production caches use Caffeine (size-aware eviction, async loading); this is the interview-shaped core.
SwSwift
struct LRUCache<K: Hashable, V> {
private let capacity: Int
private var data: [K: V] = [:]
private var order: [K] = [] // last = most recent
init(capacity: Int) { self.capacity = capacity }
mutating func get(_ key: K) -> V? {
guard let value = data[key] else { return nil }
order.removeAll { $0 == key } // O(n) — the honest cost of Array
order.append(key)
return value
}
mutating func put(_ key: K, _ value: V) {
data[key] = value
order.removeAll { $0 == key }
order.append(key)
if order.count > capacity {
let eldest = order.removeFirst() // O(n) shift; the dict delete is O(1)
data.removeValue(forKey: eldest)
}
}
}Swift Dictionary is unordered — the stdlib has no ordered-map, so recency lives in a parallel Array of keys. The honest price: every get scans the array (removeAll with a predicate is O(n)), fine at dozens of keys, wrong at millions. The real structure is the explicit pair — [K: (value, node)] with class nodes wired into a doubly-linked list — or NSCache when the goal is reacting to memory pressure rather than strict LRU.
KtKotlin
class LRUCache<K, V>(private val capacity: Int) :
LinkedHashMap<K, V>(16, 0.75f, true) { // accessOrder = true
override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>): Boolean =
size > capacity // true ⇒ auto-evict after put
}
val cache = LRUCache<String, Int>(3)
cache["a"] = 1
cache["b"] = 2
check(cache["a"] == 1) // a GET — accessOrder refreshes "a"
cache["c"] = 3
cache["d"] = 4 // evicts "b", not "a"The same JVM LinkedHashMap as Java — the third constructor Boolean is the accessOrder switch in both languages, and removeEldestEntry runs after every put. The singleton shape is an object expression: object : LinkedHashMap<K, V>(16, 0.75f, true) { override fun removeEldestEntry(...) = size > capacity }. Default the flag to false and nothing warns you — the class silently becomes FIFO.
RbRuby
class LRUCache
def initialize(capacity)
@capacity = capacity
@data = {} # Hash preserves insertion order (1.9+)
end
def get(key)
return nil unless @data.key?(key)
value = @data.delete(key) # the move-to-end:
@data[key] = value # delete + re-store, no gem needed
value
end
def put(key, value)
@data.delete(key) # update refreshes recency too
@data[key] = value
@data.shift if @data.size > @capacity # first key = least recent
end
endRuby Hash has preserved insertion order since 1.9 — the delete-then-reassign idiom is the whole move-to-front, and any 'orderedhash' gem is a relic. Hash#shift returns AND removes the oldest pair: the eviction in one call; Hash#first peeks at the next victim without evicting. The old recreate-the-hash trick ({ key => v }.merge(rest)) rebuilds the entire hash per touch — delete + reassign does it in place.
ZigZig
const std = @import("std");
const Entry = struct {
key: []const u8,
value: i32,
link: std.DoublyLinkedList.Node = .{}, // intrusive: the node lives IN the entry
};
const LRUCache = struct {
capacity: usize,
order: std.DoublyLinkedList, // front = most recent, back = victim
index: std.StringHashMap(*Entry), // key → entry, O(1) both ways
allocator: std.mem.Allocator,
fn init(allocator: std.mem.Allocator, capacity: usize) LRUCache {
return .{ .capacity = capacity, .order = .{}, .allocator = allocator,
.index = std.StringHashMap(*Entry).init(allocator) };
}
fn get(self: *LRUCache, key: []const u8) ?i32 {
const entry = self.index.get(key) orelse return null;
self.order.remove(&entry.link); // touch-on-read: a hit MOVES
self.order.prepend(&entry.link);
return entry.value;
}
fn put(self: *LRUCache, key: []const u8, value: i32) !void {
if (self.index.get(key)) |entry| {
entry.value = value;
self.order.remove(&entry.link);
self.order.prepend(&entry.link);
return;
}
const entry = try self.allocator.create(Entry);
entry.* = .{ .key = key, .value = value };
self.order.prepend(&entry.link);
try self.index.put(key, entry);
if (self.index.count() > self.capacity) {
const victim_link = self.order.pop().?; // back = least recent
const victim: *Entry = @fieldParentPtr("link", victim_link);
_ = self.index.remove(victim.key);
self.allocator.destroy(victim); // manual heap: FREE the evicted entry
}
}
};std already ships BOTH primitives — StringHashMap for lookup, DoublyLinkedList for order — so the composition is the whole exercise, done with an intrusive Node field inside the entry and @fieldParentPtr to walk link→entry. prepend is move-to-front, pop() takes the back (the victim). Manual memory cuts both ways: create on insert, and destroy on evict — leak the destroy and the cache's memory grows exactly like its miss rate.