Have you ever clicked:
Back
Forward
inside a browser?
That feature works efficiently because the system can move in both directions.
A Doubly Linked List provides exactly that capability.
Unlike a Singly Linked List, every node knows:
- who comes next
- who came before
1. What is a Doubly Linked List?
A Doubly Linked List is a collection of nodes where each node stores:
- data
- next pointer
- previous pointer
Visual representation:
null ← [10] ⇄ [20] ⇄ [30] → null
This allows traversal in both directions.
2. Node Structure
public class DNode {
int data;
DNode prev;
DNode next;
DNode(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
What's New?
Compared to a Singly Linked List:
Node next;
becomes
DNode prev;
DNode next;
One extra pointer unlocks bidirectional navigation.
3. Insert at Head
Idea
Create a new node and make it the first node.
public void insertAtHead(int data) {
DNode newNode = new DNode(data);
newNode.next = head;
if (head != null)
head.prev = newNode;
head = newNode;
}
Complexity
O(1)
No traversal required.
4. Insert at End
Idea
Move to the last node and attach the new node.
public void insertAtEnd(int data) {
DNode newNode = new DNode(data);
if (head == null) {
head = newNode;
return;
}
DNode temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
Complexity
O(n)
Traversal is needed.
5. Delete a Node
Idea
Reconnect neighboring nodes.
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
The node gets removed from the chain.
Why Deletion is Easier
In a Singly Linked List:
- you must find the previous node.
In a Doubly Linked List:
- previous node is already available.
That's a major advantage.
6. Advantages
_- Bidirectional Traversal
_
Move:
- forward
- backward
- Easier Deletion
Previous node is instantly accessible.
- Better Navigation Systems
Perfect for:
- browser history
- undo/redo systems
- playlists
7. Drawbacks
- Extra Memory
Each node stores one additional pointer.
- More Pointer Updates
Insertion and deletion require updating multiple links.
Key Insights
- Nodes store prev + next
- Traversal works both directions
- Easier deletion than singly linked lists
- Uses more memory
Doubly Linked Lists solve one of the biggest limitations of Singly Linked Lists:
- moving backward.
That single improvement makes them ideal for many real-world systems, from browsers to text editors and music players.
Explore More: https://www.quipoin.com/tutorial/data-structure-with-java/doubly-linked-list