Skip to content
Back to Data StructuresAll lessons

Data Structures

LRU Cache

get and put: O(1) each. This uses a hash map combined with an order-preserving structure, so you never scan to find the oldest entry.

The idea, in plain English

An LRU cache, short for Least Recently Used, is like a small whiteboard with a fixed number of slots. Every time you write or reread something, it moves to the 'freshest' spot. When the board is full and you need to add something new, you erase whatever hasn't been touched for the longest time.

How it works

  1. 1Store key-value pairs in a structure that remembers insertion order, like a Map in JavaScript, or a dict in modern Python.
  2. 2On get(key): if the key exists, move it to the 'most recently used' end before returning its value.
  3. 3On put(key, value): if the cache is full and this key is brand-new, remove whatever sits at the 'least recently used' end first.
  4. 4Add or update the key at the 'most recently used' end.

When you'd use it

Use an LRU cache for database query results, browser tabs, image thumbnails, or any fixed-size cache where you want to keep what's popular and drop what's gone cold.

Common beginner mistakes

  • Remember that a get() also counts as 'using' an item. It must refresh that item's position, not just insert().
  • Don't evict an item on every put(). Only evict when the cache is full and the key is genuinely new.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
get a: 1
get b: -1
get a: 1
get c: 3

See it in motion

Watch the LRU cacheLRU cache · cap 2get and put: O(1) each. This uses a hash map combined with an order-preserving structure, so you never scan to find the oldest entry.

Ready. Most-recent on the left, least-recent on the right. Touching an entry floats it to the front.

0/2
Used
–
LRU (next out)
0/0
Hits/Misses
0
Evictions
Just touched (now MRU)Least recently usedEvicted / miss

Not sure this is the right topic? See the learning paths → or where this leads →