Doubly Linked List
A doubly linked list gives each node both prev and next, enabling constant-time removal from the middle when the node itself is already known.
Two Directions Per Node
A doubly linked list node is shaped like {val, prev, next}. The next pointer moves forward, and the prev pointer moves backward. Drawn in the forward direction, the list is head -> 1 -> 2 -> 3 -> null, while the prev pointers point back from 3 to 2, 2 to 1, and 1 to null.
This two-way structure makes traversal flexible. From a middle node, you can move to its successor or predecessor without returning to head. That extra reach is exactly what many design problems need.
Why Deletion Becomes Easier
In a singly linked list, deleting a known node usually requires the previous node so you can reconnect around it. In a doubly linked list, the node carries that previous pointer itself. Given only the node, you can connect node.prev.next to node.next and connect node.next.prev back to node.prev.
That makes deletion O(1) when the node is already known. The operation is local, but it has two sides. Forgetting either side leaves a broken chain that may still appear correct in one traversal direction and fail in the other.
Where Interviews Use It
Doubly linked lists appear in cache and navigation designs. In an LRU cache, the list stores items from most recently used to least recently used, while a HashMap stores key to node. Access moves a node to the front in O(1), and eviction removes the tail in O(1). LFU designs often combine frequency buckets with doubly linked lists for the same reason.
Browser history is another natural example. Moving back follows prev; moving forward follows next. The structure models bidirectional navigation directly instead of forcing a stack-only view.
The Cost of Extra Power
The trade-off is memory and bookkeeping. Every node stores one extra pointer, and every insert or delete must maintain more relationships. For insertion between a and b, the new node must point to both neighbors, a.next must point forward to the new node, and b.prev must point back to it.
That extra complexity is worthwhile when nodes are frequently moved or removed from the middle. If the task only scans forward and rarely mutates local nodes, a singly linked list is simpler and usually enough.
Minimal doubly linked list node
A doubly linked node stores both directions, which is what allows O(1) removal after a cache or history map hands you the node.
Key Takeaways
- A doubly linked list node has **val**, **prev**, and **next** fields.
- Given only the node, middle deletion can be **O(1)** because the predecessor is stored on the node.
- LRU, LFU, and browser-history designs use doubly linked lists to move or remove known nodes quickly.
- The extra pointer improves flexibility but increases memory use and mutation bookkeeping.