Gỡ bỏ phần tử khỏi ArrayList một cách tối ưu

Việc gỡ bỏ phần tử khỏi ArrayList trong Java có độ phức tạp thuật toán là O(n^2) 

Khi tôi có một danh sách các số ngẫu nhiên được lưu dưới dạng ArrayList, và tôi muốn bỏ đi tất cả các hợp số khỏi danh sách (số không phải là số nguyên tố) thì thông thường, chúng ta sẽ dử dụng vòng lặp while-do và một Iterator để duyệt tuần tự qua ArrayList đó. Và có 2 vấn đề phát sinh ở đây:

Thứ nhất, bản chất của việc gỡ một phần tử khỏi ArrayList là: duyệt đến vị trí của phần tử đó, gỡ bỏ nó ra, sau đó 'dịch' tất cả các phần tử trước nó lên một vị trí. Quá trình này được đánh giá là có độ phức tạp thuật toán mức O(n^2) - chậm so với LinkedList

Thứ hai, chúng ta không thể vừa duyệt, vừa xóa ArrayList đó, hay nói một cách tổng quát hơn, vừa duyệt vừa xóa một object đã vô tình làm ta rơi vào Concurrent Modification Exception. (Một ví dụ dễ hình dung hơn của Concurrent Modification Exception đó là một cái ghế không thể có 2 người ngồi vào cùng lúc được).

Để khắc phục 2 vấn đề này, Java 8 đã bổ sung method removeIf() trong interface Collection. Nhờ removeIf(), việc gỡ bỏ phần tử khỏi ArrayList sẽ chỉ nằm ở mức O(n).

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

Và đây là phần implement đầy đủ của removeIf() trong 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;
    }

Tham khảo bài viết gốc tại Dzone