Doubly Linked List Data Structure
A Doubly Linked List node contains both next and previous pointer references, enabling bidirectional traversal.
Doubly Linked List Bidirectional Relinking Step-by-Step
Identify Surrounding Node Pointers
Locate target.prev (NULL) and target.next (Node(45)).
Target: Node(15) | prev: NULL, next: Node(45)Relink Pointers & Free Node
Set head = target.next (Node(45)), set Node(45).prev = NULL. Free Node(15).
Result: NULL <-> [45] <-> NULLReal-world analogy: Two-Way Railway Line
Train cars are connected with couplings in both forward and backward directions, allowing movement both ways.
- Prev & Next= Pointers linking adjacent nodes bidirectionally.
Operations explained
Complexity analysis
500 steps (Linear)
O(N) Linear Time
O(1) / O(N) Space
Memory growth rate as N expands.
Relative efficiency rating for large N.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert Head / Tail | O(1) | O(1) |
| Delete Given Node | O(1) | O(1) |
Code implementations
class Node {
constructor(val) {
this.val = val;
this.prev = null;
this.next = null;
}
}Real-world applications
LRU Cache Memory
Moves accessed entries to head instantly.
Text Editor History
Navigates undo/redo steps bidirectionally.
Interview questions
Topic Knowledge Test & Assessment
Doubly Linked List Knowledge & Skill Test
Validate your conceptual understanding, operation mechanics, and core concepts of Doubly Linked List.
Topic Metadata
Doubly linked lists trade extra memory per node (for the `prev` pointer) to achieve O(1) node deletions!