Removing items from ArrayList in java 8

As we know ArrayList implementation of List interface store elements in an Array under the hood. Removing elements from ArrayList is a bit costly which is the order of n^2.

Let’s say I have a list of integers and I wanna remove all the nonprime number from the list.

Typically what we do is, use iterator and while loop to that. We can’t iteration/removing at the time with for each loop, because we would end of up with concurrent modification exception.

So-

Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (!isPrime(next)) {
                iterator.remove();
            }
        }

However, it has an order of n^2 time complexity. We are doing two things here, iterate the entire list, which is n here. In the array list when you have removed an element from an index, everything on the tail of the array has to be shoved up 1 space. That’s how remove method works. It has to copy array data on each remove call. That’s mean there are n copies. So it ends up being an order of n2.

The java8 has a removeIf method in the collection interface. For the ArrayList, it has an advance implementation which ends up being the order of n.

numbers.removeIf(integer -> !isPrime(integer));

here is the source code of removeIf method from Java8 api –

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // shift surviving elements left over the spaces left by removed elements
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s