Last Updated on July 31, 2023 by Mayank Dham
Throughout our exploration of linked list operations, including insertion and deletion, one crucial operation that stands out is searching within a linked list. Regardless of the various operations we encounter, the need for efficient searching in a linked list remains essential.
Java program to search element in linked list
In this question, we are given a singly linked list. We have to search for a given element X in the list. If it is present, we have to return its index, otherwise -1.
How to find element in linked list in java
Let’s first understand the problem statement with the help of examples.
Suppose the given list is:
and the element to be searched is 15. As we can see, 15 is present in the list at the 2nd index.
So, our program will return the value 2 (considering 0 based indexing), which is the index of elements to be searched in the given linked list.
Input:
X = 15.
Output: 2
Explanation: As we can see, 15 is present at the 2nd index.
Now, I think it is clear from the above example what we have to do in the problem. So let’s move to approach.
Before jumping to approach, just try to think how you can approach this problem?
It’s okay, if your solution is not the best optimized solution, we will try to optimize it together.
This question is not a very complex one. We have to make use of list traversal in the question. We can either use the in-built library to traverse through the linked list or the normal linked list traversal method.
Let us have a glance at the approaches.
Let us have a glance at the approaches for the Java program to find element in linked list.
Approach and Algorithm(In-built libraries) for searching in linked list
The approach is going to be pretty simple.
- First, we will initialize the linked list.
- Now, as we are allowed to use in-built libraries, we can use a for loop with zero-based indexing to traverse through the list.
- To extract the ith element, we can simply use List.get(i).
- We will create an integer variable ans and initialize it with -1.
- Now, we will simply traverse through the loop and for every element, we will check if the data of that node is equal to the searched element. If the condition becomes true, we will store i in ans and break from the loop.
- In the end, if the value of ans remains -1, it means that the element is not present in the list. Else, we will print the ans.
Code Implementation of search in linked list java
import java.util.LinkedList;
public class SearchInALinkedList {
public static void main(String[] args)
{
LinkedList<integer> llist = new LinkedList<>();
llist.add(1);
llist.add(7);
llist.add(15);
llist.add(27);
int element = 15;
int ans = -1;
for (int i = 0; i < llist.size(); i++) {
int llElement = llist.get(i);
if (llElement == element) {
ans = i;
break;
}
}
if (ans == -1) {
System.out.println("Element not found");
}
else {
System.out.println(
"Element found at index " + ans);
}
}
}
Output
Element found at index 2
Time Complexity for search in linked list java: O(n), as list traversal is needed.
Space Complexity for java program to search element in linked list
: O(1), as only temporary variables are being created.
Approach (Generic node class) for search in linked list java
In this approach, we will use the generic list traversal method.
- If the head of the list is null, we will return -1.
- Now, we will traverse through the list and check if the element is present in the list or not. We will also maintain an index variable which will initially be 0 and will be incremented by 1 in every iteration.
- If the element to be searched matches with the current node’s data, we will return the index.
In the end, if element to be searched, not found in the list we will return -1, as the element is not present.
Algorithm for search in linked list java
- Base case – If the head is null, return -1
- Create a variable index and initialize it with 0, and a node curr which will have the value of head.
- Traverse through the list using curr.
- In every iteration, check if the data of curr is equal to the search element or not. If it is equal, we will return the index variable. Also increment the index variable by 1 in every iteration.
- In the end, return -1, as the search element is not present in the list.
Dry Run for searching in linked list
Code Implementation
class Node<e> {
E data;
Node<e> next;
Node(E data) { this.data = data; }
}
class LinkedList<e> {
Node<e> head = null;
int size = 0;
public void add(E element)
{
if (head == null) {
head = new Node<>(element);
size++;
return;
}
Node<e> add = new Node<>(element);
Node<e> temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = add;
size++;
}
public int search(E element)
{
if (head == null) {
return -1;
}
int index = 0;
Node<e> temp = head;
while (temp != null) {
if (temp.data == element) {
return index;
}
index++;
temp = temp.next;
}
return -1;
}
}
public class PrepBytes {
public static void main(String[] args) throws Exception
{
LinkedList<integer> ll = new LinkedList<>();
ll.add(1);
ll.add(7);
ll.add(15);
ll.add(27);
int element = 15;
int ans = ll.search(element);
if (ans == -1) {
System.out.println(
"Element not found in the Linked List");
}
else
System.out.println(
"Element found at index "
+ ans);
}
}
Output:
Element found at index 2
Time Complexity: O(n), as list traversal is needed.
Conclusion
So, in the above article, we tried to understand the most optimal approach for searching in Linked List in Java.The implementation of code made it seem easy and understandable. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.
Conclusion
In this article, we learned how to implement a Java program to search for an element in a linked list. We used a simple and efficient approach that involved traversing the linked list and comparing each node’s data with the target element. If a match was found, we returned the index (position) of the element; otherwise, we indicated that the element was not present in the linked list. By following this method, we can easily search for elements in both singly and doubly linked lists.
Frequently Asked Questions (FAQs) related to Java Program to find element in linked list:
Q1. How does the search operation work in a linked list?
The search operation in a linked list involves iterating through the list and comparing the data of each node with the target element we want to find. Starting from the head (or tail in the case of doubly linked lists), we traverse the list until we find the matching element or reach the end of the list. If the element is found, we return its position (index); otherwise, we indicate that the element is not present.
Q2. What is the time complexity of searching in a linked list?
The time complexity of searching in a linked list is O(n), where "n" is the number of nodes in the linked list. In the worst-case scenario, we may need to traverse the entire list to find the target element.
Q3. How can I implement a search operation in a singly linked list?
To implement a search operation in a singly linked list, follow these steps:
Start from the head of the linked list.
Traverse the list one node at a time.
Compare the data of each node with the target element.
If a match is found, return the index (position) of the element; otherwise, continue to the next node.
If the end of the list is reached without finding the element, indicate that the element is not present.
Q4. How can I implement a search operation in a doubly linked list?
Searching in a doubly linked list is similar to searching in a singly linked list, but with the advantage of being able to traverse the list in both directions. The steps are as follows:
Start from the head (or tail, depending on the search direction) of the linked list.
- Traverse the list one node at a time, either moving forward (next pointer) or backward (previous pointer).
- Compare the data of each node with the target element.
- If a match is found, return the index (position) of the element; otherwise, continue to the next/previous node.
- If the end of the list is reached without finding the element, indicate that the element is not present.
Q5. Can I optimize the search operation in a linked list to reduce time complexity?
The search operation in a basic linked list has a time complexity of O(n) since we need to traverse the entire list in the worst case. To optimize the search, we can consider using more advanced data structures like hash tables or binary search trees, which can provide faster search times (O(1) for hash tables and O(log n) for balanced binary search trees). However, these data structures come with their own trade-offs, and their implementation may be more complex compared to a standard linked list search.