How to search an element inside 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 its interested element or not. Since java.util.LinkedList is an implementation of doubly linked list, these two methods are quite handy to search from either ends e.g. indexOf() method start search from head and return an element's position while lastIndexOf() starts the search from tail. Though the position is not relative to ends, they are always calculated from head. You can also use these two methods to find out duplicate elements. If an element is appeared twice in linked list then indexOf() and lastIndexOf() method will return different positions for that because it will be found at different position 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 require list traversal, which means time complexity will be O(n).

Also, If you are good in Java but lacks data structure and algorithm skill, 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 algorithm 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 indexOf() and lastIndexOf() method to search for a duplicate element e.g. 1003 and a unique element  1002 inside linked list. From the result you can see that indexOf() start the search from the first element and that's why it found 1003 at 3rd position, which is index 2. On the other hand, lastIndexOf() starts the search from 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 node 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 returns same index.

BTW, if you are good in Java but lacks data structure and algorithm skill, 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 algorithm using Java programming language.

searching element on linked list in Java


That's all about how to search an element inside LinkedList in Java. Searching an element require traversing the list from either end e.g. 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 method 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 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 linked list in Java? [solution]
  • How to find middle node of linked list in one pass? [solution]
  • How do you find the length of singly linked list in Java? [solution]
  • What is the difference between linked list and array in Java? [answer]
  • How to find first and last element from LinkedList in Java? [example]
  • How to check if linked list contains loop in Java? [solution]


Recommended books for Java Beginners :
  1. Data Structures and Algorithm Analysis in Java by Mark A. Wiess [see here]
  2. Head First Java 2nd Edition by Kathy Sierra [see here]
  3. Core Java Volume 1 and 2, 9th Edition by Cay S. Horstmann [see here]


No comments:

Post a Comment