How Does an LRU Cache Work?

An LRU cache, short for Least Recently Used cache, stores a limited number of key-value pairs and removes the entry that has gone unused for the longest time when the cache reaches its capacity.

The central rule is simple:

Keep recently accessed entries, and evict the entry that has been ignored the longest.

The rule is simple, but implementing it efficiently requires combining two data structures. A cache must quickly answer two different questions:

1. Where is the value for this key?
2. Which entry was used most recently, and which entry should be evicted next?

A HashMap answers the first question. It maps a key directly to its cache entry and provides expected O(1) lookup. A doubly linked list answers the second question. It stores cache entries in access order and allows an entry to be removed or moved in O(1) time when the cache already has a reference to its node.

Together, these structures support the two primary cache operations efficiently:

• get(key): retrieve the value associated with a key.
• put(key, value): insert a new value or update an existing value.

With the standard design, both operations run in expected O(1) time, while the cache uses O(n) space for n stored entries.

What Does “Least Recently Used” Mean?​

An LRU cache has a fixed capacity. If its capacity is three, it can retain at most three entries after an operation completes. When a fourth distinct entry is added, the cache needs an eviction rule. LRU chooses the entry that was accessed least recently.

Suppose a cache contains three entries, and their access order from oldest to newest is:

A, B, C

A is the least recently used entry, and C is the most recently used. If the cache is full and the program inserts D, the cache evicts A:

Before: A, B, C
After:  B, C, D

The important detail is that recency changes when an entry is accessed, not only when it is inserted. Start again with:

A, B, C

Now perform:

get(A)

A has just been used, so it becomes the most recently used entry:

B, C, A

If the cache is full and D is inserted now, B is evicted rather than A:

C, A, D

Therefore, an LRU cache does not simply remove the oldest inserted item. It removes the item whose most recent access is farthest in the past. A previously old entry can become recent again after a successful get.

The Two Responsibilities of an LRU Cache​

A correct LRU cache must maintain two kinds of information at the same time.

Fast key lookup​

Given a key, the cache should locate its value without scanning every stored entry. A HashMap is designed for this purpose. It maps each key to an associated object, which in this design is a linked-list node.

Access order​

The cache must also maintain the order of recent use. Every successful lookup changes that order: the accessed entry becomes the most recent one. When the cache is full, the least recent entry must be identifiable immediately so it can be evicted.

A HashMap alone does not naturally provide this access order. A linked list can represent the order, but a linked list alone requires a scan to find a key. The standard LRU design combines the two structures so that each handles the job it performs well.

Why One Data Structure Is Not Enough​

Understanding the limitations of individual structures makes the combined design easier to understand.

An array alone​

An array can store entries in recency order. For example, the left side could represent the least recent entry and the right side the most recent entry. Removing an item from one end can be straightforward.

The difficulty is moving an existing item after a get. The implementation must first find the item, which may require scanning the array. It may then need to shift other elements to close the gap and place the accessed item at the recent end. These operations can take O(n) time.

An array can be useful for simpler ordering tasks, but it does not provide the desired constant-time behavior for every LRU operation without additional indexing and movement logic.

A HashMap alone​

A HashMap provides expected O(1) access by key, but a normal HashMap does not by itself identify the least recently used entry. The map can answer whether A exists, but it does not necessarily tell the cache whether A, B, or C was accessed least recently.

The cache would need a separate way to record access order. Without that additional structure, eviction order would either be unavailable or require extra work.

A linked list alone​

A linked list naturally represents order. An entry can be placed at one end when it becomes recent, and the entry at the opposite end can be selected for eviction.

However, finding a node by key requires traversing the list from one end until the key is found. In the worst case, this takes O(n) time. If every get begins with a list scan, the cache no longer has constant-time lookup.

The combined design​

The standard LRU cache uses:

• A HashMap from each key to its linked-list node.
• A doubly linked list containing the nodes in recency order.

The map avoids searching for a key. The node’s previous and next pointers avoid searching for its neighbors when it must be moved or removed. This combination gives the cache direct access to both the requested entry and the eviction candidate.

The Core Representation​

A typical implementation maintains state similar to this:

capacity
cache: HashMap<Key, Node>
head: linked-list boundary
 tail: linked-list boundary

Each real cache node stores at least:

key
value
previous pointer
next pointer

The key is stored both in the HashMap and inside the node. That duplication is intentional. When the least recently used node is evicted, the cache must remove its key from the HashMap. The node itself needs to provide that key so the map deletion can happen directly.

The list is often organized using this convention:

head <-> most recent <-> ... <-> least recent <-> tail

Under this convention:

• A newly inserted node is placed next to head.
• A node returned by a successful get is moved next to head.
• The real node next to tail is the least recently used node.
• When capacity is exceeded, the node next to tail is evicted.

The opposite convention is also valid. An implementation could place the most recent node next to tail and evict next to head. The important requirement is consistency. The insertion, movement, and eviction helpers must all agree about which end represents which meaning.

Sentinel Nodes​

Many LRU implementations use two dummy nodes, also called sentinel nodes, at the ends of the list. These nodes do not represent real cache entries. They mark the boundaries:

head <-> real nodes <-> tail

With sentinels, an empty list still has a stable structure:

head <-> tail

When a real node is inserted at the recent side, it is placed between head and head.next. When the least recent node is removed, it is the node immediately before tail.

Sentinels simplify pointer manipulation because a real node being inserted or removed always has a left neighbor and a right neighbor. Without sentinels, the implementation must handle special cases such as:

• Adding the first real node.
• Removing the only real node.
• Updating head when the first node changes.
• Updating tail when the last node changes.
• Removing a node at either physical end of the list.

Sentinel nodes do not change the algorithmic complexity. Their purpose is to make the linked-list operations more uniform and less error-prone.

The Recency Invariant​

The linked list must always represent the current access order. If the convention is that head is the recent side, then walking from head toward tail should visit entries from most recently used to least recently used.

For example:

head <-> C <-> A <-> B <-> tail

means:

• C is the most recently used entry.
• A was used before C.
• B is the least recently used entry.

A successful get changes this ordering. An insertion also changes it because a new entry is considered recent. Updating an existing key generally changes its position as well because the put operation uses that key.

The exact policy can be defined by an API, but the standard LRU behavior treats successful reads and writes as use. The implementation must apply that rule consistently. If get returns a value but does not update the list, the structure is no longer a true access-ordered LRU cache.

How get Works​

The get operation has two basic cases: the key is missing, or the key is present.

A missing key​

The cache first checks the HashMap. If the key is absent, there is no cache entry to return. The operation reports a miss using an API-specific result such as null or another “not found” value.

The linked list does not change because no existing entry was successfully accessed. The expected work is one HashMap lookup:

get(key):
    if key is not in cache:
        return not_found

A present key​

If the key exists, the map returns a direct reference to its node. The cache then:

1. Reads the node’s value.
2. Removes the node from its current position.
3. Inserts the node at the most recently used position.
4. Returns the value.

For example, consider this list:

head <-> A <-> B <-> C <-> tail

Assume A is most recent and C is least recent. If the operation is get(B), the cache unlinks B:

head <-> A <-> C <-> tail

It then inserts B at the recent side:

head <-> B <-> A <-> C <-> tail

The map still points to the same node for B; the node has simply changed neighbors.

A high-level version of the algorithm is:

get(key):
    if key is not in cache:
        return not_found

    node = cache[key]
    remove_node(node)
    add_to_most_recent_position(node)
    return node.value

The lookup is expected O(1). Removing and reinserting the node changes only a constant number of pointers, so the complete operation is expected O(1).

How put Works​

The put operation must distinguish between an existing key and a new key.

Updating an existing key​

Suppose the cache already contains A, and the operation is:

put(A, 10)

The map finds the existing node. The cache updates its value from the old value to 10, then moves the node to the most recently used position.

It is important not to create a second node for the same key. If two nodes represent A, the map can point to only one of them, while the other remains in the list without a reliable map relationship. That breaks the cache’s invariants and can lead to incorrect eviction behavior.

The operation is conceptually:

if key exists:
    node = cache[key]
    node.value = value
    move node to the recent side

Inserting a new key when space is available​

If the key is not present and the cache has not reached capacity, the cache creates a node, stores it in the map, and inserts it at the most recent side.

Starting from an empty cache:

head <-> tail

After put(A, 1):

head <-> A <-> tail

After put(B, 2):

head <-> B <-> A <-> tail

B is more recent because it was inserted after A.

Inserting when the cache is full​

If the key is new and the cache is already full, the implementation must evict one entry. A common sequence is:

1. Create the new node.
2. Add it to the HashMap.
3. Insert it at the recent side of the list.
4. Check whether the cache exceeds capacity.
5. Remove the least recent node from the list.
6. Remove the evicted node’s key from the map.

For example, suppose the list is:

head <-> C <-> A <-> B <-> tail

Here, B is least recent. After put(D, 4), the new node is recent, and the final list should be:

head <-> D <-> C <-> A <-> tail

The cache must delete B from both representations. Removing only the list node leaves a stale map entry. Removing only the map entry leaves an entry in the list that should no longer participate in recency ordering.

A high-level version is:

put(key, value):
    if key is in cache:
        node = cache[key]
        node.value = value
        remove_node(node)
        add_to_most_recent_position(node)
        return

    node = new Node(key, value)
    cache[key] = node
    add_to_most_recent_position(node)

    if cache size > capacity:
        old_node = least_recent_node()
        remove_node(old_node)
        remove cache[old_node.key]

An implementation may evict before inserting rather than after inserting. Either sequence can work if the capacity condition and map/list updates are consistent.

Removing a Node in O(1) Time​

The doubly linked list is valuable because a node knows both of its neighbors. Suppose the list contains:

previous <-> node <-> next

To remove node, connect its neighbors directly:

previous.next = next
next.previous = previous

The list then becomes:

previous <-> next

No traversal is necessary. The operation touches a constant number of pointers.

After unlinking, an implementation may clear the removed node’s pointers, although the essential algorithmic requirement is that the node is no longer connected to the active list. The map entry must also be deleted when the node is being evicted.

Inserting a Node at the Recent Side​

To insert a node between two existing nodes, call them left and right, the links can be set as follows:

node.previous = left
node.next = right
left.next = node
right.previous = node

For insertion next to the head sentinel:

left = head
right = head.next

For removal of the least recent real node, use the node immediately before the tail sentinel:

node = tail.previous

Small helper methods are useful for keeping this logic centralized:

remove_node(node)
add_to_front(node)
move_to_front(node)
remove_least_recent()

A move_to_front helper can call remove_node followed by add_to_front. Centralizing pointer changes helps prevent one code path from updating next pointers while forgetting previous pointers.

Complexity Analysis​

Let n be the number of entries stored in the cache.

get complexity​

A get operation performs:

• One expected O(1) HashMap lookup.
• A constant number of pointer updates to unlink the node.
• A constant number of pointer updates to reinsert the node.

Therefore:

Expected time: O(1)

The HashMap’s O(1) lookup is an expected bound based on normal hashing assumptions. The linked-list operations are O(1) directly because the map provides the node reference and the node provides its neighbors.

put complexity​

A put operation performs:

• One expected O(1) HashMap lookup.
• Either a value update or a node allocation.
• Constant-time list movement or insertion.
• At most one eviction for the standard fixed-capacity behavior.
• One expected O(1) HashMap deletion if eviction occurs.

Thus:

Expected time: O(1)

Space complexity​

The cache stores one map entry and one linked-list node for each cached key. For n entries:

Space: O(n)

Each node stores a key, a value, and two pointers. The map and list therefore require more memory than a simple collection of values. That additional metadata is what makes direct lookup and access-order updates efficient.

A Complete Walkthrough​

Consider a cache with capacity two. Use the convention that the left side is most recent and the right side is least recent.

Initial state​

List: head <-> tail
Map:  empty

put(A, 1)​

A is not present. Create a node and place it at the recent side:

List: head <-> A <-> tail
Map:  A -> node(A, 1)

put(B, 2)​

B is new, so insert it before A:

List: head <-> B <-> A <-> tail
Map:  B -> node(B, 2)
      A -> node(A, 1)

The cache is full. A is currently least recent.

get(A)​

The map finds A directly. The cache returns 1 and moves A to the recent side:

List: head <-> A <-> B <-> tail

Now B is least recent.

put(C, 3)​

C is new. Insert it at the recent side first:

List: head <-> C <-> A <-> B <-> tail

The cache is temporarily over capacity. The node next to tail, B, is the eviction candidate. Remove it from the list and delete B from the map:

List: head <-> C <-> A <-> tail
Map:  C -> node(C, 3)
      A -> node(A, 1)

The final cache contains A and C.

get(B)​

B is no longer in the map, so this operation is a miss. The list remains unchanged:

List: head <-> C <-> A <-> tail

This sequence demonstrates why both structures are necessary. The HashMap finds A quickly, and the linked list records the fact that accessing A changed the eviction order.

Cache Hits and Misses​

A cache hit occurs when get(key) finds the key. The cache returns the stored value and moves the associated node to the most recent position.

A cache miss occurs when the key is absent. The LRU structure cannot return a cached value, so it reports the absence according to the API’s rules. A larger system may then obtain the value from another source and call put to add it to the cache, but the LRU data structure itself is responsible for storing entries, updating order, and evicting entries.

The usefulness of an LRU policy depends on the access pattern. If recently used data is likely to be requested again, retaining recent entries can improve the chance of future hits. If most entries are accessed only once, recency may provide less benefit. LRU does not know the future; it uses recent access history as a practical signal for deciding what to keep.

Important Invariants​

An LRU cache is correct only when the HashMap and linked list remain synchronized. The following invariants are useful during implementation and debugging.

One active node per key​

Each cached key should correspond to exactly one real linked-list node. Updating an existing key should reuse its current node rather than creating a duplicate.

Every map entry points to a list node​

If the HashMap contains a key, the node referenced by that map entry should be connected to the active linked list.

Every list node has a map entry​

If a real node appears in the list, its key should be present in the HashMap and the map should point back to that same node.

The list contains each entry once​

A traversal from the recent side to the least-recent side should visit every real node exactly once before reaching the boundary. A reverse traversal should visit the same nodes in the opposite order.

The size values agree​

The number of real nodes in the linked list should equal the number of entries in the HashMap. After an operation completes, the number of entries should not exceed the configured capacity.

The ends have the intended meanings​

The recent end must be the location where new or accessed nodes are placed. The opposite end must identify the eviction candidate. Accidentally reversing these meanings can produce a cache that returns correct values for some operations while evicting the wrong key later.

Common Implementation Mistakes​

Forgetting to move a node after get​

A successful get is not merely a read in an LRU cache. It changes recency. If the node stays in its old position, a later insertion may evict an entry that was recently used.

Updating a value without updating recency​

When put receives an existing key, changing the stored value is only part of the operation. The node should also move to the recent side if writes count as use, as they do in the standard design.

Removing an evicted node from only one structure​

Eviction must update both the linked list and the HashMap. A stale map entry can make a later get locate a node that is no longer in the list. A stale list node can make later eviction logic operate on an entry that the map no longer considers active.

Omitting the key from the node​

The eviction candidate is found through the list. To remove its corresponding map entry, the implementation needs the candidate’s key. Storing the key inside every node makes this deletion direct.

Breaking one direction of the list​

Every list mutation must maintain both links. If previous is updated but next is not, forward and reverse traversals can disagree. The list may appear correct in one direction while later operations fail when they rely on the other direction.

Creating duplicate nodes​

The implementation should check the map before allocating a node. If an existing key receives a new node, the old node may remain in the list and create duplicate representations of the same key.

Mishandling capacity​

The capacity rule should be explicit. A capacity of two means that no more than two entries should remain after an operation completes. A capacity of zero means that inserted entries cannot remain in the cache; the implementation must apply an immediate removal or an equivalent consistent behavior.

Testing only returned values​

A flawed LRU cache can return the expected value from a direct lookup while maintaining the wrong access order. Tests must also verify which key is evicted after a sequence of accesses and insertions.

Why Constant-Time Operations Matter​

Suppose a cache stores n entries. If every get scans a linked list or array to find its key, one lookup may inspect many entries. Repeating that work across a large number of requests can become expensive.

The HashMap avoids that search by mapping a key directly to its node. Once the node is known, the doubly linked list avoids traversal during movement because the node already knows its immediate neighbors. The cache can unlink it and place it at the recent end by changing a constant number of pointers.

The same principle applies to eviction. The least recent node is located at a known boundary, so the cache does not search the list for a candidate. It removes that node and uses the node’s stored key to delete the matching map entry.

The important design lesson is that neither component is being used for every responsibility:

• The HashMap handles direct access by key.
• The doubly linked list handles local updates to access order.
• The combination supports efficient lookup, movement, insertion, and eviction.

This is a common data-structure design pattern. When one structure cannot efficiently support all required operations, combine complementary structures and maintain the relationship between them carefully.

Practical Implementation Checklist​

When designing or reviewing an LRU cache, check the following points:

1. Choose one recency convention. Decide which side is most recent and which side is least recent.
2. Map keys to nodes. The map should provide the node reference, not merely a separate value that requires another search.
3. Store key and value in each node. The key is needed to remove an evicted entry from the map.
4. Use a doubly linked list. Both directions are needed to remove an arbitrary known node in O(1) time.
5. Move successful get operations. A returned entry becomes most recent.
6. Move updated entries. An existing key handled by put should become most recent under the standard policy.
7. Insert new entries at the recent side. This ensures new entries are initially treated as recently used.
8. Evict from the opposite side. The least recent node should be identifiable without traversal.
9. Update both structures during eviction. Remove the node from the list and its key from the map.
10. Handle empty and single-entry states. Sentinel nodes can simplify these cases.
11. Define zero-capacity behavior. An entry should not remain stored when the capacity is zero.
12. Keep pointer changes in helper methods. Centralized list operations make consistency easier to verify.
13. Test recency order explicitly. Verify not just returned values but also the identity of the next evicted key.

Useful Test Scenarios​

A practical test suite should exercise both lookup behavior and ordering behavior.

Empty cache​

Call get on an empty cache. It should report a miss and leave both the map and list empty.

First insertion​

Insert one key and verify that exactly one map entry and one real list node exist.

Several insertions​

Insert multiple keys below capacity and verify that the most recently inserted key is at the recent side and the first inserted key is at the least-recent side.

Repeated access​

Insert several keys, access an older key, then insert another key. The accessed key should not be evicted if another entry has been used less recently.

Updating an existing key​

Insert a key, update its value, and verify both that the new value is returned and that the key has moved to the recent side.

Eviction at capacity​

Fill the cache, insert one additional distinct key, and verify that exactly one least-recent entry is removed from both the map and the list.

Accessing an evicted key​

Request a key that was evicted. The cache should report a miss, and the list should not change because no active node was accessed.

Capacity of one​

With capacity one, inserting a new distinct key should replace the previous key. Accessing the current key should update its recency without changing the set of stored keys.

Capacity of zero​

Test the explicitly defined zero-capacity behavior. The cache should not retain an inserted entry.

Bidirectional traversal​

When internal inspection is possible, traverse the list from the recent side and then from the least-recent side. Both traversals should contain the same keys in reverse order, and those keys should match the map’s keys.

Broader Design Lessons​

An LRU cache is a compact example of designing around required operations rather than around a single favorite data structure. Start by listing the operations and their desired costs:

• Find an entry by key.
• Mark an entry as recently used.
• Identify the least recently used entry.
• Remove an arbitrary known entry.
• Insert a new entry.

A HashMap is strong at direct key lookup but does not provide the needed access order. A doubly linked list is strong at order maintenance but does not provide direct key lookup. Combining them gives each operation a suitable mechanism.

The design also demonstrates the cost of maintaining multiple representations. The map and list must agree after every insertion, access, update, and eviction. This synchronization creates implementation responsibilities, but it is what changes potentially linear operations into expected constant-time operations.

Another useful lesson is that policy and storage can be separated conceptually. The map stores the key-to-node relationship. The linked list stores the policy order used by LRU. The cache’s behavior comes from how operations update that order and how eviction selects from it.

For software engineers, the practical approach is:

1. Identify the operations a component must support.
2. Estimate the cost of those operations with one data structure.
3. Add a complementary structure when a different operation needs different access behavior.
4. Define invariants describing how the structures must agree.
5. Test both visible results and internal ordering effects.

Final Summary​

An LRU cache stores a bounded set of key-value pairs and evicts the entry that has been used least recently. Its standard implementation combines:

• A HashMap that maps each key directly to its linked-list node.
• A doubly linked list that stores nodes in recency order.
• A most-recent end where new or accessed entries are placed.
• A least-recent end from which eviction occurs.

For get, the cache looks up the key in the HashMap. On a miss, it returns a not-found result. On a hit, it returns the value and moves the node to the most recent position.

For put, the cache updates and moves an existing node, or creates and inserts a new node. If the insertion exceeds capacity, the cache removes the least recent node from the linked list and deletes its key from the HashMap.

HashMap lookup and deletion are expected O(1), while linked-list movement, insertion, and removal require only a constant number of pointer updates. As a result, both get and put run in expected O(1) time, with O(n) space for n entries.

The essential idea is straightforward: use the HashMap for fast lookup and the doubly linked list for fast access-order maintenance. The two structures complement each other, allowing the cache to retain recent entries, evict old ones, and perform its core operations efficiently.