Building an LRU Cache in Python: The Data Structure Behind Every Cache

A cache is a small box holding copies of expensive things: rows you already fetched from a database, files you already read from disk, results you already computed. Filling it is easy. The whole difficulty is what happens when it is full — something has to go, and throwing out the wrong thing means paying for the expensive work again.

Least recently used, or LRU, is the policy almost everything settles on: discard the entry nobody has touched for the longest. It is a bet that the recent past predicts the near future, and on real workloads that bet pays.

The interesting part is the implementation, because both of the obvious data structures fail. A dict finds a value instantly but has no idea which key is stalest. A list kept in recency order knows exactly which key is stalest, but finding an entry inside it means walking it. What makes every operation O(1) is a hash map and a doubly linked list wired together — and once you have seen it you will recognise it inside CPython's functools.lru_cache, inside MySQL's buffer pool, and behind the eviction setting of every cache server you have configured.

The idea

An LRU cache has a fixed capacity — say three entries — and two operations.

• get(key) returns the stored value, or a default if the key is not there.
• put(key, value) stores a value, evicting the least recently used entry first if the key is new and the cache is already full.

Both operations count as a use. That single rule is what makes the structure work: after a successful get or any put, that key becomes the most recently used one, and every entry that was ahead of it slides one place closer to the exit. Entries that were already colder than it do not move.

So on every operation the cache must answer three questions, and it must answer all three in constant time or the whole thing is pointless:

1. Is this key present, and what is its value?
2. Given a key that is present, mark it as the most recently used.
3. Which entry is the least recently used, so it can be dropped?

Why a dict on its own fails

A Python dict answers question 1 perfectly and question 3 not at all, because a dict has no notion of "oldest use".

You can bolt one on: store a counter alongside each value and bump it on every access, which handles question 2 as well. But question 3 then means finding the smallest counter, and with no ordering maintained anywhere that is a scan of every entry. One eviction from a 100,000-entry cache reads 100,000 counters.

Why a list in recency order fails

The opposite approach is a plain list of keys, most recently used first. Question 3 becomes free — the answer is the last element. Questions 1 and 2 become expensive, because to move a key to the front you first have to find it, and finding a value in a list means comparing your way along it.

It gets worse than the scan. Deleting from position i in a Python list shifts every later element one slot left, and insert(0, key) shifts every single element one slot right. One read of one key costs three separate linear passes. The code below counts the scan alone: a thousand reads of a thousand-entry cache examine a million list positions, and that total grows with the square of the cache size.

The two structures together

Look again at what each question needs. Question 1 is a hash map's entire job — that is what dicts are for.

Question 2 is "remove this item from the middle of an ordered sequence and reattach it at the front". In an array-backed list that is O(n) because of the shifting. In a doubly linked list it is a handful of pointer assignments, because each node holds a reference to both of its neighbours and can splice itself out without anyone searching for it. The catch is the phrase if you already hold the node. Question 3 is "give me the last node", which the same list answers immediately as long as you keep a reference to the end.

The trick that joins them: the hash map does not store the values, it stores the nodes.

One dict lookup turns a key into the exact node, and from that node the list operations are pure pointer work with no searching at all. The dict never stores any ordering. The list is never searched. Each structure does only the one thing it is fast at, and together they cover all three questions in constant time.

The sentinels

One more piece separates clean code from a nest of special cases.

A linked list normally forces you to ask, on every insert and removal: is this the first node? The last? The only one? Is the list empty? Each answer needs different pointer updates, and each is a place to get it wrong.

The fix is to permanently allocate two nodes holding no data — a head sentinel and a tail sentinel — and keep every real node strictly between them. Now every real node has a neighbour on both sides, the first node is always head.next, the last is always tail.prev, and an empty cache is just the two sentinels pointing at each other. Every branch disappears. Two nodes of wasted memory buy you code with no edge cases in it.

Watching it work

Take a cache with capacity 3 and run seven operations through it. The rightmost column is the recency list, most recently used first — exactly what the linked list holds.

Two rows are worth slowing down on.

get("A") moves A from the back to the front. Before the call the list is C B A, so A is the last real node and its neighbours are B and the tail sentinel. The unlink is two assignments: B's next now points at the tail sentinel, and the tail sentinel's prev now points at B. The relink is four more: A's prev becomes the head sentinel, A's next becomes C, the head sentinel's next becomes A, and C's prev becomes A. B and C never move in memory. Only pointers change.

put("D", 4) evicts B. The cache already holds three entries, so something must go, and the coldest entry is whatever sits immediately before the tail sentinel — B, untouched since it was inserted. Notice that get("A") on the previous line is what saved A: without that read, A would have been at the back and A would have gone instead. That is the entire policy, in one step.

The last two rows cover the remaining cases. get("B") misses, because B was evicted, and a miss changes nothing — you cannot promote an entry that is not there. get("C") hits and pulls C to the front, so D and A each slide one place towards eviction.

The code

Start with the version that is correct but wrong: a dict for the values, a list for the order.

class NaiveLRUCache:
    """An LRU cache built from a dict plus a list kept in recency order.

    It behaves correctly. It is still the wrong design, and the counter
    attached to it shows exactly why.
    """

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.values: dict = {}
        self.recency: list = []  # most recently used first, coldest last
        self.scanned = 0  # list positions examined, so the cost is visible

    def get(self, key, default=None):
        if key not in self.values:
            return default
        position = self.recency.index(key)  # a linear scan — this is the problem
        self.scanned += position + 1
        del self.recency[position]  # shifts every later element one step left
        self.recency.insert(0, key)  # shifts every element one step right
        return self.values[key]

    def put(self, key, value) -> None:
        if key in self.values:
            self.get(key)  # already present, so this is just a recency refresh
        else:
            if len(self.values) == self.capacity:
                del self.values[self.recency.pop()]  # the tail is the coldest key
            self.recency.insert(0, key)
        self.values[key] = value


naive = NaiveLRUCache(capacity=1000)
for number in range(1000):
    naive.put(number, number * number)

# Read every key once, in order. The puts left key 0 at the far end, and each
# read drags the next key you are about to ask for to the far end in turn, so
# every read is a full-length scan.
for number in range(1000):
    naive.get(number)

print(f"1,000 reads of a 1,000-entry cache: {naive.scanned:,} list positions examined")

1,000 reads of a 1,000-entry cache: 1,000,000 list positions examined

A million positions examined for a thousand reads, and that is only the index scan — the del and the insert(0, ...) each shift up to a thousand more pointers on top. Multiply the cache size by a thousand and the per-read cost multiplies by a thousand too.

Here is the real thing. It is longer, and every extra line buys constant time.

from collections.abc import Hashable
from typing import Any


class _Node:
    """One cache entry, and its two neighbours in the recency list.

    The key is stored on the node as well as in the dict. Without it, finding
    the coldest node would not tell you which dict entry to delete.
    """

    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key: Any = None, value: Any = None) -> None:
        self.key = key
        self.value = value
        self.prev: "_Node | None" = None
        self.next: "_Node | None" = None


class LRUCache:
    """A fixed-capacity cache that discards the least recently used entry.

    Two structures kept in step:

    * a dict mapping each key to its node, for O(1) lookup;
    * a doubly linked list of those nodes in recency order, most recently
      used first, for O(1) reordering and O(1) eviction.

    Both get and put count as a use and move the entry to the front.
    """

    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self.capacity = capacity
        self.entries: dict = {}
        # Two sentinel nodes holding no data. They exist so that every real
        # node always has a neighbour on both sides, which removes every
        # "is this the first or last node?" branch from the methods below.
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node: _Node) -> None:
        """Detach a node by making its two neighbours point past it."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _link_front(self, node: _Node) -> None:
        """Insert a node between the head sentinel and the current first node."""
        first = self.head.next
        node.prev = self.head
        node.next = first
        self.head.next = node
        first.prev = node

    def get(self, key: Hashable, default: Any = None) -> Any:
        node = self.entries.get(key)
        if node is None:
            return default
        self._unlink(node)
        self._link_front(node)
        return node.value

    def put(self, key: Hashable, value: Any) -> None:
        node = self.entries.get(key)
        if node is not None:
            # Overwriting an existing key is a use, not an insertion, so
            # nothing is evicted and the size does not change.
            node.value = value
            self._unlink(node)
            self._link_front(node)
            return
        if len(self.entries) == self.capacity:
            coldest = self.tail.prev  # the node immediately before the tail sentinel
            self._unlink(coldest)
            del self.entries[coldest.key]
        node = _Node(key, value)
        self.entries[key] = node
        self._link_front(node)

    def __len__(self) -> int:
        return len(self.entries)

    def __contains__(self, key: Hashable) -> bool:
        return key in self.entries  # deliberately not a use: no reordering

    def keys_mru_first(self) -> list:
        """Walk the list, for demonstrations. Real callers never need this."""
        keys, node = [], self.head.next
        while node is not self.tail:
            keys.append(node.key)
            node = node.next
        return keys


cache = LRUCache(capacity=3)


def show(label: str) -> None:
    print(f"{label:<20} {' '.join(cache.keys_mru_first())}")


for letter, number in [("A", 1), ("B", 2), ("C", 3)]:
    cache.put(letter, number)
    show(f"put {letter}={number}")

show(f"get A -> {cache.get('A')}")
doomed = cache.keys_mru_first()[-1]
cache.put("D", 4)
show(f"put D=4 (drop {doomed})")
show(f"get B -> {cache.get('B')}")
show(f"get C -> {cache.get('C')}")

put A=1              A
put B=2              B A
put C=3              C B A
get A -> 1           A C B
put D=4 (drop B)     D A C
get B -> None        D A C
get C -> 3           C D A

That is the table from the walkthrough, produced by the code rather than by hand.

How the code maps to the idea

self.entries holds nodes, not values. This is the one line to remember. self.entries.get(key) hands you the node, and from the node you get the value, the two neighbours, and the ability to move it — without touching any other entry.

The sentinels erase the edge cases. _unlink is two assignments with no if in sight, because node.prev and node.next are never None for a real node. _link_front is four assignments for the same reason. Write either method without sentinels and you need branches for "the list is empty", "the node is first", "the node is last" and "the node is the only one".

A promotion is the two methods back to back. _unlink then _link_front: six pointer writes, in that order, whether the cache holds 3 entries or 3 million. They are not always paired — eviction calls _unlink on the coldest node and never relinks it, and a brand-new node goes straight to _link_front with nothing to unlink.

The node stores its own key, which looks redundant until you evict. Eviction starts from the list — self.tail.prev — and ends at the dict, and the only way from a node to its dict entry is the key the node carries. Drop that field and the dict grows for ever while the list stays capped.

put checks for an existing key before it checks capacity. If a full cache evicted first and only then noticed the key was already present, it would have thrown away a live entry to make room for one that needed no room.

get takes a default instead of returning None. If None is a legal value to cache, a bare None return is indistinguishable from a miss and your code recomputes that entry every time. Passing a private sentinel object as the default is the standard way out.

__contains__ does not promote, because checking whether something is cached is not the same as using it. That is a design decision rather than a law, but make it on purpose and document it: a caller who assumes the opposite gets a different eviction pattern. And capacity < 1 is rejected up front, because a capacity of zero breaks the sentinel invariant: the first put sees a full cache, reads self.tail.prev for the coldest node, and gets the head sentinel — the one node that has no prev. _unlink then raises AttributeError on node.prev.next. Rejecting the capacity is cheaper than teaching _unlink to defend itself.

The version you would actually write at work

collections.OrderedDict already contains exactly this doubly linked list, implemented in C. move_to_end does the promotion and popitem does the eviction, so the whole cache collapses to a dozen lines.

from collections import OrderedDict


class OrderedDictLRU:
    """The same cache in a fraction of the lines, using OrderedDict.

    Note the flipped convention: here the most recently used entry sits at
    the *end*, because that is where assigning a new key puts it.
    """

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.entries: OrderedDict = OrderedDict()

    def get(self, key: Hashable, default: Any = None) -> Any:
        if key not in self.entries:
            return default
        self.entries.move_to_end(key)  # O(1): unlinks and relinks one node
        return self.entries[key]

    def put(self, key: Hashable, value: Any) -> None:
        self.entries[key] = value
        self.entries.move_to_end(key)  # a new key is already last; an old one is not
        if len(self.entries) > self.capacity:
            self.entries.popitem(last=False)  # drop from the cold end

    def keys_mru_first(self) -> list:
        return list(reversed(self.entries))


compact = OrderedDictLRU(capacity=3)
for letter, number in [("A", 1), ("B", 2), ("C", 3)]:
    compact.put(letter, number)
compact.get("A")
compact.put("D", 4)
compact.get("B")
compact.get("C")
print("OrderedDict:", compact.keys_mru_first())
print("from scratch:", cache.keys_mru_first())

OrderedDict: ['C', 'D', 'A']
from scratch: ['C', 'D', 'A']

Same sequence, same final order. The trap is the move_to_end call inside put: assigning to a key that already exists updates the value but does not reorder it, so that line is doing real work even though it looks redundant for new keys. A plain dict can do this too, since deleting a key and reinserting it moves it to the end and dicts have kept insertion order since Python 3.7 — but move_to_end relinks one node instead of leaving a tombstone in the dict's table for a later resize to clean up.

The version you should usually reach for

If what you are caching is the return value of a function, do not build a cache at all. functools.lru_cache is a decorator that wraps any function whose arguments are hashable, and it is the same structure again — a dict of keys to links, plus a circular doubly linked list of those links.

from functools import lru_cache


@lru_cache(maxsize=128)
def fib(n: int) -> int:
    """Naive recursive Fibonacci: exponential uncached, linear with a cache."""
    return n if n < 2 else fib(n - 1) + fib(n - 2)


print(fib(60))
print(fib.cache_info())

1548008755920
CacheInfo(hits=58, misses=61, maxsize=128, currsize=61)

Naive fib(n) makes 2 × F(n+1) − 1 calls, so fib(60) undecorated is about five trillion of them. With the decorator, 61 misses do the real work and 58 hits come straight from the cache. cache_info() is the part people forget: it tells you whether the cache is earning its memory, and a hit count near zero means you are paying for bookkeeping and getting nothing. cache_clear() empties it.

functools.cache is the unbounded variant, identical to lru_cache(maxsize=None). With no ceiling there is nothing to evict, so it drops the linked list entirely and becomes a plain dict lookup — faster, and dangerous in exactly the way you would expect.

from functools import cache


@cache  # shorthand for lru_cache(maxsize=None): unbounded, nothing is ever evicted
def collatz_steps(n: int) -> int:
    """How many halve-or-triple steps it takes to reach 1."""
    if n == 1:
        return 0
    return 1 + collatz_steps(3 * n + 1 if n % 2 else n // 2)


print(max(collatz_steps(start) for start in range(1, 1000)))
print(collatz_steps.cache_info())

178
CacheInfo(hits=998, misses=2228, maxsize=None, currsize=2228)

999 starting values, and the cache holds 2,228 entries — the recursion cached every intermediate value it passed through as well. On a long-running process fed unbounded input, that is a memory leak with a decorator on it. Use functools.cache when the set of possible arguments is small and known, and lru_cache(maxsize=...) when it is not.

Complexity

get: O(1). A hit is one dict lookup, then _unlink (two pointer writes) and _link_front (four). Six writes, every time, with no loop anywhere — the count does not depend on how many entries the cache holds. A miss is one dict lookup and nothing else.

put: O(1). Existing key: one dict lookup, one value assignment, the same six pointer writes. New key into a full cache: one dict lookup, two writes to unlink the coldest node, one dict delete, one node allocation, one dict insert, four writes to link the new node at the front. A fixed amount of work, still no loop.

Eviction: O(1). This is what the tail sentinel buys. self.tail.prev is the least recently used node; nothing is searched, compared or sorted to find it.

The honest caveat is the dict. Python dict operations are O(1) on average, not in the worst case: if every key hashes to the same bucket, lookups degrade to a linear probe sequence, which needs pathological or attacker-chosen keys. Amortisation is involved too — a dict that has seen many inserts and deletes occasionally rebuilds its table, O(capacity) work on one unlucky insert, spread over all the ones that did not trigger it.

Compare the two implementations directly:

The naive column is index, then the shift from del, then the shift from insert(0, ...), each up to one full pass.

Space: O(capacity). Not O(number of distinct keys ever seen) — that is the whole selling point of a bounded cache. Each entry costs one _Node, one dict slot, and the key and value objects themselves. The __slots__ declaration matters more than it looks: on the CPython build used here, sys.getsizeof reports 64 bytes for a four-slot node against 48 bytes plus a 104-byte instance dictionary — 152 bytes — for the same class without it. At a capacity of 100,000 entries that one line saves about 8.8 MB. The two sentinels add two more nodes, for ever, regardless of capacity.

When to use it, and when not to

Use LRU when access has temporal locality — the same keys coming back soon after they were last used — and entries cost roughly the same to produce and take roughly the same space. Web sessions, database rows, rendered templates, compiled patterns and decoded images are all recency-friendly.

Do not hand-roll it in Python. Reach for functools.lru_cache if you are caching function results, and OrderedDict if you need a key-value store with your own hooks. Write the node-and-sentinel version only when you need something the standard library will not give you: an eviction callback, per-entry time-to-live, a budget in bytes rather than entries, or a policy that is not quite LRU. Otherwise the C implementations win on speed and on lines of code.

Do not use LRU for scan-shaped workloads. Its one spectacular failure mode is cycling repeatedly through slightly more distinct keys than the cache can hold. With capacity 1,000 and a loop over 1,001 keys, every request evicts the entry you are about to ask for next and the hit rate is exactly zero. Random eviction on that same loop hits about 99% of the time, because a randomly chosen victim is almost never the key you need next — LRU is beaten here by picking without looking. This is not hypothetical; it is what a full table scan does to a database cache. Look instead at MRU, at segmented LRU, or at admission policies that refuse to cache a key on its first sighting.

Do not put an in-process cache in front of shared state you do not own. Eight worker processes means eight independent caches, eight copies of the memory, and eight chances to serve a value another worker has already invalidated. Shared caching needs a shared cache: Redis or memcached.

This implementation is not thread-safe. Two threads interleaving inside _unlink corrupt the list. Every operation must hold one lock — CPython's own pure-Python lru_cache allocates an RLock for exactly this reason, with the comment "because linkedlist updates aren't threadsafe".

Other eviction policies, honestly

LRU is a default, not a law. Each alternative beats it on some real workload.

• FIFO evicts whatever was inserted longest ago and never promotes on a read, so there is no bookkeeping on the hot path at all — just a queue. Measurably worse than LRU on most workloads, and measurably cheaper. CPython's re module takes this deal: compiled patterns live in a plain dict capped at 512 entries, and when it fills, the oldest inserted entry is deleted. Insertion-ordered dicts make that a one-liner, and pattern reuse is not recency-shaped enough to justify more.
• LFU evicts the least frequently used entry. It beats LRU when popularity is stable and loses badly when it shifts, because an item that was hugely popular last week keeps its enormous count and squats in the cache for ever. Practical LFU implementations therefore decay their counters over time.
• Random picks a victim at random. Zero metadata, zero per-access work, immune to the scan pathology, and on many workloads within a few percentage points of LRU's hit rate. If bookkeeping is your bottleneck, this is a serious answer.
• MRU evicts the most recently used entry. Backwards, until you meet the cyclic scan: looping over 1,001 keys with room for 1,000, MRU keeps throwing away the same slot and hits on about 99% of requests where LRU hits on none. Random eviction lands within a point of it on that same loop, so MRU is the specialist here, not the only escape.
• Belady's optimal algorithm evicts the entry whose next use is furthest in the future. It needs the future, so it cannot be implemented — but it can be computed afterwards on a recorded trace, which makes it the yardstick every other policy is measured against.
• Hybrids are what modern systems ship: ARC, 2Q, segmented LRU and W-TinyLFU (used by the Caffeine cache library for Java) all mix recency with frequency and add scan resistance.

Where it shows up in the real world

functools.lru_cache is this post's data structure in the standard library, and memoising an expensive pure function is what most Python programmers use it for. Read functools.py and you will find a dict mapping keys to links, where each link is a four-element list holding prev, next, key and result, joined into a circular doubly linked list. The sentinel trick is there too, in a slicker form: a single root list initialised to point at itself, so the newest entry is always root[PREV] and the coldest is always root[NEXT]. On eviction it reuses the evicted link object as the new root rather than allocating a fresh one. Most CPython builds use a C implementation of the same design and fall back to that Python version when it is unavailable.

Redis exposes LRU as maxmemory-policy allkeys-lru — and does not implement exact LRU. A true recency list would cost two extra pointers on every key plus a list update on every access, across millions of keys. Instead each object header carries a 24-bit clock, and on eviction Redis samples a few random keys (maxmemory-samples, default 5), evicts the oldest of the sample, and keeps a pool of good candidates between rounds. The Redis documentation publishes hit-rate comparisons showing that sampling 10 keys lands very close to exact LRU. Redis 4.0 added allkeys-lfu beside it. The honest lesson: the exact structure is what you learn, and an approximation is what ships when memory per key is the constraint.

MySQL's InnoDB buffer pool splits its LRU list into a young and an old sublist, with the boundary 3/8 of the way down by default (innodb_old_blocks_pct is 37). Newly read pages enter at that midpoint rather than at the head, so a one-off full table scan fills the old sublist and drains out again without displacing the hot pages — a deliberate patch for the scan pathology above.

CPU caches approximate as well. Exact LRU across a 16-way set-associative cache needs enough state to encode an ordering of 16 lines, which is 45 bits per set; the tree-based pseudo-LRU used in real silicon needs 15. Multiply by every set in every cache in every core and the reason is obvious. Operating systems do the same thing one level up: Linux keeps active and inactive page lists with reference bits rather than a strict ordering, and PostgreSQL's shared buffers use a clock sweep with usage counters.

Memcached has used a segmented LRU since version 1.5, with hot, warm and cold segments and a background crawler moving items between them, again because plain LRU spent too much work promoting on every read. Browsers and CDNs evict cached responses under memory and disk pressure, where recency is the dominant signal, usually mixed with object size and remaining freshness.

Common mistakes

Not promoting on get. Leave the _unlink and _link_front pair out of get and you have quietly built a FIFO cache. It works, it passes casual tests, and it evicts entries you are using constantly. Reading is a use.

Updating a value without moving it. With OrderedDict, self.entries[key] = value on an existing key updates the value and leaves the order untouched. The unconditional move_to_end after the assignment is what makes it correct.

Evicting from the list but not the dict. The dict is the only thing keeping the evicted node alive, so forgetting del self.entries[coldest.key] gives you a dict that grows without limit and a len() that no longer matches the list. This is the bug the key field on the node exists to prevent.

Evicting before checking whether the key is present. A put on an existing key needs no space, so evicting first throws away a live entry for nothing and leaves the cache one entry short.

Returning None to mean "not cached". If None is a value you legitimately store, every read of it counts as a miss and the expensive work runs every time. Use an explicit sentinel object as the default.

Assuming functools.lru_cache is free on methods. The cache lives on the function object, shared by every instance, and each entry holds a reference to the self it was called with — so a decorated method keeps its instance alive for as long as the entry survives. For per-instance caching use functools.cached_property, or hold the cache on the instance.

Caching on unhashable arguments. lru_cache builds its key from the arguments, so a list or dict argument raises TypeError. Convert to a tuple or a frozenset at the boundary.

Practice

1. Add a peek(key) method that returns a value without promoting it, and show that keys_mru_first() is unchanged after calling it.
2. Add an on_evict callback, invoked with the key and value of every entry the cache drops, and use it to count evictions over a workload.
3. Add resize(new_capacity) that evicts from the tail until the cache fits, and returns how many entries it dropped.
4. Run one fixed sequence of key requests through your LRU cache and through a FIFO variant (identical, but get does not promote), and compare the hit counts. Then find a sequence where FIFO wins.
5. Implement an LFU cache that evicts the least frequently used entry, breaking ties by recency, and find one request pattern where it beats LRU and one where it is far worse.

Summary

An LRU cache is the clearest example in this series of two data structures covering each other's weakness. The hash map cannot order anything; the linked list cannot search. Point the map at the list's nodes and every operation — lookup, promotion, eviction — becomes a fixed number of pointer writes, whatever the capacity. The sentinels keep that code free of branches, and the key stored on each node keeps the two structures in step.

Write it once from scratch so the mechanism is yours, then use functools.lru_cache for the rest of your career. And keep the failure mode in mind: the moment your access pattern turns into a scan, the most-recently-used entry is the one you should be throwing away.

Keep reading

• Hash Tables in Python — where the O(1) lookup half of this structure comes from, and what "average case" is hiding.
• Linked Lists in Python — singly, doubly and circular lists built from scratch, including the sentinel trick used above.
• Queues and Deques in Python — collections.deque is the same doubly linked list, written in C.
• Dynamic Programming Explained — memoisation is the single biggest use of lru_cache, and this is why it works.
• Big O Notation — the counting arguments behind every complexity claim here.