Overview
An LRU cache combines a hash table for lookup with an ordered list that tracks recent access.
CoreSource checked
LRU Cache
Evicts the least recently used item when capacity is exceeded.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Cache
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
recency orderhash lookupeviction policylinked list
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(capacity)
When to Use
- Use when fast lookup needs recency order.
- Use when the input matches the assumptions behind cache.
When Not to Use
- Avoid when the operation mix does not benefit from the structure's maintenance cost.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Evicts the least recently used item when capacity is exceeded
- Uses recency order and hash lookup to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Eviction rule
evict item with oldest access time
evict item with oldest access timeRemoves the least recently used item when the cache is full.
Pseudocode
- 1.Initialize the storage layout and invariants
- 2.For each update, locate the affected position or node
- 3.Modify pointers, counters, buckets, or summary values
- 4.Repair invariants such as balance, order, or load bounds
- 5.Answer queries from the maintained structure
Canonical Example
- Input
- LRU Cache
- Output
- Stored structure
- Explanation
- LRU Cache applies recency order to produce stored structure.
Implementation Notes
- Test insertion, deletion, lookup, and boundary cases separately.
- Keep the recency order step separate enough to test independently.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- Ignoring update costs can make a structure look faster than it is in practice.
- Test edge cases, not only clean examples.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 5: Initialize the storage layout and invariants
data-structures-mechanismNotes
LRU Cache should be used with the assumptions and tradeoffs of cache in mind.
Sources (2)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for LRU cache organization, recency order maintenance, and hash/list update operations.
Operating Systems: Three Easy Pieces
BookReference for LRU replacement policy, recency-based eviction, and practical cache-management behavior.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesHash Table
LRU caches commonly combine hash-table lookup with an order-maintaining list or queue.
Related Algorithms
Tags
Data StructureCacheHash TableBinary Search Tree