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
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 –
- 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.
- 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.
- 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
Employeeclass has three main attributes –
ArrayListof Employees is created, named
employeeList, to which 5
Employeeobjects are added.
- Using iterator-based iteration in a for-loop the individual
employeeListare 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.
employeeListis 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, 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 PredicateClick to read detailed tutorial on Predicate Functional Interfaces.)
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)
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
(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.)
- 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
employeeListwith the input
(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
Employeeobjects from the employeeList if the employee’s age is greater than 30.
Employeeobjects remaining in 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
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
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.
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
Map interfaces respectively. Specifically, the article on
List interface will cover the newly added
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.