Java Program to search an element in a Linked List

Introduction

The linked list is one of the most important data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

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

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.

Approach and Algorithm(In-built libraries)

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


import java.util.LinkedList;
  
public class SearchInALinkedList {
    public static void main(String[] args)
    {
        LinkedList 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: O(n), as list traversal is needed.
Space Complexity: O(1), as only temporary variables are being created.

Approach (Generic node class)

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

  • 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

Code Implementation


class Node {

    E data;

    Node next;

    Node(E data) { this.data = data; }
}
  
class LinkedList {

    Node head = null;
    int size = 0;

    public void add(E element)
    {

        if (head == null) {
            head = new Node<>(element);
            size++;
            return;
        }

        Node add = new Node<>(element);

        Node 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 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 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.

So, in this article, we have tried to explain the most efficient approach to search an element in a Linked List in Java. 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.

Previous post Count rotations in a sorted and rotated linked list
Next post LinkedList removeFirst method in Java

Leave a Reply

Your email address will not be published. Required fields are marked *