Implementing an LRU Cache with a Hash Table and Doubly Linked List

Two structures, one cache

An LRU cache stores at most a fixed number of key–value pairs. A successful get makes its entry most recently used; updating an existing entry with put does too. A get miss changes nothing. When put adds a new key to a full cache, the least recently used entry must leave.

A hash table can locate a key in expected constant time, but it does not tell us which key was used last. A list can represent recency, but searching that list by key would take linear time. The combination solves both problems: the hash table maps each key directly to its list node.

Watch the problem setup and capacity-two trace before examining the C implementation. The video places its most-recent entry at the right end; our implementation will place it immediately after a dummy head at the left. Either orientation works if used consistently.

The first diagram shows the relationship between the structures. Its hash-map entries hold node addresses, not separate copies of the cached values.

We will use dummy head and tail nodes. They hold no cached data: the first real node is most recently used (MRU), and the last real node is least recently used (LRU). The operation sequence below shows how a get changes that order even though it does not change a value.

State the invariant before changing pointers

The implementation is easier to reason about if you keep three promises in view:

1. Every cached key has exactly one real list node and exactly one hash-table entry pointing to that node.
2. Reading from head toward tail visits real nodes from most to least recently used.
3. The number of real nodes equals size, and size never exceeds capacity.

A node stores its key as well as its value. That matters at eviction: the tail gives us a node, and we need its key to remove the matching hash-table entry before freeing it.

Two small list operations do nearly all the recency work. Given a real node, detach connects its neighbors to each other. Given an unlinked node, push_front inserts it just after the dummy head. Because each real node has both prev and next, neither operation searches the list. Moving a hit to the front reuses the same node, so its hash-table entry remains valid.

The C version below uses separate chaining for collisions. Each node therefore has a third link, hash_next, for its bucket chain. The prev and next fields describe recency; hash_next describes hash collisions. Changing one order does not require changing the other.

Implement get and put in C

Budget 20–25 minutes here. Save this as lru.c. The bucket lookup, initialization, teardown, and tests are provided so you can concentrate on list manipulation and the two cache operations. Replace the four TODO functions before expecting the tests to pass.

The API uses a Boolean result and an output pointer for get: a cached value of -1 must not be mistaken for a miss. put returns false only if allocating a new node fails; in that case, it must leave the existing cache unchanged.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key, value;
    struct Node *prev, *next;  /* recency list */
    struct Node *hash_next;    /* hash bucket chain */
} Node;

typedef struct {
    Node **buckets;
    size_t capacity, size;
    Node head, tail;           /* embedded dummy nodes */
} LRU;

/* Only call when capacity > 0. Unsigned multiplication is well-defined. */
static size_t bucket_index(const LRU *c, int key)
{
    uint32_t mixed = (uint32_t)key * UINT32_C(2654435761);
    return (size_t)mixed % c->capacity;
}

/* Return the address of the link pointing to key, or an empty link. */
static Node **find_slot(LRU *c, int key)
{
    Node **slot = &c->buckets[bucket_index(c, key)];
    while (*slot != NULL && (*slot)->key != key)
        slot = &(*slot)->hash_next;
    return slot;
}

static bool lru_init(LRU *c, size_t capacity)
{
    *c = (LRU){0};
    c->head.next = &c->tail;
    c->tail.prev = &c->head;

    if (capacity == 0)
        return true;
    if (capacity > SIZE_MAX / sizeof(*c->buckets))
        return false;

    c->buckets = calloc(capacity, sizeof(*c->buckets));
    if (c->buckets == NULL)
        return false;

    c->capacity = capacity;
    return true;
}

/* Precondition: n is a real node currently in the recency list. */
static void detach(Node *n)
{
    /* TODO: reconnect both neighbors around n. */
    (void)n;
}

/* Precondition: n is not currently in the recency list. */
static void push_front(LRU *c, Node *n)
{
    /* TODO: insert n between the dummy head and the old first node. */
    (void)c;
    (void)n;
}

/* On a hit, write the value to non-NULL out and mark the node MRU. */
static bool lru_get(LRU *c, int key, int *out)
{
    /* TODO: handle zero capacity and a miss; move a hit to the front. */
    (void)c;
    (void)key;
    (void)out;
    return false;
}

/* Return false on allocation failure without changing the cache. */
static bool lru_put(LRU *c, int key, int value)
{
    /* TODO: update an existing key, or insert a new one.
       If full, remove the LRU node from BOTH structures and free it. */
    (void)c;
    (void)key;
    (void)value;
    return false;
}

static void lru_destroy(LRU *c)
{
    Node *n = c->head.next;
    while (n != &c->tail) {
        Node *next = n->next;
        free(n);
        n = next;
    }
    free(c->buckets);
    *c = (LRU){0};  /* call lru_init before reusing */
}

int main(void)
{
    LRU c;
    int value;

    assert(lru_init(&c, 2));
    assert(lru_put(&c, 1, 10));
    assert(lru_put(&c, 2, 20));
    assert(lru_get(&c, 1, &value) && value == 10);
    assert(lru_put(&c, 3, 30));  /* key 2 is LRU */
    assert(!lru_get(&c, 2, &value));
    assert(lru_put(&c, 1, -1));  /* update also changes recency */
    assert(lru_get(&c, 1, &value) && value == -1);
    assert(lru_put(&c, 4, 40));  /* key 3 is now LRU */
    assert(!lru_get(&c, 3, &value));
    assert(c.size == 2);
    lru_destroy(&c);

    assert(lru_init(&c, 2));
    assert(lru_put(&c, 0, 7));
    assert(lru_put(&c, 2, 8));   /* keys 0 and 2 share a bucket */
    assert(lru_get(&c, 0, &value) && value == 7);
    assert(lru_put(&c, 4, 9));
    assert(!lru_get(&c, 2, &value));
    assert(lru_get(&c, 4, &value) && value == 9);
    lru_destroy(&c);

    assert(lru_init(&c, 1));
    assert(lru_put(&c, -7, 70));
    assert(lru_put(&c, 8, 80));
    assert(!lru_get(&c, -7, &value));
    assert(lru_get(&c, 8, &value) && value == 80);
    lru_destroy(&c);

    assert(lru_init(&c, 0));
    assert(lru_put(&c, 5, 50));  /* valid no-op */
    assert(!lru_get(&c, 5, &value));
    assert(c.size == 0);
    lru_destroy(&c);

    puts("LRU tests passed");
    return 0;
}

Compile with warnings and sanitizers:

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
    -fsanitize=address,undefined lru.c -o lru
./lru

Plan the new-key case carefully. Allocate first, evict second. If allocation fails, no existing entry is lost. Once you evict, do not reuse a pointer into a hash bucket chain that you saved before eviction: it might have pointed into the freed node. The simplest insertion is to compute the new key’s bucket again and insert at its front.

Compare the pointer and ownership decisions

Here are replacements for the four TODO functions. Read the list helpers in assignment order: push_front gives the new node its links to both neighbors before redirecting the neighbors’ links toward it.

static void detach(Node *n)
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->prev = NULL;
    n->next = NULL;
}

static void push_front(LRU *c, Node *n)
{
    n->prev = &c->head;
    n->next = c->head.next;
    n->next->prev = n;
    c->head.next = n;
}

static bool lru_get(LRU *c, int key, int *out)
{
    if (c->capacity == 0)
        return false;

    Node *n = *find_slot(c, key);
    if (n == NULL)
        return false;

    *out = n->value;
    detach(n);
    push_front(c, n);
    return true;
}

static bool lru_put(LRU *c, int key, int value)
{
    if (c->capacity == 0)
        return true;

    Node *n = *find_slot(c, key);
    if (n != NULL) {
        n->value = value;
        detach(n);
        push_front(c, n);
        return true;
    }

    n = malloc(sizeof(*n));
    if (n == NULL)
        return false;
    n->key = key;
    n->value = value;

    if (c->size == c->capacity) {
        Node *victim = c->tail.prev;
        Node **victim_slot = find_slot(c, victim->key);

        assert(*victim_slot == victim);
        *victim_slot = victim->hash_next;
        detach(victim);
        free(victim);
        --c->size;
    }

    size_t index = bucket_index(c, key);
    n->hash_next = c->buckets[index];
    c->buckets[index] = n;
    push_front(c, n);
    ++c->size;
    return true;
}

Notice the distinction between a move and an eviction. On a hit, detach and push_front relocate a live node without changing the hash table or size. On eviction, the victim is removed from its hash bucket and the recency list before free; no hash entry may retain its address. The test with keys 0 and 2 checks more than recency: those keys collide in this capacity-two table, so removing one must preserve the other’s bucket chain.

The list operations take constant time. Hash lookup and removal take expected constant time under a suitably distributed hash function and controlled load, giving expected $O(1)$ get and put, with $O(\text{capacity})$ space. A collision-heavy or adversarial bucket can still require $O(\text{capacity})$ time; “constant time” is not an unconditional worst-case guarantee. This implementation is single-threaded—concurrent cache access would require synchronization, which is the next module’s concern.

Key takeaways

An LRU cache needs two synchronized views of the same entries: hash buckets for key lookup and a doubly linked list for recency. A hit moves an existing node; a new insertion may evict the node before the dummy tail. In C, the critical correctness rule is to remove an evicted node from both structures before freeing it, while ensuring allocation failure does not discard a valid entry.

You’ve now implemented the module’s main data-structure combinations. Next, the course turns to concurrency, where these same pointer and lifetime invariants must hold even when operations overlap.