LRU Cache Without a Doubly Linked List

We all think LRU cache means a doubly linked list plus a map. But there is another way to build it, using just a flag and a circular hand. Let's see how.

Whenever I heard “LRU cache”, one picture always came to my mind: a doubly linked list plus a hash map.

The idea is simple. Every node is a linked list node. On every get, if the key is present, we move that node to the head of the list. When the cache is full and we need to insert a new key, we evict the node from the tail, because that is the one which was used the longest time back.

This works fine, and it is the most common way to explain LRU in interviews. But recently I came across another way of doing the same thing, called the Clock algorithm (also called the Second-Chance algorithm). It does not use a doubly linked list at all. It just uses one flag per entry. I found this quite interesting, so let’s go through it.

The core idea

Instead of a list ordered by recency, we keep all the cache entries in a circular array (or circular buffer). Think of it like a clock face, with a “hand” pointing to one of the entries.

Each entry has just one extra bit of information: a used flag (also called a “reference bit”).

• Whenever an entry is accessed (a get or set on it), we set used = true.
• We do not move anything around on access. No shifting, no re-linking. Just flip a flag. That’s it.

How eviction works

The interesting part is eviction. When the cache is full and we need space for a new key, we move the “hand” forward, one entry at a time, and check the used flag of whichever entry it is pointing at:

• If used is true, it means this entry was accessed recently. We give it a “second chance” — we set used = false and move the hand to the next entry.
• If used is false, it means this entry was not accessed since the last time the hand passed over it. So it becomes our eviction candidate. We evict it, put the new key in its place, and move the hand forward.

So basically, the hand keeps sweeping around the circle. The first time it sees an entry, if the flag is set, it just clears the flag and moves on, giving that entry one more chance. If it comes back around a second time and the flag is still not set (meaning nobody used it in between), that entry gets evicted.

This is why it’s called “second chance” — every entry gets one pass where it can save itself by having been used.

Code example

Here is a simple Go implementation to make this concrete:

package main

import "fmt"

type entry struct {
	key   int
	value int
	used  bool
	valid bool // whether this slot currently holds a key
}

type ClockCache struct {
	capacity int
	entries  []entry
	index    map[int]int // key -> position in entries
	hand     int
}

func NewClockCache(capacity int) *ClockCache {
	return &ClockCache{
		capacity: capacity,
		entries:  make([]entry, capacity),
		index:    make(map[int]int),
	}
}

func (c *ClockCache) Get(key int) (int, bool) {
	pos, ok := c.index[key]
	if !ok {
		return 0, false
	}
	c.entries[pos].used = true
	return c.entries[pos].value, true
}

func (c *ClockCache) Put(key int, value int) {
	// if key already exists, just update value and mark used
	if pos, ok := c.index[key]; ok {
		c.entries[pos].value = value
		c.entries[pos].used = true
		return
	}

	pos := c.findSlot()
	c.entries[pos] = entry{key: key, value: value, used: true, valid: true}
	c.index[key] = pos
}

// findSlot runs the clock hand until it finds a slot to evict (or an empty one)
func (c *ClockCache) findSlot() int {
	for {
		e := &c.entries[c.hand]

		if !e.valid {
			pos := c.hand
			c.hand = (c.hand + 1) % c.capacity
			return pos
		}

		if e.used {
			// give it a second chance
			e.used = false
			c.hand = (c.hand + 1) % c.capacity
			continue
		}

		// not used since last sweep, evict this one
		delete(c.index, e.key)
		pos := c.hand
		c.hand = (c.hand + 1) % c.capacity
		return pos
	}
}

func main() {
	cache := NewClockCache(3)

	cache.Put(1, 100)
	cache.Put(2, 200)
	cache.Put(3, 300)

	cache.Get(1) // mark 1 as used
	cache.Get(2) // mark 2 as used

	// cache is full now, key 3 was not used again, so it is the candidate
	cache.Put(4, 400)

	if _, ok := cache.Get(3); !ok {
		fmt.Println("key 3 got evicted, as expected")
	}
}

Notice how the Get method is doing almost nothing — just setting a flag. There is no pointer surgery, no moving nodes around. All the real work happens lazily, only at eviction time, inside findSlot.

The trade-off

Doubly linked list: get is O(1), eviction is O(1).

Clock algorithm: get is O(1) (just a flag flip). Eviction is O(N) — but bounded to at most two sweeps around the circle, since every entry can only get one “second chance” before it’s cleared.

So we are trading a guaranteed O(1) eviction for an even cheaper get. This is worth it when reads massively outnumber evictions (true for a lot of real systems, including OS page replacement). If evictions are frequent, the doubly linked list is the safer bet.