Linked Lists & Custom Allocators

Building an LRU cache from scratch is one of the best ways to understand how data structures combine in real systems. The industry standard pattern is combining two complementary structures:

1. A Hash Map: Gives you O(1) key-to-node lookups.
2. A Doubly Linked List (DLL) with Dummy Head & Tail: Gives you O(1) node insertion at the front (most recent) and O(1) node removal from the back (least recent).

The secret trick that eliminates 90% of bug-prone null checks is using sentinel (dummy) head and tail nodes. Instead of constantly checking if (head == null) or if (node->prev == null), the dummy head and tail are always linked together: head <-> tail. Any real data node always lives safely in between them!

Architectural Diagram

[Head Dummy] <---> [Most Recent Node] <---> [Older Node] <---> [Tail Dummy]
                                                                      ^
                                                      Evict from here |

Clean, Idiomatic Python 3.12 Implementation

class Node:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, Node] = {}
        
        # Dummy sentinel boundaries
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        """Unlinks a node from its current position."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_at_front(self, node: Node) -> None:
        """Inserts node right after head (most recently used)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # Refresh access: move to front
        self._remove(node)
        self._insert_at_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._insert_at_front(node)
        else:
            if len(self.cache) >= self.cap:
                # Evict least recently used (node right before tail)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
                
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._insert_at_front(new_node)

Why Storing the Key Inside the Node is Crucial

Notice that the Node class stores both key and val. Many developers forget to store key in the node and only store val. But when the cache reaches full capacity and you evict tail.prev, how do you delete that entry from the hash map? Without node.key, you’d have to search the entire hash map in O(N) time, destroying your O(1) guarantee!

Thread Safety in Production

If multiple threads access this cache concurrently:

• In Python, use threading.Lock() around get and put.
• In Go or C++, a Read-Write Lock (sync.RWMutex / std::shared_mutex) is often tempting, but remember: even a get() operation mutates the linked list (to move the accessed item to the front)! Therefore, standard read locks are not enough—you must acquire an exclusive lock or use lock striping across multiple shards.