Removing every other element in an array list

user_12335617 0
Viewed 2474
for(int i = 0; i < points.size(); i = i+lines) {
    points.remove(i);
}

The idea here is that a user can either remove every other space or every third space or every fourth space .. And so forth, of an array list by entering an int "line" that will skip the spaces. However, I realize the list gets smaller each time messing with the skip value. How do I account for this? I'm using the ArrayList library from java so don't have the option of just adding a method in the array list class. Any help would be greatly appreciated.

arraylist java
4 Answers

I've perfomed a benchmark of all the answers proposed to this question so far.

For an ArrayList with ~100K elements (each a string), the results are as follows:

removeUsingRemoveAll  took 15018 milliseconds (sleepToken)
removeUsingIter       took   216 milliseconds (Arvind Kumar Avinash)
removeFromEnd         took    94 milliseconds (WJS)

Removing an element from an ArrayList is an Θ(n) operation, as it has to shift all remaining elements in the array to the left (i.e. it's slow!). WJS's suggestion of removing elements from the end of the list first, appears to be the fastest (inplace) method proposed so far.

However, for this problem, I'd highly suggest considering alternative data structures such as a LinkedList, which is designed to make removing (or adding) elements in the middle of the list fast. Another alternative, if you have sufficient memory, is to build up the results in a separate list rather than trying to modify the list inplace:

removeUsingIterLinked took    12 milliseconds
removeUsingSecondList took     3 milliseconds (sleepToken with WJS's comment)
user_17032160

Use an Iterator with a counter e.g. the following code will remove every other (i.e. every 2nd) element (starting with index, 0):

Iterator<Point> itr = points.iterator();
int i = 0;
while(itr.hasNext()) {
    itr.next();
    if(i % 2 == 0) {
        itr.remove();
    }
    i++;
}

Here, I've used i as a counter.

Similarly, you can use the condition, i % 3 == 0 to remove every 3rd element (starting with index, 0).

user_108195730

Here is a different approach. Simply start from the end and remove in reverse. That way you won't mess up the index synchronization. To guarantee that removal starts with the second item from the front, ensure you start with the last odd index to begin with. That would be list.size()&~1 - 1. If size is 10, you will start with 9. If size is 11 you will start with 9

List<Integer> list = IntStream.rangeClosed(1,11)
    .boxed().collect(Collectors.toList());

for(int i = (list.size()&~1)-1; i>=0; i-=2) {
            list.remove(i);
}
System.out.println(list);

Prints

[1, 3, 5, 7, 9, 11]
user_15525340

You could add them to a new ArrayList and then remove all elements after iterating.

You could set count to remove every countth element.

import java.util.ArrayList;

public class Test {

    static ArrayList<String> test = new ArrayList<String>();

    public static void main(String[] args) {
        test.add("a");
        test.add("b");
        test.add("c");
        test.add("d");
        test.add("e");

        ArrayList<String> toRemove = new ArrayList<String>();
        int count = 2;

        for (int i = 0; i < test.size(); i++) {
            if (i % count == 0) {
                toRemove.add(test.get(i));
            }
        }

        test.removeAll(toRemove);

        System.out.print(test);
    }
}
user_44590690
Related