DZone
Java Zone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Java Zone > Removing Items From ArrayLists in Java 8

Removing Items From ArrayLists in Java 8

Can Java 8 beat the usual cost of removing items from an ArrayList? Read on to find out and for some source code.

A N M Bazlur Rahman user avatar by
A N M Bazlur Rahman
CORE ·
Oct. 08, 16 · Java Zone · Tutorial
Like (30)
Save
Tweet
44.88K Views

Join the DZone community and get the full member experience.

Join For Free

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

Let’s say I have a list of integers and I want to remove all the non-prime numbers from the list.

Typically, what we do is use iterator and a while loop to do that. We can’t iterate/remove at the same time with for each loops — we would end up with concurrent modification exceptions.

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 complexity. We are doing two things here — iterating the entire list, which is n here. In the ArrayList, when you remove an element from an index, everything on the tail of the array has to be shoved up one space. That’s how the remove method works. It has to copy array data on each remove call. That means there are n copies. So it ends up being an order of n^2.

Java 8 has a removeIf method in the collection interface. For the ArrayList, it has an advanced implementation, which ends up being to the order of n.

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

Here is the source code of the removeIf method from the Java 8 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;
    }

Data structure Java (programming language)

Published at DZone with permission of A N M Bazlur Rahman, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Implementing Microservices Architectures
  • When Disaster Strikes: Production Troubleshooting
  • Getting Started With RSocket Kotlin
  • Chopping the Monolith: The Demo

Comments

Java Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • MVB Program
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends:

DZone.com is powered by 

AnswerHub logo