Thursday, July 1, 2021

How to search a LinkedList in Java? Example

You can search an element inside LinkedList in Java by using indexOf() and lastIndexOf() methods. Though LinkedList doesn't support random search like ArrayList, you can still go through the list, check each element and find out whether it's an interesting element or not. Since java.util.LinkedList is an implementation of a doubly-linked list, these two methods are quite handy to search from either end e.g. indexOf() method starts the search from the head and returns an element's position while lastIndexOf() starts the search from the tail. Though the position is not relative to the ends, they are always calculated from the head. 

You can also use these two methods to find out duplicate elements. If an element has appeared twice in the linked list then the indexOf() and lastIndexOf() method will return different positions for that because it will be found at different positions from head and tail. For unique elements, both these methods will return the same position.

In this article, you will see examples of both indexOf() and lastIndexOf() methods to search a given element inside LinkedList. As I said before since LinkedList doesn't support random search and searching an element requires list traversal, which means time complexity will be O(n).

Also, If you are good in Java but lacks data structure and algorithm skills, I strongly suggest reading Data Structures and Algorithm Analysis in Java by Mark A. Wiess. It's a great book to build your foundation on data structure and algorithms using Java programming language.




Java Program to search element inside linked list

Here is our sample program to search a given node inside LinkedList in Java.  We first build our linked list of numbers and insert 1003 twice to make it a duplicate number. Later we have used the indexOf() and lastIndexOf() method to search for a duplicate element like 1003 and a unique element  1002 inside the linked list. 

From the result, you can see that indexOf() starts the search from the first element and that's why it found 1003 at the 3rd position, which is index 2. On the other hand, lastIndexOf() starts the search from the last element and that's why it found 1003 at 6th position i.e. index 5.

Here is a sample doubly linked list data structure :

How to search nodes inside LinkedList in Java


and here is our example to search duplicate and unique nodes inside LinkedList in Java.

import java.util.LinkedList;

/**
 * Java Program to search an element inside LinkedList.
 * LinkedList doesn't provide random search and 
 * time complexity of searching is O(n)
 * 
 * @author java67
 */

public class LinkedListSearch {

    public static void main(String args[]) {

       LinkedList<Integer> ints = new LinkedList<>();
        ints.add(1001);
        ints.add(1002);
        ints.add(1003);
        ints.add(1004);
        ints.add(1005);
        ints.add(1003);
        
        
        // let's search a duplicate element in linked list
        // for duplicate elements indexOf() and lastIndexOf() will
        // return different indexes.
        System.out.println("First index of 1003 is : " + ints.indexOf(1003));
        System.out.println("Last index of 1003 is : " + ints.lastIndexOf(1003));
        

        // let's search an element which is not appeared twice
        // for unique elements both indexOf() and lastIndexOf() will return
        // same position
        System.out.println("First index of 1002 is : " + ints.indexOf(1002));
        System.out.println("Last index of 1002 is : " + ints.lastIndexOf(1002));

    }

}

Output :
First index of 1003 is : 2
Last index of 1003 is : 5
First index of 1002 is : 1
Last index of 1002 is : 1

From the output, you can also see those duplicate nodes has two different positions returned by indexOf() and lastIndexOf() method while for unique elements both methods return the same index.

Btw, If you are good in Java but lacks data structure and algorithm skills, I strongly suggest reading Data Structures and Algorithm Analysis in Java by Mark A. Wiess. It's a great book to build your foundation on data structure and algorithms using Java programming language.


That's all about how to search an element inside LinkedList in Java. Searching an element requires traversing the list from either end, for example from head to tail or tail to head, which is what indexOf() and lastIndexOf() method does. You can use any of these methods to find out the index of a given element in Java, but just remember that if the element is repeated then both methods can return different indices.


If you like this tutorial and interested to learn more about linked list data structure in Java, You can also check the following Java LinkedList tutorials :
  • How to add elements at the first and last position in LinkedList in Java? [example]
  • The difference between LinkedList and ArrayList in Java? [answer]
  • Top 5 data structures from Java Collections framework? [article]
  • How to implement a linked list in Java? [solution]
  • How to find the middle node of the linked list in one pass? [solution]
  • How do you find the length of a singly linked list in Java? [solution]
  • What is the difference between a linked list and an array in Java? [answer]
  • How to find the first and last element from LinkedList in Java? [example]
  • How to check if the linked list contains a loop in Java? [solution]

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.