Searching in linked list

In a recent post, we have seen how to add, remove, and retrieve the element from LinkedList in java. In this post, we will know how to search in linked list. We have some methods that help us to search an element in linked list. Let’s see how to perform Searching in linked list.

As we know Java LinkedList doesn’t support random access like array and ArrayList. When we perform searching in Linked List, it checks each element which means time complexity will be O(n). We can search in LinkedList by use of indexOf(), lastIndexOf(), contain() or manual way.  Let’s perform Searching in linked list

1. indexOf(Object obj) method

The indexOf() method is used to find the index of the particular object. This method takes an argument and starts the search from the head and moves towards the tail. If an object finds, then it returns the index value else it returns -1. If  a LinkedList contains a duplicate object it returns the index value of the first occurrence.

public int indexOf(Object o)

accessModifier, this method is public, so it is accessible everywhere.
returnType, it returns int value.
o, the object which we want to search in LinkedList.

import java.util.LinkedList;

public class ExampleOfLinkedList
{  
    public static void main(String args[])
    {
    	LinkedList<String> data = new LinkedList<String>();
    	data.add("Java");
    	data.add("Goal");
    	data.add(".com");
    	data.add("Java");
    	data.add("Learning");
    	data.add("Website");
    	
    	int index = data.indexOf("Java");
    	if(index != -1)
    	{
    		System.out.println("Element exists at index: "+ index);
    	}
    	else
    	{
    		System.out.println("Element not found");
    	}
    }  
}  

Output: Element exists at index: 0

AS you can see in above example. The indexOf() method returned the index 0, even the same object presented at index 3.  

2.  lastIndexOf(Obejct obj) method

The lastIndexOf(Object obj) method is also used to find the index value of the given object. This method also takes the parameter but it starts the search from the tail of LinkedList.

public int lastIndexOf(Object o)

accessModifier, this method is public, so it is accessible everywhere.
returnType, it returns int value.
o, the object which we want to search in LinkedList.

import java.util.LinkedList;

public class ExampleOfLinkedList
{  
    public static void main(String args[])
    {
    	LinkedList<String> data = new LinkedList<String>();
    	data.add("Java");
    	data.add("Goal");
    	data.add(".com");
    	data.add("Java");
    	data.add("Learning");
    	data.add("Website");
    	
    	int index = data.lastIndexOf("Java");
    	if(index != -1)
    	{
    		System.out.println("Element exists at index: "+ index);
    	}
    	else
    	{
    		System.out.println("Element not found");
    	}
    }  
}  

Output: Element exists at index: 3

3. Contains(Object o) method

The contains(Object o) method is used to check whether the object o is present in LinkedList or not. It returns a boolean value. If an element exists, then it returns true otherwise false.

public boolean contains(Object o)

accessModifier, this method is public, so it is accessible everywhere.
returnType, it returns boolean value.
o, the object which we want to search in LinkedList.

import java.util.LinkedList;

public class ExampleOfLinkedList
{  
    public static void main(String args[])
    {
    	LinkedList<String> data = new LinkedList<String>();
    	data.add("Java");
    	data.add("Goal");
    	data.add(".com");
    	data.add("Java");
    	data.add("Learning");
    	data.add("Website");
    	
    	boolean isExists = data.contains("Java");
    	if(isExists)
    	{
    		System.out.println("Element exists");
    	}
    	else
    	{
    		System.out.println("Element not found");
    	}
    }  
}  

Output: Element exists

By manual way

We can search the object by a manual way. We can traverse the LinkedList and match the element in LinkedList.

import java.util.LinkedList;

public class ExampleOfLinkedList
{  
    public static void main(String args[])
    {
    	LinkedList<String> data = new LinkedList<String>();
    	data.add("Java");
    	data.add("Goal");
    	data.add(".com");
    	data.add("Java");
    	data.add("Learning");
    	data.add("Website");
    	
    	for(int i = 0; i < data.size(); i++)
    	{
    		if(data.get(i).equals("Java"))
    			System.out.println("Element exists index: "+ i);
    	}
    }
    	
}  

Output: Element exists index: 0
Element exists index: 3