r/javahelp • • Apr 30 '20

ArrayList vs LinkedList

So I understand that for different situations, either the ArrayList API or the LinkedList API will be more efficient. So what should I look for in terms of design that will tell me which one of those structures is recommended? Is it more related to preference rather than specific uses?

Thanks!

17 Upvotes

22 comments sorted by

View all comments

13

u/feral_claire Software Dev Apr 30 '20

It's about specific user cases. However, almost always Arraylist will be the better choice. I can't remember a time that I've used LinkedList over ArrayList.

Arraylist is faster in most situations and uses way less memory.

The only time LinkedList might be faster is if you are adding or tracking elements at the beginning or middle of the List. Adding and removing from the end (like when you use add without an index) is very fast for ArrayList and is the most common easy to add elements to a List.

In general, always use ArrayList, and only if you are sure (and probably have benchmarks to prove it) should you switch to LinkedList.

1

u/OriginalError May 01 '20

Even ignoring the memory used, the biggest performance hit you actually see in Java (or C) are the cache misses. The elements in a linked list are *never* stored in a way that can be accessed in a timely (from a CPU cycle perspective) manner.

The *amount* of memory you use isn't the truly important part. You lose the most time from cache misses while you try to iterate through the linked list. The only advantage you'll ever see on linked lists is performance when deleting individual entries..

3

u/nutrecht Lead Software Engineer / EU / 20+ YXP May 01 '20

Even ignoring the memory used, the biggest performance hit you actually see in Java (or C) are the cache misses. The elements in a linked list are never stored in a way that can be accessed in a timely (from a CPU cycle perspective) manner.

Array lists store references to objects. While the references are 'next to each other' in the array, the actual objects are not. So you're still going to have cache misses.

Not saying there's no difference between them, but there's no guarantee the objects being pointed to are in the same cache page even with array lists.

1

u/OriginalError May 01 '20

I agree there is no guarantee (and most impls of ArrayList makes no promise of proximity) but the chance of memory proximity in an ArrayList is non-zero, and the chance that you miss a reference on a cache is 0. This ends up adding up significantly when comparing raw performance against LinkedLists, even for actions that would traditionally 'favor' LinkedList impls.

This is all anecdotal from years of enterprise C and Java, ymmv

3

u/nutrecht Lead Software Engineer / EU / 20+ YXP May 01 '20

I am not disagreeing with you, but the proximity of the actual objects will generally be the same whether you use an array list or linked list. The only difference, which still definitely matters, are the references themselves.

Working in C(++) gives you control over this, Java unfortunately doesn't.