Doubly Linked List

Doubly Linked List

In a Doubly Linked List, each node contains three fields:

• prev — pointer to the previous node
• data — the stored value
• next — pointer to the next node

Node Structure

NULL <-- [prev | data | next] <--> [prev | data | next] --> NULL

Advantages over Singly LL

• Can traverse both forward and backward
• Deletion is easier — no need for a separate prev pointer variable during deletion
• Can efficiently implement LRU Cache, Deque, Browser history

Disadvantages

• Extra memory per node for the prev pointer
• More pointer updates per operation (must set both prev and next)

Operations & Complexity

Operation	Time	Notes
Insert at head	O(1)	Update prev/next of new and old head
Insert at tail	O(N)	Traverse to end
Delete node	O(1)	If pointer to the node is already known
Traverse forward	O(N)	Follow next pointers
Traverse backward	O(N)	Follow prev pointers