CODEWITHSUNDEEP
javaarraylistlinked-list
Sophie Sperner
Sophie Sperner

Reputation: 4556

Remove list elements - my approach for best performance in Java

If I need to remove elements in a list, will the following be better than using LinkedList:

int j = 0;
List list = new ArrayList(1000000);
...
// fill in the list code here
...
for (Iterator i = list.listIterator(); i.hasNext(); j++) {
    if (checkCondition) {
        i.remove();
        i = list.listIterator(j);
    }
}

?

LinkedList does "remove and add elements" more effectively than ArrayList, but LinkedList as a doubly-linked list needs more memory, since each element is wrapped as an Entry object. While I need a one-direction List interface, because I'm running over in ascending order of index.

Upvotes: 0

Views: 187

Answers (2)

Stephen C
Stephen C

Reputation: 719729

There is no simple answer to this:

  • It depends on what you are optimizing for. Do you care more about the time taken to perform the operations, or the space used by the lists?

  • It depends on how long the lists are.

  • It depends on the proportion of elements that you are removing from the lists.

  • It depends on the other things that you do to the list.

The chances are that one or more of these determining factors is not predictable up-front; i.e. you don't really know. So my advice would be to put this off for now; i.e. just pick one or the other based on gut feeling (or a coin toss). You can revisit the decision later, if you have a quantifiable performance problem in this area ... as demonstrated by cpu or memory usage profiling.

Upvotes: 0

Kristopher Micinski
Kristopher Micinski

Reputation: 7682

The answer is: it depends on the frequency and distribution of your add and removes. If you have to do only a single remove infrequently, then you might use a linked list. However, the main killer for an ArrayList over a LinkedList is constant time random access. You can't really do this with a normal linked list (however, look at a skip list for some inspiration..). Instead, if you're removing elements relative to other elements (where, you need to remove the next element) then you should use a linked list.

Upvotes: 2

Related Questions