🔍 Searching, ✏️ Updating, 🔢 Counting Nodes & 🔄 Reversing a Doubly Linked List
Welcome to Part 4 of our Doubly Linked List in Java series.
So far, we have learned:
✅ Part 1A
- Introduction to Doubly Linked List
- Need for Doubly Linked List
- Node Structure
- Memory Representation
✅ Part 1B
- Creating a Doubly Linked List
- Forward Traversal
- Backward Traversal
✅ Part 2
- Insertion at Beginning
- Insertion at End
- Insertion at Specific Position
✅ Part 3
- Deletion from Beginning
- Deletion from End
- Deletion at Position
- Deletion by Value
Now we’ll learn four more important operations that complete the core functionality of a Doubly Linked List:
- 🔍 Searching
- ✏️ Updating
- 🔢 Counting Nodes
- 🔄 Reversing a Doubly Linked List
These operations are frequently asked in university exams and coding interviews.
Let’s begin!
📚 Table of Contents
- Searching
- Updating
- Counting Nodes
- Reversing a Doubly Linked List
- Java Programs
- Dry Runs
- Time Complexity
- Common Mistakes
- FAQs
- Conclusion
🔍 Searching in a Doubly Linked List
Searching means finding whether a particular value exists in the linked list.
Suppose we have
10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50
Search
30
Result
Element Found
Search
70
Result
Element Not Found
📝 Algorithm
- Start from Head.
- Compare current node with the required value.
- If found, stop.
- Otherwise move to the next node.
- Continue until NULL.
💻 Java Program – Searching
public boolean search(int value){
Node temp = head;
while(temp != null){
if(temp.data == value)
return true;
temp = temp.next;
}
return false;
}
Example
if(list.search(30))
System.out.println("Element Found");
else
System.out.println("Element Not Found");
Output
Element Found
🔍 Dry Run
Current List
10 ⇄ 20 ⇄ 30 ⇄ 40
Search
30
Compare
10 ≠ 30
↓
20 ≠ 30
↓
30 = 30
Found.
📈 Time Complexity
Searching requires traversal.
O(n)
Extra Space
O(1)
✏️ Updating a Node
Updating means replacing an existing value with another value.
Suppose
10 ⇄ 20 ⇄ 30 ⇄ 40
Replace
30
with
35
Result
10 ⇄ 20 ⇄ 35 ⇄ 40
📝 Algorithm
- Traverse the list.
- Find the required node.
- Replace its data.
- Stop.
💻 Java Program – Update
public void update(int oldValue,int newValue){
Node temp = head;
while(temp != null){
if(temp.data == oldValue){
temp.data = newValue;
return;
}
temp = temp.next;
}
System.out.println("Value Not Found");
}
Output
10 ⇄ 20 ⇄ 35 ⇄ 40
📈 Time Complexity
Traversal required.
O(n)
🔢 Counting the Number of Nodes
Sometimes we need to know the size of the linked list.
Suppose
10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50
Total Nodes
5
📝 Algorithm
- Start from Head.
- Initialize count = 0.
- Visit every node.
- Increment count.
- Return count.
💻 Java Program – Count Nodes
public int countNodes(){
Node temp = head;
int count = 0;
while(temp != null){
count++;
temp = temp.next;
}
return count;
}
Output
5
📈 Time Complexity
O(n)
Space
O(1)
🔄 Reversing a Doubly Linked List
One of the most interesting interview questions.
Suppose
10 ⇄ 20 ⇄ 30 ⇄ 40
After reversing
40 ⇄ 30 ⇄ 20 ⇄ 10
Unlike a Singly Linked List,
we must reverse both previous and next references.
🤔 How Does Reversal Work?
Every node stores
Previous
Next
To reverse,
we simply swap these two references for every node.
🎨 Visual Explanation
Current
NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL
Node 20
Initially
Prev = 10
Next = 30
After swapping
Prev = 30
Next = 10
Every node performs the same operation.
Finally,
Head becomes the old Tail.
📝 Algorithm
- Start from Head.
- Swap previous and next references.
- Move to the next node (which becomes previous after swapping).
- Continue until the end.
- Update Head.
💻 Java Program – Reverse
public void reverse(){
Node current = head;
Node temp = null;
while(current != null){
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if(temp != null)
head = temp.prev;
}
Example
Before
10 ⇄ 20 ⇄ 30 ⇄ 40
After
40 ⇄ 30 ⇄ 20 ⇄ 10
🔍 Dry Run
Initially
10 ⇄ 20 ⇄ 30 ⇄ 40
At Node 10
Swap
Prev = 20
Next = NULL
Move to Node 20.
Repeat.
Eventually
40 ⇄ 30 ⇄ 20 ⇄ 10
💻 Complete Java Program
class Node{
int data;
Node prev;
Node next;
Node(int data){
this.data = data;
prev = null;
next = null;
}
}
public class DoublyLinkedList{
Node head;
public void insertAtEnd(int data){
Node newNode = new Node(data);
if(head == null){
head = newNode;
return;
}
Node temp = head;
while(temp.next != null)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
public boolean search(int value){
Node temp = head;
while(temp != null){
if(temp.data == value)
return true;
temp = temp.next;
}
return false;
}
public void update(int oldValue,int newValue){
Node temp = head;
while(temp != null){
if(temp.data == oldValue){
temp.data = newValue;
return;
}
temp = temp.next;
}
}
public int countNodes(){
Node temp = head;
int count = 0;
while(temp != null){
count++;
temp = temp.next;
}
return count;
}
public void reverse(){
Node current = head;
Node temp = null;
while(current != null){
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if(temp != null)
head = temp.prev;
}
public void display(){
Node temp = head;
while(temp != null){
System.out.print(temp.data + " ⇄ ");
temp = temp.next;
}
System.out.println("NULL");
}
public static void main(String args[]){
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.display();
System.out.println(list.search(30));
list.update(30,35);
list.display();
System.out.println("Total Nodes = " + list.countNodes());
list.reverse();
list.display();
}
}
📊 Time Complexity
| Operation | Time Complexity |
|---|---|
| Search | O(n) |
| Update | O(n) |
| Count Nodes | O(n) |
| Reverse | O(n) |
💾 Space Complexity
All operations use only a few temporary references.
O(1)
⚠️ Common Mistakes
❌ Forgetting to swap both references
Many beginners only change the next reference.
In a Doubly Linked List,
both
prev
next
must be swapped.
❌ Forgetting to update Head
After reversing,
the old Tail becomes the new Head.
Always update
head = temp.prev;
❌ Traversing incorrectly after swapping
After swapping,
the next node becomes
current.prev
not
current.next
❓ Frequently Asked Questions
Q1. Why is searching O(n)?
Because we may need to visit every node.
Q2. Can we update a node without searching?
No.
We must first locate the node.
Q3. Why do we swap both prev and next while reversing?
Because both links define the structure of a Doubly Linked List.
Q4. Is reversing done in-place?
Yes.
No additional linked list is created.
Q5. What is the time complexity of reversing?
Every node is visited exactly once.
O(n)
🎯 Key Takeaways
- 🔍 Searching traverses the list from Head.
- ✏️ Updating changes the data stored in a node.
- 🔢 Counting requires visiting every node.
- 🔄 Reversing swaps both
prevandnextreferences. - 🚀 All operations require O(n) time.
- 💾 Extra space required is O(1).
🎉 Conclusion
Searching, updating, counting, and reversing complete the set of core operations for a Doubly Linked List. These operations demonstrate the true advantage of storing both previous and next references, enabling efficient bidirectional navigation while keeping memory usage reasonable.
By now, you’ve learned how to create, traverse, insert, delete, search, update, count, and reverse a Doubly Linked List in Java.
👉 In Part 5 (Final Part), we’ll complete this series by covering:
- 📊 Time Complexity Summary
- ⚖️ Singly vs Doubly Linked List
- 📚 Arrays vs Doubly Linked List
- 🌍 Real-World Applications
- 🎯 Interview Questions
- 🧪 Practice Programs
- 📝 Revision Notes
- 🎉 Final Conclusion
This final part will serve as your complete revision guide for exams, interviews, and practical programming.
