Course contentsShow
← Computer Science
Lesson 449 of 2,87210. Hash TablesFree lesson

Implementing LRU Cache

Combining hash tables with doubly linked lists to implement Least Recently Used cache with O(1) get and put operations.

Implementing LRU Cache

What you'll learn: You'll discover how to combine hash tables with doubly linked lists to build a Least Recently Used (LRU) cache that achieves blazing-fast O(1) operations.

The Problem

An LRU cache evicts the least recently used item when it reaches capacity. You need both fast lookups (get) and fast updates (put), plus a way to track which item was used longest ago.

Why Neither Structure Alone Works

A hash table gives O(1) lookups but can't efficiently track access order. A doubly linked list maintains order beautifully (most recent at head, least recent at tail) but requires O(n) to find items.

The Hybrid Solution

Combine both structures:

  • Hash table: Maps keys to nodes in the linked list (O(1) lookup)
  • Doubly linked list: Maintains access order (O(1) reordering)

How get(key) Works

  1. Hash table finds the node instantly
  2. Move that node to the list's head (it's now "most recently used")
  3. Return its value

Both steps are O(1) because doubly linked lists allow constant-time removal and insertion when you have the node reference.

How put(key, value) Works

  1. If key exists: update value, move node to head
  2. If key is new:
    • Add to hash table and list head
    • If cache is full, remove tail node from both list and hash table (it's the LRU item)

Analogy: Imagine a stack of papers on your desk. The hash table is your mental index ("The Smith report is 5 sheets down"), and the stack itself is your linked list. Every time you access a paper, you pull it out and put it on top. When the stack is too tall, you discard the bottom sheet.

Key Takeaway: LRU cache achieves O(1) get and put by using a hash table for fast key lookups and a doubly linked list for efficient order maintenance—each structure compensates for the other's weakness.