Linked List- contains() and containsAll() methods in Java

contains() method checks whether the specified element is present in the list or not, and the containsAll() method checks whether all elements of the specified collection are present in the list. This post will discuss contains and containsAll methods implemented in the Linked List class.

public boolean contains(Object o)

• What does it do? It will take an Object ( String, Integer, etc. ) in the argument and determine whether the passed object is present in the linked list or not.
• What does it return? It will return true or false based on whether the passed object is present in the linked list or not.

Code example

So, let us take a linked list consisting of various types of objects ( String and Integer ) and then will try to use contains() method on the list.

import java.util.LinkedList;

public class Codekru {

	public static void main(String[] args) {
		LinkedList<Object> linkedList = new LinkedList<>();

		// adding some objects in the linked list
		linkedList.add("hi");
		linkedList.add("codekru");
		linkedList.add(4);

		// using contains method to check if the list contains the elements passed in the
		// arguments of the method or not
		System.out.println("does linked list conatins 'hi' -> " + linkedList.contains("hi"));
		System.out.println("does linked list conatins 5 -> " + linkedList.contains(5));
		System.out.println("does linked list conatins 'codekru' -> " + linkedList.contains("codekru"));
	}
}

Output –

does linked list conatins 'hi' -> true
does linked list conatins 5 -> false
does linked list conatins 'codekru' -> true

The internal implementation of the contains(Object o) method

Well, under the hood, contains() method uses the indexOf method, and if the output of the indexOf() method is greater than or equal to zero, it will return true or else false.

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

The time complexity of the contains(Object o) method

• Best case scenario – Best case time complexity would be O(1) when the element is present at the first location.
• Worst case scenario – Worst case time complexity would be O(n) when the element is present at the last index of the linked list or not present at all.

So, the average time complexity of the contains(Object o) method would be O(n).

public boolean containsAll(Collection c)

• What does it do? It will take a collection as an argument and iterates over it to see whether each element of the Collection is present in the linked list or not.
• What does it return? It will return true or false based on whether all of the elements in the collection are present in the linked list or not.
• What is Collection means here? The collection is an interface in Java that many classes implement. We can pass the object of any of those classes as an argument of the contains() method.

Code Example

We will be using the object of the Stack class to be passed in the argument as the Stack class implements the Collection interface.

import java.util.LinkedList;
import java.util.Stack;

public class Codekru {

	public static void main(String[] args) {
		LinkedList<Object> linkedList = new LinkedList<>();

		// adding some objects in the linked list
		linkedList.add("hi");
		linkedList.add("codekru");
		linkedList.add(4);

		Stack<Object> stack = new Stack<Object>();

		// adding elements in stack
		stack.push("codekru");
		stack.push("hi");

		System.out.println("does stack has all elements present in the linked list? - " + linkedList.containsAll(stack));

		stack.push("hello"); // adding a new element 

		System.out.println("does stack has all elements present in the linked list? - " + linkedList.containsAll(stack));

	}
}

Output –

does stack has all elements present in the linked list? - true
does stack has all elements present in the linked list? - false

The internal implementation of containsAll(Collection C) method

The containsAll() method iterates over the collection passed in the argument. In each iteration, it uses the contains() method to see whether a particular element is present in the linked list or not.

    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

Time Complexity of containsAll(Collection C) method

• Best Case Time Complexity – Best case scenario will be when there is only one element present in the collection and that element is present at the first location in the linked list, then its time complexity would be O(1).
• Worst Case Time Complexity – Worst case time complexity will be O(m*n), where m is the size of the collection passed in the argument and n is the size of the linked list. It will happen when the collection’s element is not present in the linked list or present at the last index of the linked list.

So, the average time complexity of the containsAll(Collection C) would be O(m*n), where m is the size of the collection passed in the argument and n is the size of the linked list.

contains vs containsAll() method

• containsAll() method internally uses the contains() method to check whether all elements are present in the list or not.
• contains() method checks for the presence of only a single element, whereas the containsAll() checks whether all the elements of a collection are present in the list.
• The time complexity of contains() method is O(n), whereas the time complexity of the containsAll() method is O(n*m).

The What If scenarios

Q – What if we use the contains() method on a null linked list?

Here, we will get a NullPointerException as illustrated by the below program.

public class Codekru {

	public static void main(String[] args) {
		LinkedList<Object> linkedList = new LinkedList<>();

		linkedList = null;
		
		linkedList.contains(4);

	}
}

Output –

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.LinkedList.contains(Object)" because "linkedList" is null

Q – What if we use the contains() with an element of a different data type than the linked list elements?

Here, our linked list will be made up of strings, and we will use an integer as an argument in the contains() method.

public class Codekru {

	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>();

		linkedList.add("Codekru");

		System.out.println("Does linked list contains 4: " + linkedList.contains(4));

	}
}

Output –

Does linked list contains 4: false

We can see that it returned false without any error.

Please visit this link to learn more about the linked list class and its methods.

We hope that you have liked this article. If you have any doubts or concerns, please feel free to write us in the comments or mail us at admin@codekru.com.