Searching, Updating, Counting Nodes & Reversing a Singly Linked List
Welcome to Part 4 of our Singly Linked List in Java series.
So far, we’ve learned:
✅ Part 1
- Introduction to Linked Lists
- Node Structure
- Creating Nodes
- Traversing a Linked List
✅ Part 2
- Insertion at Beginning
- Insertion at End
- Insertion at Specific Position
✅ Part 3
- Deletion from Beginning
- Deletion from End
- Deletion at Specific Position
- Deletion by Value
Now we’ll learn four more important operations that are frequently asked in university exams and technical interviews:
- 🔍 Searching a Node
- ✏️ Updating Node Data
- 🔢 Counting the Number of Nodes
- 🔄 Reversing a Singly Linked List
By the end of this tutorial, you’ll be able to perform all common operations on a Singly Linked List.
📚 Table of Contents
- Searching in a Linked List
- Updating Node Data
- Counting the Number of Nodes
- Reversing a Linked List
- Java Programs
- Dry Runs
- Time Complexity
- Interview Questions
- Conclusion
🔍 Searching in a 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
Found
Search
70
Result
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 – Search
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
Worst Case
O(n)
Space
O(1)
✏️ Updating a Node
Updating means replacing the old value with a new value.
Suppose
10 → 20 → 30 → 40
Replace
30
with
35
Result
10 → 20 → 35 → 40
📝 Algorithm
- Traverse the linked list.
- Find the required value.
- Replace it.
- 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");
}
Example
list.update(30,35);
Output
10 → 20 → 35 → 40
🔍 Dry Run
Current
10 → 20 → 30 → 40
Search
30
Replace
30
↓
35
Result
10 → 20 → 35 → 40
📈 Time Complexity
Traversal required.
O(n)
Space
O(1)
🔢 Counting Number of Nodes
Sometimes we need to know how many nodes are present.
Suppose
10 → 20 → 30 → 40 → 50
Count
5
📝 Algorithm
- Start from Head.
- Initialize count = 0.
- Move through 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;
}
Example
System.out.println(list.countNodes());
Output
5
🔍 Dry Run
List
10 → 20 → 30 → 40
Count
0
Visit 10
1
Visit 20
2
Visit 30
3
Visit 40
4
Return
4
📈 Time Complexity
Traversal
O(n)
Space
O(1)
🔄 Reversing a Singly Linked List
One of the most popular interview questions.
Current List
10 → 20 → 30 → 40 → NULL
After Reversing
40 → 30 → 20 → 10 → NULL
🤔 Why is Reversing Difficult?
In a singly linked list,
every node only knows the next node.
To reverse,
we must change every reference.
📝 Algorithm
We use three references.
previous
current
next
Initially
previous = NULL
current = head
Repeat
- Store next node.
- Reverse current link.
- Move previous.
- Move current.
Finally,
Head becomes previous.
🎨 Visual Explanation
Initially
NULL ← previous
10 → 20 → 30 → 40
↑
current
Step 1
Store
next = 20
Reverse
10 → NULL
Move
previous = 10
current = 20
Next Iteration
20 → 10
Then
30 → 20 → 10
Finally
40 → 30 → 20 → 10
Done!
💻 Java Program – Reverse Linked List
public void reverse() {
Node previous = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
head = previous;
}
Example
Before
10 → 20 → 30 → 40
After
40 → 30 → 20 → 10
💻 Complete Java Program
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
public class SinglyLinkedList {
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;
}
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 previous = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
head = previous;
}
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) {
SinglyLinkedList list = new SinglyLinkedList();
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)
🌟 Advantages
✅ Easy to search sequentially.
✅ Updating only changes the node’s data.
✅ Counting nodes is straightforward.
✅ Reversing does not require additional memory.
❓ Frequently Asked Questions
Q1. Why is searching in a linked list O(n)?
Because nodes are stored sequentially, and we may need to visit every node.
Q2. Can we directly access the fifth node?
No. Unlike arrays, linked lists do not support random access. We must traverse from the head.
Q3. Why do we need three references while reversing?
- previous keeps track of the reversed part.
- current points to the node being processed.
- next temporarily stores the next node so that we don’t lose the rest of the list after changing the link.
Q4. Is reversing a linked list done in place?
Yes. The links are updated within the existing list, so no additional linked list is created.
Q5. What is the time complexity of reversing a linked list?
Since each node is visited exactly once, the time complexity is O(n).
🎯 Key Takeaways
- 🔍 Searching traverses the list until the required value is found.
- ✏️ Updating changes the data stored in an existing node.
- 🔢 Counting nodes involves visiting every node exactly once.
- 🔄 Reversing a linked list changes the direction of every link.
- 🚀 All four operations have O(n) time complexity and O(1) extra space.
🎉 Conclusion
Searching, updating, counting, and reversing are essential operations that complete the core functionality of a Singly Linked List. These operations are frequently used in real-world applications and are among the most common coding interview questions.
By understanding how references are manipulated, you’ve now mastered the fundamental operations on a singly linked list. You can create, traverse, insert, delete, search, update, count, and reverse nodes with confidence.
👉 In Part 5, we’ll conclude this series by covering:
- 📊 Time Complexity Summary of All Linked List Operations
- ⚖️ Arrays vs Linked Lists
- 🔄 Singly vs Doubly vs Circular Linked Lists
- 🌍 Real-World Applications of Linked Lists
- 🎯 Common Interview Questions
- 📝 Practice Programs
- 🧠 Revision Notes and Key Takeaways
This final part will help you revise everything you’ve learned and prepare for exams and technical interviews.
