ArrayList vs LinkedList

[roland]

Hi, I am adding a whole bunch of elements to a list, then iterating through it once.
-no contains
-no delete

LinkedList is order(1) for add
where as ArrayList is worst case order(n) when doubling its size (assuming it starts from the initial size)

Why is ArrayList still slightly faster for me?

Thanks,
roland

[Riven]

In general: the Big-O notation only states what the performance characteristics are for growth. Meaning that O(1) can be a lot slower than O(n) or even slower than O(n²), depending on size of the datastructure.



In this case: even LinkedList.add(0, value), which is the ideal case for LinkedList and the worst case for ArrayList, will only surpass ArrayList.add(0, value) in performance for 'really big lists'.

[roland]

Thanks for the reply, Riven

So ArrayList is the fastest of the Java collections, say for adding up to 1 million elements?

Games published by our own members! Check 'em out!

[Riven]

Thanks for the reply, Riven

So ArrayList is the fastest of the Java collections, say for adding up to 1 million elements?

I don't know. Measure it.

If you are adding elements at the end of the List, then ArrayList should always be used.

There are barely any cases where LinkedLists are a good idea.

[roland]

Linked Lists are doubly linked though right? why are they slower for adding at the end?
Edit: Oh, you mean because that's fast for ArrayList and ArrayList is faster than LinkedList

[Riven]

Linked Lists are doubly linked though right? why are they slower for adding at the end?

For every elements in the list, a new Object is created, which takes time. These objects add another level of indirection and are scattered all over the heap, resulting in lots of cache misses.

[roland]

Oh, I see
Thanks Riven!

[sproingie]

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

[Eli Delventhal]

Yup, I pretty much never use LinkedList. Always ArrayList. Plus index access is a lot nicer in my opinion than using Iterators.

[krasse]

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

I often use the ListIterator where you can remove an element while iterating through the list. It's convenient for objects that are removed suddenly like particles, actions, projectiles etc. This is probably bad to do with an ArrayList.
Its mainly for convenience though, I haven't tested the performance, but I still use it quite often

Games published by our own members! Check 'em out!

[Eli Delventhal]

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

I often use the ListIterator where you can remove an element while iterating through the list. It's convenient for objects that are removed suddenly like particles, actions, projectiles etc. This is probably bad to do with an ArrayList.
Its mainly for convenience though, I haven't tested the performance, but I still use it quite often

Just do 1 pass and remove all the deleted objects at once O(n).

[davedes]

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

I often use the ListIterator where you can remove an element while iterating through the list. It's convenient for objects that are removed suddenly like particles, actions, projectiles etc. This is probably bad to do with an ArrayList.
Its mainly for convenience though, I haven't tested the performance, but I still use it quite often

Just do 1 pass and remove all the deleted objects at once O(n).

Another way to do it

[krasse]

I used that method before I started messing around with LinkedLists. It looks so deceptively nice and clean when you do it that way

[princec]

So deceptively nice, clean and simple it's been at the core of my games for the last 10 years

Cas

[krasse]

Well, has anyone played your games?
It might just work nicely on your system

[R.D.]

I'm "cheating" this like so:

1   2   3   4   5

for(int i = (list.size() - 1); i >= 0; i--) {    if(updateDrop(delta, list.get(i))) {       releaseDrop(list, i);          } }

where releaseDrop removes the "drop" (strange rain system) and add it to the free list. Dunno if this is good but it works quite fast

[Eli Delventhal]

Yep, actually what Cas is doing is what I was referring to. The 1 pass can be the same thing as the update pass.

[Rorkien]

What is the issue with the ArrayList.remove() method? I noticed that nobody here uses it...

[matheus23]

The problem with the remove() method is, that everything, which is in the ArrayList's array AFTER that element to be deleted, will be needed to be shifted one element to the left. That makes the method kind of slow.
(but I don't acctually care... its fast enough, unless you spam delete Elements ?!?)

[ChristerSwahn]

Sounds like there would be some case for writing a new linked list implementation backed by one or a small set of arrays, now that the RAM cache misses is such a major performance factor. I.e. in order to avoid new object creation for each link, maintaining cache locality, and yet offer fast insertion and deletion.

[sproingie]

Scala's default IndexedSeq implementation, Vector, works pretty much like that, using a some sort of wide tree of array chunks.  Performance is pretty good.  Python's deque I think uses chunks.  Java's ArrayDeque uses a single array, it's just smart enough to adjust the starting index when deleting from the front instead of shifting everything over.