Java Top

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE

1. Overview

In this quick tutorial, we’ll find out how to determine if all the elements in a List are the same.

We’ll also look at the time complexity of each solution using Big O notation, giving us the worst case scenario.

2. Example

Let’s suppose we have the following 3 lists:

notAllEqualList = Arrays.asList("Jack", "James", "Sam", "James");
emptyList = Arrays.asList();
allEqualList = Arrays.asList("Jack", "Jack", "Jack", "Jack");

Our task is to propose different solutions that return true only for emptyList and allEqualList.

3. Basic Looping

First, it’s true that for all elements to be equal, they all have to equal the first element. Let’s take advantage of that in a loop:

public boolean verifyAllEqualUsingALoop(List<String> list) {
    for (String s : list) {
        if (!s.equals(list.get(0)))
            return false;
    }
    return true;
}

This is nice because, while the time complexity is O(n), it may often exit early.

4. HashSet

We can also use a HashSet since all its elements are distinct.  If we convert a List to a HashSet and the resulting size is less than or equal to 1, then we know that all elements in the list are equal:

public boolean verifyAllEqualUsingHashSet(List<String> list) {
    return new HashSet<String>(list).size() <= 1;
}

Converting a List to HashSet costs O(n) time while calling size takes O(1). Thus, we still have a total time complexity of O(n).

5. Collections API

Another solution is to use the frequency(Collection c, Object o) method of the Collections API. This method returns the number of elements in a Collection c matching an Object o.

So, if the frequency result is equal to the size of the list, we know that all the elements are equal:

public boolean verifyAllEqualUsingFrequency(List<String> list) {
    return list.isEmpty() || Collections.frequency(list, list.get(0)) == list.size();
}

Similar to the previous solutions, the time complexity is O(n) since internally, Collections.frequency() uses basic looping.

6. Streams

The Stream API in Java 8 gives us even more alternative ways of detecting whether all items in a list are equal.

6.1. distinct()

Let’s look at one particular solution making use of the distinct() method.

To verify if all the elements in a list are equal, we count the distinct elements of its stream:

public boolean verifyAllEqualUsingStream(List<String> list) {
    return list.stream()
      .distinct()
      .count() <= 1;
}

If the count of this stream is smaller or equal to 1, then all the elements are equal and we return true.

The total cost of the operation is O(n), which is the time taken to go through all the stream elements.

6.2. allMatch()

The Stream API’s allMatch() method provides a perfect solution to determine whether all elements of this stream match the provided predicate:

public boolean verifyAllEqualAnotherUsingStream(List<String> list) {
    return list.isEmpty() || list.stream()
      .allMatch(list.get(0)::equals);
}

Similar to the previous example using streams, this one has an O(n) time complexity, which is the time to traverse the whole stream.

7. Third-Party Libraries

If we’re stuck on an earlier version of Java and cannot use the Stream API, we can make use of third-party libraries such as Google Guava and Apache Commons.

Here, we have two solutions that are very much alike, iterating through a list of elements and matching it with the first element. Thus, we can easily calculate the time complexity to be O(n).

7.1. Maven Dependencies

To use either, we can add either guava or commons-collections4 respectively to our project:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.1</version>
</dependency>

7.2. Google Guava

In Google Guava, the static method Iterables.all() returns true if all elements in the list satisfy the predicate:

public boolean verifyAllEqualUsingGuava(List<String> list) {
    return Iterables.all(list, new Predicate<String>() {
        public boolean apply(String s) {
            return s.equals(list.get(0));
        }
    });
}

7.3. Apache Commons

Similarly, the Apache Commons library also provides a utility class IterableUtils with a set of static utility methods to operate on Iterable instances.

In particular, the static method IterableUtils.matchesAll() returns true if all elements in the list satisfy the predicate:

public boolean verifyAllEqualUsingApacheCommon(List<String> list) {
    return IterableUtils.matchesAll(list, new org.apache.commons.collections4.Predicate<String>() {
        public boolean evaluate(String s) {
            return s.equals(list.get(0));
        }
    });
}

8. Conclusion

In this article, we’ve learned different ways of verifying whether all elements in a List are equal starting with simple Java functionality and then showing alternative ways using the Stream API and the third-party libraries Google Guava and Apache Commons.

We have also learned that each of the solutions gives us the same time complexity of O(n). However, it’s up to us to choose the best one according to how and where it will be used.

And make sure to check out the complete set of samples over on GitHub.

Java bottom

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE