Doubly Linked List

Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is `O(n)`. Add a `prev` pointer to every node and the same delete becomes four pointer rewires in `O(1)`, which is exactly the upgrade that powers LRU caches and the browser back-forward stack. This lesson covers the **Doubly Linked List** node layout (`value`, `next`, `prev`), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks. In **Linked Lists (Singly)**, head insertion was already `O(1)` but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping. Next, **Circular Linked List** keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.

Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both `get(key)` and `put(key, value)` in `O(1)`. No single primitive does that: a hash map gives `O(1)` lookup but no recency order, and a doubly linked list gives `O(1)` recency moves but no key index. The classical **LRU Cache** wires the two together so each compensates for what the other lacks. This lesson designs the composite from scratch: a hash map that points keys to DLL nodes, and a doubly linked list that orders nodes by recency with most-recent at the head and least-recent at the tail. You will trace `get` and `put` through both structures, handle the capacity-of-one and update-existing-key edge cases, and see why this design appears in browser caches, database query caches, OS page replacement, and CDNs. In **Hash Map (Dictionary) Basics**, you used a hash map for `O(1)` lookup by key. **Doubly Linked List** added the `prev` pointer that makes mid-list deletion `O(1)` once you hold the node, plus the sentinel pattern that erases null checks at the boundaries; both are load-bearing here. The LRU pattern (one structure for indexing, another for ordering, kept consistent on every operation) is the gateway to a wider family of composite designs covered in later lessons.