StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There are two things here.</p> <p>The first is that your timings are unreliable as you haven't "warmed up" the code before each run. Java optimizes and compiles code as it is run so the first few times through it are much slower than later runs. You should run through your test loops a few hundred times, throw those results away and then do the timings.</p> <p>To answer the question though:</p> <p><code>LinkedList</code> is constant time no matter how long the list is but on each add it has to do a lot more work. It needs to create the wrapper object, insert it into the list, update references, etc.</p> <p>On the other hand <code>ArrayList</code> just sets a value into the array and then increments the size counter. Only if it needs to re-allocate the array does it then have to do a lot of work.</p> <p>Do the test adding new objects at the start and compare the results though and you will see things swing more back in the favor of linked lists as now <code>ArrayList</code> needs to shuffle up all the values every time.</p> <p>The cost to reallocate the arrays is also illustrated with your third test, by knowing the size in advance the ArrayList becomes even more efficient.</p> <p>Big O notation is helpful when discussing algorithms, but you need to understand what it actually means or it can be very misleading. It's talking about the Order of the operation, not how long it actually takes. <code>ArrayList</code> and <code>LinkedList</code> are both O(1) for most append insertions, <code>ArrayList</code> insertion is O(n) if it needs to reallocate.</p> <p>All O(1) says is that it still takes the same amount of time no matter how many objects are in the list. Add something to the end of a 10 item list, 100 item list, 10000 item list it still takes the same time.</p> <p>LinkedList though takes more time than ArrayList does - even though they still have the same O(1) order.</p> <p>In fact the speed difference is such that even if you look at adding to the start of the list where LinkedList is O(1) and ArrayList is O(n) ArrayList is still faster for small lists!</p> <p>To give some idea (this is just an example, don't try and take exact timings out of this!) then if the time taken to add for a LinkedList is L and the time for an ArrayList is A then the total time to do an add at the end is L*1, A*1. To add at the start is L*1, A*N.</p> <p>So if L/A < N then its actually faster to use an ArrayList even though just looking at the O characteristics you might think you are better using the LinkedList.</p> <p>(Linked list is also O(n) if you need random access reads, which can be a big factor too).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload