Java 8 – Collection.removeIf method tutorial with examples

This is the 2nd article, of a 4 part article series, covering the important enhancements introduced in Collections API in Java 8. The previous article, 1st part of the series(read hereRead Part 1-Iterable.forEach,Iterator.remove methods tutorial), explained the enhancements introduced in Iterable and Iterator interfaces in Java 8.

In this part 2 of 4, I will be explaining the new default method removeIf() which has been added to the java.util.Collection interface. To understand the intent with which this method has been introduced, we will start off with looking at how element removal from a Collection worked until Java 7. We will then look at the new Collection.removeIf() method introduced in Java 8 along with a working example showing its usage. Along with seeing the code for the two ways of achieving conditional element removal, we will also understand the performance improvement which Java 8’s new removeIf() method delivers as compared to the Java 7 style of accomplishing the same.

Conditional removal from a Collection before Java 8
Until Java 7, iterating a Collection and removing elements from it based on a given condition involved the following steps –

  1. Creating a for loop for iterating over the collection elements. The newer for..each loop could not be used here as it only allows reading the elements in a collection without the possibility of removing them. So, one will need to use the standard long-form for-loop.
  2. To remove an element from a collection required access to its iterator. So, one had to use the Collection’s iterator to access the elements as well as handle the loop terminating condition.
  3. Examine each element, as we iterate over the collection, and based on the given condition either remove the current element being examined or let it remain in the collection.

Let’s see a sample program showing how conditional removal from a Collection could be done till Java 7. The Collection we will use will be an ArrayList, and it will contain objects of type Employee.

Java 7 code showing Collection handling using Iterator
//Employee.java(POJO class)
package com.javabrahman.java8;
public class Employee {
  private String name;
  private Integer age;
  private Double salary;
  public Employee(String name, Integer age, Double salary) {
    this.name = name;
    this.age = age;
    this.salary = salary;
  }
  public String toString(){
    return "Employee Name:"+this.name
        +"  Age:"+this.age
        +"  Salary:"+this.salary;
  }
//getters and setters for name, age and salary go here
//standard equals() and hashcode() code go here
}

//CollectionRemoveIfExample.java
com.javabrahman.java8.collections;
import com.javabrahman.java8.Employee;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class CollectionRemoveIfExample {
  static List<Employee> employeeList = new ArrayList<>();
  public static void main(String[] args) {
    employeeList.add(new Employee("Tom Jones", 45, 7000.00));
    employeeList.add(new Employee("Harry Major", 25, 10000.00));
    employeeList.add(new Employee("Ethan Hardy", 65, 8000.00));
    employeeList.add(new Employee("Nancy Smith", 22, 12000.00));
    employeeList.add(new Employee("Deborah Sprightly", 29, 9000.00));
    for(Iterator empIterator=employeeList.iterator();
        empIterator.hasNext();) {
      Employee emp = empIterator.next();
      if(emp.getAge() > 30){
        empIterator.remove();
      }
    }
    System.out.println("Employees below the age of 30");
        employeeList.forEach(System.out::println);
  }
}
 OUTPUT of the above code
Employees below the age of 30
Employee Name: Harry Major   Age:25   Salary:10000.0
Employee Name: Nancy Smith   Age:22   Salary:12000.0
Employee Name: Deborah Sprightly   Age:29   Salary:9000.0
Explanation of the code

  • Employee class has three main attributes – name, age and salary.
  • An ArrayList of Employees is created, named employeeList, to which 5 Employee objects are added.
  • Using iterator-based iteration in a for-loop the individual Employee objects in employeeList are visited. All employees aged above 30 years are removed using the Iterator.remove() method. The code for iteration and conditional removal of employee objects is in red color.
  • The employeeList is printed post the conditional removal and, as expected, the output consists of 3 employees aged below 30 years.

Time Complexity of removal using for loop and iterator in specific case of an ArrayList
We used a for-loop with an iterator to iterate over the ArrayList. A single loop implies a time complexity of O(n).

Further, as an ArrayList stores elements in sequential storage in memory, the removal of an element from the middle implies that all the elements to the right of(or after) the removed element have to be moved 1 place each towards the left. This needs to be done in order to fill up the empty space left by the removed element. The movement of elements for these place would further require time proportional to O(m).

Since we potentially will need to move the elements for every removal, the total complexity across all the removals equals O(n) X O(m) ~ O(n2).

Conditional Removal from a Collection using Java 8’s Collection.removeIf() default method
Java 8 has added support for functional programming features. One of the important in-built functional interface is Predicate. Predicate, or a condition checking function, checks the given input for a given condition and returns a boolean result for the same indicating whether the condition was met or not.
(Note – If you haven’t worked with Java 8’s Predicate Functional Interface before then you can read the tutorial on Predicate hereClick to read detailed tutorial on Predicate Functional Interfaces.)

Java 8’s java.util.Collection interface has a new default method added to it named removeIf(). This method is defined with the following signature –

default boolean removeIf(Predicate<? super E> filter)

Where,
     – filter is an instance of a Predicate Functional Interface.

Collection.removeIf() method works by applying the condition provided in the Predicate instance to all the elements in the Collection on which it is invoked. The elements which satisfy the condition are retained while the remaining are removed from the Collection.

Let us now see how the code for doing the same operation we did above, that of filtering out employees if their age > 30, would look using the new Collection.removeIf method.
(Note – I am leaving out the code for Employee class, along with package and import declarations below as they remain the same as Java 7 code above.)

Java 8 code showing Collection.removeIf() usage
public class CollectionRemoveIfExample {
  static List<Employee> employeeList = new ArrayList<>();
  public static void main(String[] args) {
    employeeList.add(new Employee("Tom Jones", 45, 7000.00));
    employeeList.add(new Employee("Harry Major", 25, 10000.00));
    employeeList.add(new Employee("Ethan Hardy", 65, 8000.00));
    employeeList.add(new Employee("Nancy Smith", 22, 12000.00));
    employeeList.add(new Employee("Deborah Sprightly", 29, 9000.00));
    employeeList.removeIf((Employee emp) -> emp.getAge() > = 30);
    System.out.println("Employees below the age of 30");
    employeeList.forEach(System.out::println);
  }
}
 OUTPUT of the above code
Employees below the age of 30
Employee Name: Harry Major   Age:25   Salary:10000.0
Employee Name: Nancy Smith   Age:22   Salary:12000.0
Employee Name: Deborah Sprightly   Age:29   Salary:9000.0
Explanation of the code

  • The code above is same as the earlier iterator-based code except the single line in green color which has replaced the red colored code.
  • removeIf() method is invoked on employeeList with the input Predicate being (Employee emp) -> emp.getAge() > 30.
  • The input predicate, expressed using its equivalent lambda expressionRead Java 8 Lambda Expressions Tutorial, specifies exactly the same condition used in iterator based code – to remove Employee objects from the employeeList if the employee’s age is greater than 30.
  • Employee objects remaining in the employeeList post the removeIf() method invocation are then printed and, as expected, 3 employees are printed.
  • Notice that instead of 6 lines of iterator-based code of Java 7, we wrote only a single line Java 8 code using the Collection.removeIf() method.

Time Complexity of removal from an ArrayList using Collection.removeIf()
Collection traversal using an iterator was not designed only for removals. The programmer could do whatever they wanted with the Collection elements as they iterated over it. Collection.removeIf() method, on the other hand, is specifically meant for removals. Knowing the specificity of purpose of the removeIf() method, and the need to remove the overhead of shifting of ArrayList elements after a removal from the midde, Java designers overrode the default implementation of removeIf() in the ArrayList (possible as ArrayList implements Collection), and optimize the code while doing so to achieve a time complexity of O(n).

O(n2) Vs O(n) – Big performance improvement
Removal from an ArrayList using an iterator has time complexity of O(n2), while the same operation when performed using Java 8’s new Collection.removeIf() method has a complexity of O(n). This is a significant improvement in performance. If an application has large-sized ArrayLists then using the Collection.removeIf() method will result in the application being speeded up by an order of complexity, making the choice of the new method over the earlier one a no-brainer in such scenarios.

Conclusion
In this 2nd part of the 4-part Java 8 Collection Enhancements Series, we looked at how conditional removals from a java.util.Collection was done prior to Java 8. We then saw how Java 8’s new Collection.removeIf() method uses a Predicate instance to do the same conditional removal operation in significantly less time [O(n) vs O(n2)] and with concise, single-line code.

In the remaining 2 articles of the series, we will be looking at the important changes introduced in List and Map interfaces respectively. Specifically, the article on List interface will cover the newly added sort() and replaceAll() methods, while the article on Map interface will explain the new methods introduced in Java 8 which allow easier handling of multi-value maps.

 

Digiprove sealCopyright © 2014-2016 JavaBrahman.com, all rights reserved.