Designing data structures

Combine basic primitives (maps, lists, heaps) to create complex data structures with fast operations.

The idea

Many system design problems ask you to build a custom data structure with specific time complexities (e.g., O(1) read, O(1) write, O(1) eviction).

A classic example is the LRU (Least Recently Used) Cache. A Hash Map gives O(1) lookup, but it doesn't preserve order. An Array preserves order, but deleting an element takes O(N). By combining a Hash Map with a Doubly-Linked List, we get the best of both: O(1) lookups and O(1) moves to the front of the line!

Capacity is 3. A is least recently used (tail). C is most recently used (head).

How it works (LRU Cache)

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {} # Key -> Node
        self.head = Node(0, 0) # Dummy head (MRU)
        self.tail = Node(0, 0) # Dummy tail (LRU)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key in self.map:
            node = self.map[key]
            self.remove(node)
            self.add_to_head(node)
            return node.val
        return -1