## What is it? A Doubly Linked List extends the singly linked list by giving each node a pointer to both its next and previous nodes. This allows traversal in both directions and O(1) deletion when the node reference is known. ## How it works Each node: `{ value, prev → Node | null, next → Node | null }` **Core operations:** - **Insert at head/tail** → O(1) — update two pointers - **Delete (given node)** → O(1) — adjust prev and next neighbors - **Delete by value** → O(n) — first find the node - **Traverse forward/backward** → O(n) ## When to use - LRU Cache (need O(1) delete from the middle) - Browser history (forward/back navigation) - Deque (double-ended queue) implementation - Any problem where backward traversal is needed ## Key Points - Each insertion/deletion updates 4 pointers (prev and next of two nodes) - Sentinel/dummy head and tail nodes simplify edge case handling - Uses twice as much pointer memory as a singly linked list