Stage 1: The Doubly-Linked List

Objective:Build a doubly-linked list with O(1) head insertion and O(1) node removal -- the data structure that makes LRU eviction fast.

The LRU cache needs to do two things fast: move a node to the front (cache hit -- mark as recently used) and remove the node at the back (eviction -- drop the least recently used). Both operations require O(1) time, which means you can't traverse the list to find anything.

A doubly-linked list with sentinel nodes makes this clean. The sentinel head is always first; the sentinel tail is always last. Real data nodes sit between them. When you promote a node, you remove it from its current position (O(1) -- you know prev and next) and insert it after the sentinel head (O(1)). When you evict, you remove the node just before the sentinel tail (O(1) -- tail.prev).

Implement createList() returning:

• addToHead(val) -- create a new node { val, prev, next } and insert it immediately after the sentinel head; return the node
• removeFromTail() -- remove and return the node just before the sentinel tail (or null if the list is empty)
• remove(node) -- remove a specific node from the list (fix its neighbors' pointers)
• size -- number of real data nodes currently in the list

Sentinel pattern: Create a dummy head node and a dummy tail node. Wire them together: head.next = tail, tail.prev = head. Now every real node always has a prev and next -- no null-pointer edge cases on insert or remove.

Why this matters in production

A singly-linked list can remove the tail in O(1), but removing an arbitrary node takes O(n) because you need to find its predecessor. A doubly-linked list stores the predecessor directly (node.prev), so removing any node is O(1): update two pointers and you're done. This is the only reason LRU cache implementations use doubly-linked lists -- without it, promoting a cache hit to "most recently used" would cost O(n) per operation, making the cache useless at scale. Every LRU implementation from Memcached to Chrome's DiskCache uses exactly this structure.