Join Community
Home Events Academy Speakers Organizers Stories Gallery Blog FAQs Join Community
← All courses

The LRU Cache — DSA You’ll Actually Build

🗓 May 31, 2026 • ⏱ 3 min read

Why caching needs a data structure

Phones have limited memory, but you want to avoid re-loading the same image or data. The answer is a cache — but a cache can’t grow forever or the OS kills your app. So you need an eviction policy: when the cache is full, throw something out. The most popular policy is LRU — Least Recently Used: evict whatever hasn’t been used for the longest time. Every major image library (Glide, Coil, Picasso, SDWebImage) uses an LRU cache.

The clever design

An LRU cache must do two things in O(1): look up a value by key, and know the usage order so it can evict the least recent. The elegant solution combines two structures:

  • A hash map — for O(1) lookup by key.
  • A doubly linked list — ordered by recency; most-recent at the front, least-recent at the back.
most recent evict from here K1 K2 K3 K4

How it works

  • get(key) — look it up in the map (O(1)); if found, move its node to the front of the list (just used).
  • put(key, value) — add to the map and the front of the list; if over capacity, remove the node at the back (least recently used) and delete it from the map.

Because the linked list lets you move and remove nodes in O(1), and the map gives O(1) lookup, the whole cache is O(1) per operation — this is why it scales.

You usually don’t build it from scratch

Android gives you LruCache out of the box; iOS has NSCache (which evicts under memory pressure). Knowing the design helps you size and use them well.

// Android's built-in LruCache, sized by memory
val cacheSize = (Runtime.getRuntime().maxMemory() / 1024 / 8).toInt() // 1/8 of heap
val imageCache = object : LruCache<String, Bitmap>(cacheSize) {
    override fun sizeOf(key: String, value: Bitmap) = value.byteCount / 1024
}
imageCache.put(url, bitmap)
val cached = imageCache.get(url)

Multi-level caching (real apps)

Production apps layer caches: a fast memory LRU cache, backed by a slower disk cache, backed by the network. Check memory → disk → network in order. This is a direct application of the structures in this course.

Why this is the perfect DSA lesson for mobile

The LRU cache shows DSA isn’t abstract: combining a hash map and a linked list solves a real, daily mobile problem (image caching) elegantly and efficiently — and it’s a classic interview question too.

Common mistakes

  • An unbounded cache (a plain map that never evicts) → out-of-memory kills.
  • Sizing the cache by item count instead of memory (one huge bitmap blows the budget).
  • Re-implementing LRU when LruCache/NSCache already exist.
Summary: An LRU cache evicts the least-recently-used item when full, achieving O(1) get/put by combining a hash map (lookup) with a doubly linked list (recency order). It powers image caching everywhere; use the built-in LruCache/NSCache, size by memory, and layer memory→disk→network.