What are ArrayList's most performance friendly methods?

Question

I need to know which of the following ArrayList methods is the most performance friendly:

arrayList.add(index,Object)
arrayList.clear()

I'm in a situation where I have to choose to either add 1 element to the first position of a non empty arraylist or to just clear the whole arrayList. What would you choose?

They're really not alternatives to each other, so the comparison is meaningless... — Jon Skeet, May 19 '15 at 14:21
If you are adding an item to a specific index, removing from a specific index, or removing , they have a runtime of O(1). Think about it logically; you are giving it the **EXACT** location that it needs to go to in the first 2 cases. clear() would simply remove everything from the list, without discriminating. IMO this is an easily answerable question with small amount of research... — Evan Bechtol, May 19 '15 at 20:43

score 1 · Answer 1 · answered May 19 '15 at 14:35

1

It depends, how may items are there in the ArrayList. The worst case scenarion will be whne there a lot of items and the array list should be extended/shrinked. In this case the clear() method is the fastest. The other 2 involve System.arrayCopy the old array into new one.

answered May 19 '15 at 14:35

Anton Krosnev

3,964
1
21
37

So in that situation is it faster to use clear() instead of add(i,Object?) – ThanosFisherman May 19 '15 at 19:39
Yes, it is. I'm wondering how can you use clear instead of add? – Anton Krosnev May 20 '15 at 10:44
Well it's a long story. I'm in a situation where I have to choose to either add 1 element to the first position of a non empty arraylist or to just clear the whole arrayList. The guys above said that there is no difference on performance between those 2 actions since they both have O(n) complexity – ThanosFisherman May 20 '15 at 14:33
They are right, so am I :). O(n) means linear complexity., which both methods have. The difference `clear` has 1*n and `add` has 2*n if the underlying byte array has to be extended. – Anton Krosnev May 20 '15 at 14:49

score 0 · Accepted Answer · edited May 23 '17 at 10:26

0

Using Big-Oh notation, we can generalise the time complexity of methods within the ArrayList class.

For an ArrayList<> the following operations can be defined as follows:

get() has a time complexity of O(1)
add(), clear() and remove() all have a time complexity of O(n)
removeAll() has a time complexity of O(n^2)

From this, it can be seen that get() has the least time complexity and doesn't depend on the size of the list to how it performs. You should also note add(), clear() and remove() all run in linear time - which isn't as efficient but is not generally considered bad for performance.

According to the official documentation:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Why Big-Oh? (source)

Big O notation is a way of describing how quickly an algorithm will run given an arbitrary number of input parameters, which we'll call n. It is useful in computer science because different machines operate at different speeds, and simply saying that an algorithm takes 5 seconds doesn't tell you much because while you may be running a system with a 4.5 Ghz multi-core processor, I may be running a 15 year old, 800 Mhz system, which could take longer regardless of the algorithm.

So instead of specifying how fast an algorithm runs in terms of time, we say how fast it runs in terms of number of input parameters, or n.

By describing algorithms in this way, we are able to compare the speeds of algorithms without having to take into account the speed of the computer itself.

Sources: Big-Oh cheatsheet and this answer

edited May 23 '17 at 10:26

Community

1
1

answered May 19 '15 at 14:30

Ed Holloway-George

5,092
2
37
66

check my edited question. Which of those actions is more efficient? I'm mostly interested about add(i, object) vs clear() – ThanosFisherman May 19 '15 at 19:39
Just a few clarifications. You say that add() and clear() have the same complexity? So if you were to choose between add(1,Object) which adds a new object to position 0 and clear() which just clears everything. Which one would be the fastest? – ThanosFisherman May 19 '15 at 19:52
Please describe what you actually want to do. Those two methods do completely different things; why are you choosing between them? – Louis Wasserman May 19 '15 at 20:14
@ThanosF You asked about efficiency, but you seem to be confused by what that actually means. How fast something executes in practice depends on a whole variety of factors, if you want to see which is faster on your machine - create a test program and run it. – Ed Holloway-George May 19 '15 at 20:30
I have updated my answer to explain a bit better why measuring algorithms by time is flawed – Ed Holloway-George May 19 '15 at 20:35
thank you @EdGeorge that makes it clearer to my head. This is about an android phone so I may run some tests – ThanosFisherman May 19 '15 at 23:10
@LouisWasserman I'm in a situation where I have to choose to either add 1 element to the first position of a non empty arraylist or to just clear the whole arrayList. Don't ask how I got to that situation. long story. What would you choose? – ThanosFisherman May 19 '15 at 23:14
1

I would choose to hear the long story, but frankly I would expect no measurable difference in performance. – Louis Wasserman May 19 '15 at 23:18
The above comment is correct, you should see an extremely negligible difference in performance. For 'quicker' insertion and deletion, you could use a linked-list (`O(1)`) but at the cost of running at linear time when it comes to access elements of the list (`O(n)`) – Ed Holloway-George May 20 '15 at 08:34

What are ArrayList's most performance friendly methods?

2 Answers2

Why Big-Oh? (source)