Creating a Doubly Linked List, Forward Traversal & Backward Traversal in Java
Welcome to Part 1B of our Doubly Linked List in Java series.
In Part 1A, we learned:
- ✅ What is a Doubly Linked List?
- ✅ Why do we need a Doubly Linked List?
- ✅ Limitations of Singly Linked List
- ✅ Advantages of Doubly Linked List
- ✅ Structure of a Node
- ✅ Memory Representation
- ✅ Head and Tail
- ✅ Creating a Node in Java
Now it’s time to connect those nodes together and build a complete Doubly Linked List.
In this tutorial, you’ll learn:
- 🏗️ Creating a Doubly Linked List
- 🚶 Forward Traversal
- 🔙 Backward Traversal
- 💻 Complete Java Programs
- 🔍 Dry Runs
- 📈 Time Complexity Analysis
- ❓ Frequently Asked Questions
Let’s begin!
📚 Table of Contents
- Creating a Doubly Linked List
- Connecting Nodes
- Forward Traversal
- Backward Traversal
- Java Programs
- Dry Runs
- Time Complexity
- Advantages
- Frequently Asked Questions
- Conclusion
🏗️ Creating a Doubly Linked List
Creating a Doubly Linked List simply means connecting multiple nodes together using both next and previous references.
Suppose we want to create the following list.
10 ⇄ 20 ⇄ 30 ⇄ 40
Unlike a Singly Linked List,
every connection is made in both directions.
🎨 Visual Representation
Head Tail
↓ ↓
NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL
Notice that
- Each node points to the next node.
- Each node also points to the previous node.
🔗 Connecting Nodes
Suppose we have
10
20
30
First,
Create all three nodes.
Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Now connect them.
10 ⇄ 20 ⇄ 30
Connection 1
first.next = second;
second.prev = first;
Connection 2
second.next = third;
third.prev = second;
Notice something.
Every connection requires two assignments.
🧠 Understanding the Connections
Suppose we have
10 ⇄ 20
Internally,
10.next = 20
20.prev = 10
Both references must be updated.
If either one is missing,
the list becomes incorrect.
💻 Java Program – Creating a Doubly Linked List
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
prev = null;
next = null;
}
}
public class DoublyLinkedList {
public static void main(String[] args) {
Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Node fourth = new Node(40);
first.next = second;
second.prev = first;
second.next = third;
third.prev = second;
third.next = fourth;
fourth.prev = third;
System.out.println("Doubly Linked List Created Successfully.");
}
}
Output
Doubly Linked List Created Successfully.
🚶 Forward Traversal
Traversal means visiting every node exactly once.
Forward traversal starts from the Head and moves toward the Tail.
Example
Head
↓
10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL
Traversal Order
10
↓
20
↓
30
↓
40
📝 Algorithm
- Start from Head.
- Print current node.
- Move to next node.
- Repeat until NULL.
💻 Java Program – Forward Traversal
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
prev = null;
next = null;
}
}
public class DoublyLinkedList {
public static void main(String[] args) {
Node head = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Node fourth = new Node(40);
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
third.next = fourth;
fourth.prev = third;
Node temp = head;
while(temp != null){
System.out.print(temp.data + " ");
temp = temp.next;
}
}
}
Output
10 20 30 40
🔍 Dry Run
Initially
Head
↓
10 ⇄ 20 ⇄ 30 ⇄ 40
Iteration 1
temp = 10
Print 10
Move to 20
Iteration 2
temp = 20
Print 20
Move to 30
Iteration 3
temp = 30
Print 30
Move to 40
Iteration 4
temp = 40
Print 40
Move to NULL
Traversal completed.
🔙 Backward Traversal
One of the biggest advantages of a Doubly Linked List is backward traversal.
Instead of starting from Head,
we start from the Tail.
Example
Head
↓
10 ⇄ 20 ⇄ 30 ⇄ 40
↑
Tail
Traversal Order
40
↓
30
↓
20
↓
10
🤔 Why Can’t We Do This in a Singly Linked List?
Because a Singly Linked List stores only
Next
A Doubly Linked List stores
Previous
Next
Therefore,
moving backward becomes possible.
📝 Algorithm
- Start from Tail.
- Print current node.
- Move to previous node.
- Repeat until NULL.
💻 Java Program – Backward Traversal
class Node {
int data;
Node prev;
Node next;
Node(int data){
this.data = data;
prev = null;
next = null;
}
}
public class DoublyLinkedList {
public static void main(String[] args){
Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Node fourth = new Node(40);
first.next = second;
second.prev = first;
second.next = third;
third.prev = second;
third.next = fourth;
fourth.prev = third;
Node tail = fourth;
Node temp = tail;
while(temp != null){
System.out.print(temp.data + " ");
temp = temp.prev;
}
}
}
Output
40 30 20 10
🔍 Dry Run
Initially
Tail
↓
40
40
Move
30
30
Move
20
20
Move
10
10
Move
NULL
Stop.
💻 Program – Forward and Backward Traversal Together
class Node {
int data;
Node prev;
Node next;
Node(int data){
this.data = data;
prev = null;
next = null;
}
}
public class DoublyLinkedList {
public static void main(String args[]){
Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Node fourth = new Node(40);
first.next = second;
second.prev = first;
second.next = third;
third.prev = second;
third.next = fourth;
fourth.prev = third;
Node head = first;
Node tail = fourth;
System.out.println("Forward Traversal:");
Node temp = head;
while(temp != null){
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
System.out.println("Backward Traversal:");
temp = tail;
while(temp != null){
System.out.print(temp.data + " ");
temp = temp.prev;
}
}
}
Output
Forward Traversal:
10 20 30 40
Backward Traversal:
40 30 20 10
📈 Time Complexity
Creating Nodes
O(n)
Forward Traversal
Every node is visited once.
O(n)
Backward Traversal
Every node is visited once.
O(n)
💾 Space Complexity
Only one temporary reference is used during traversal.
O(1)
🌟 Advantages of Doubly Linked List Traversal
✅ Can move in both directions.
✅ Easy to implement browser history.
✅ Suitable for Undo/Redo operations.
✅ Efficient navigation.
❓ Frequently Asked Questions
Q1. Why does a Doubly Linked List require both prev and next?
The next reference allows forward traversal, while the prev reference allows backward traversal.
Q2. Can backward traversal be performed without a Tail pointer?
Yes, but you must first traverse from the Head to reach the last node. Maintaining a Tail pointer makes backward traversal start immediately.
Q3. Is forward traversal faster than backward traversal?
No. Both visit each node exactly once and have O(n) time complexity.
Q4. Why must we update both next and prev references while connecting nodes?
If only one reference is updated, the links become inconsistent, and the list cannot be traversed correctly in both directions.
Q5. Why does a Doubly Linked List consume more memory than a Singly Linked List?
Each node stores an additional prev reference, increasing the memory required per node.
🎯 Key Takeaways
- 🔗 Every connection in a Doubly Linked List requires updating both
nextandprev. - 🚶 Forward traversal starts from the Head and follows
next. - 🔙 Backward traversal starts from the Tail and follows
prev. - 📍 Maintaining both Head and Tail simplifies many operations.
- 📈 Both forward and backward traversal have O(n) time complexity.
- 💾 Traversal requires only O(1) extra space.
🎉 Conclusion
In this part, you learned how to build a Doubly Linked List, connect nodes correctly, and traverse the list in both forward and backward directions. These operations form the foundation for all advanced Doubly Linked List operations.
The ability to move in both directions is what makes a Doubly Linked List more flexible than a Singly Linked List, especially in applications such as browser navigation, media players, and undo/redo systems.
👉 In Part 2, we’ll begin performing Insertion Operations in a Doubly Linked List, including:
- ➕ Insertion at the Beginning
- ➕ Insertion at the End
- ➕ Insertion at a Specific Position
- 🧠 Updating both
prevandnextreferences correctly - 💻 Complete Java programs
- 🔍 Detailed dry runs
- 📈 Time complexity analysis
