Java Program to search an element in a Linked List

We have seen so many operations in the linked list such as insertion, deletion etc. We might have many operations but to find an element in a linked list Searching in linked list is necessary.

Problem Statement for 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.

Problem Statement Understanding for search in linked list 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 2^nd 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 2^nd 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.

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 i^th 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.

FAQs of searching in linked list

1. Which searching technique is not suitable for linked list?

Binary search is not suitable for linked lists because the memory is dynamic and non-contiguous which makes it difficult to find the middle element.

2. What>What is the time complexity of singly linked list?

The time complexity of singly linked list for insertion or deletion is O(n).

3. Which linked list consumes more space ?

Doubly linked list consumes more space because it has a data part and two pointers in which one pointer points to the next node and the other pointer points to the previous node.