Linear Search in Java [both Array + Linked List]

In this article at OpenGenus, we will be implementing linear search algorithm for both arrays and linked list in Java.

Table of Contents

1. About Linear Search
2. Example
3. Implementation for Arrays
4. Implementation for Linked Lists
5. Time Complexity
6. Space Complexity

Linear Search

Linear Search is a simple search algorithm in which we traverse a list sequentially until we find the element we are searching for or until all the elements have been checked and we reach the end of the list.

Example

Suppose, we want to find for number 7 in a given array = [4, 2, 6, 5, 7, 9].
Now, according to the linear search algorithm, we will start comparing each element of array to the number we want to find, and if the element is equal to the number, we will print "number is found". Else, we will print "number not found".
Compare first element, 4 with 7, 4 != 7, we move on.
Compare next element, 2 with 7, 2 != 7, we again move on.
Compare next element, 6 with 7, 6 != 7, we again move on.
Compare next element, 5 with 7, 5 != 7, we again move on.
Compare next element, 7 with 7, 7 == 7, we found our target and terminate the search.

Implementing Linear Search for Arrays

Let us first initialize an array arr in which we want to find our element:-

int[] arr = {4, 2, 6, 1, 7, 9};

Now, let's give a variable name num to the number we want to search for:-

int num = 7;

Now, we will compare each element starting from the first element with num until we found num or until all the elements have been compared and we have reached end of the array.
This can be done by a for loop:-

for(int i = 0; i < arr.length; i++) {
      if(arr[i] == num) {
        System.out.println("Number found!");
        return;
      }
}

We will print "Number found!", if we found the element, otherwise, we will print "Number not found!"

Here is the entire code with sample output:-

class main {
    private static void linearSearch(int[] arr, int num) {
        for(int i = 0; i < arr.length; i++) {
          if(arr[i] == num) {
            System.out.println("Number found!");
            return;
          }
        }
         // If number not found print this
        System.out.println("Number not found!");
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 6, 1, 7, 9};
        int num = 7;
        linearSearch(arr, num);
    
    }
}

Output:-

Number found!

Implementation for Linear Search in Linked List

In this article, we will be using LinkedList class of the Java collections framework.
Let us first initialize a linked list ll in which we want to find our element:-

LinkedList<Integer> ll = new LinkedList<>();

Remember, do not forget to import linked list package by writing this line of code in the header.

import java.util.LinkedList;

Let's populate this linked list with some data, this can be done using add(value) method of the LinkedList class:-

ll.add(4);
ll.add(2);
ll.add(6);
ll.add(1);
ll.add(7);
ll.add(9);

Our linked list will look like this:-

Let's give a variable name num to the number we want to search for:-

int num = 7;

Now, we will compare each element starting from the first element with num until we found num or until all the elements have been compared and we have reached the end of the list. This can be done by a for loop. We can access element at ith index in a linked list by using get(index) method of the LinkedList class:-

for(int i = 0; i < ll.size(); i++) {
            if(ll.get(i) == num) {
                System.out.println("Number found!");
                return;
            }
        }

We will print "Number found!", if we found the element, otherwise, we will print "Number not found!"

Have a look at the gif below, to see how it is happening:-

In the gif above, we are checking for num starting from the first element.
Here is the entire code with sample output:-

import java.util.LinkedList;

class main {
    private static void linearSearch(LinkedList<Integer> ll, int num) {
        for(int i = 0; i < ll.size(); i++) {
            if(ll.get(i) == num) {
                System.out.println("Number found!");
                return;
            }
        }
        
        // If number not found print this
        System.out.println("Number not found!");
    }
    public static void main(String args[]) {
        LinkedList<Integer> ll = new LinkedList<>();
        ll.add(4);
        ll.add(2);
        ll.add(6);
        ll.add(1);
        ll.add(7);
        ll.add(9);
        int num = 7;
        linearSearch(ll, num);
    }
}

Output:-

Number found!

Time Complexity

Best Case Complexity: If the number we want to find is the starting element of the list, we will find the element in just one step. So best case complexity will be O(1).
Worst Case Complexity: If the number we are finding is the last element of the list, or maybe the number doesn't exist at all in the list, in both cases, we will be traversing the entire list, giving us time complexity O(N).
Average Case Complexity: O(N)
For a detailed time complexity analysis, check out this article.

Space Complexity

As we are not storing any extra space during the program, space complexity will be O(1).

With this article at OpenGenus, you must have the complete idea of implementing Linear Search in Java.