Skip to content

LRU Cache

Medium ~50 min

What you'll build

An LRUCache class with get(key) and put(key, value) operations, both O(1), that evicts the least recently used entry when the cache exceeds its capacity.

Goals

  • Combine a hash map (for O(1) lookup) with a doubly linked list (for O(1) recency updates)
  • Implement get and put with eviction on overflow
  • Reason about operation complexity
  • Justify design choices in comments

Prerequisites

  • Objects as hash maps
  • Linked list concepts (from project-11)
  • O(1) complexity reasoning

Steps

  1. 1

    Choose your data structures

    Decide how to achieve O(1) get and put. The classic approach: a Map (or object) for key→node lookup, plus a doubly linked list to track access order. Document your choice.

  2. 2

    Define the node and cache skeleton

    Define a doubly linked list node (value, prev, next) and the LRUCache constructor taking a capacity. Initialize the map and the list head/tail sentinels.

  3. 3

    Implement get

    get(key) returns the value if present and moves that node to the front (most recently used). If absent, return -1. State the acceptance criteria: get on a missing key returns -1; get on a present key returns its value and makes it the most recent.

  4. 4

    Implement put with eviction

    put(key, value): if the key exists, update the value and move to front. If new, add to front and increment size. If size exceeds capacity, evict the least recently used (tail) and remove it from the map. Acceptance: after put beyond capacity, the oldest entry is gone.

  5. 5

    Verify with a scenario

    Write a test: cache capacity 2; put(1,1), put(2,2), get(1)→1, put(3,3) (evicts key 2), get(2)→-1, get(3)→3, put(4,4) (evicts key 1), get(1)→-1, get(3)→3, get(4)→4. All assertions must pass.

Try it yourself

What you learned

You combined two data structures to achieve O(1) operations on a real-world abstraction — LRU caches are used in CPU caches, browser caches, Redis, and many databases.

Related Resources

Related Lessons

  • Objects

    The map provides O(1) key lookup.

  • Loops

    Linked list manipulation uses pointer reassignment.

Related Glossary

  • Cache

    A fast store of recently used data.

Related Glossary

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

  • Cache

    A fast store of recently used data.

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to topic