r/javahelp • u/LFrancis • 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!
20
u/xkompas Apr 30 '20
LinkedList is almost never the answer, see this answer on Stack Overflow and the following comment on memory footprint.
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.
3
u/fuqqboi_throwaway Apr 30 '20
I'm currently reading Programming Interviews Exposed and am on the part going over LinkedLists. They do mention it's mainly for C++ but I figure it's helpful to know. Should I not even bother remembering any of the java stuff related to it then since it would always be better to use ArrayList if I was in a Java interview anyway? And just focus on using LinkedList if it's a C++ interview?
1
u/lifeismeanttodie I suck at coding Apr 30 '20
Java and C++ user here.
I use an ArrayList a lot in Java, there's no need for a LinkedList unless you're doing a lot of insertions at the beginning (usually) or end. If you're trying to read information a lot after adding it somewhere (usually the case) then use an ArrayList. There's a vector class in C++ which is somewhat similar to an ArrayList in Java. There's no such thing as a LinkedList API in C++. You have to make your own using dynamic memory.
i.e.
struct Node {
Node* next;
int data;
}
Node* root;You can then easily use this struct and write methods that use the root (starting point) of the "LinkedList" and use it to perform operations. Anyway, I doubt you'd be forced to use one language solely in a programming interview, unless that's what you applied for. Personally, I stick to Java. No need to deal with memory thanks to GC.
2
Apr 30 '20
[removed] — view removed comment
2
u/lifeismeanttodie I suck at coding Apr 30 '20
(I'm not a pro either)
Somewhat yes, though the implementations vary.
https://stackoverflow.com/questions/26660618/simple-linked-list-vs-stllist-which-one-is-best
There's a std::forward_list which uses a singly linked list.
Bjarne himself said that vectors outperform linked lists.
1
u/omykronbr Apr 30 '20
Why would you bother remembering Java stuff for C++ and vice-versa?
Know that LinkedList in C++ is dumpster fire and in Java is a useful structure that is not a turd.
1
u/feral_claire Software Dev Apr 30 '20
In c++ I think you should be using std::Vector which is more or less the same as java ArrayList. I'm not super experienced with c++ though.
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.
5
Apr 30 '20
I'm struggling to remember the last time I used a LinkedList to be honest. ArrayList has always provided everything i need.
4
Apr 30 '20
For the specific java collections , generally you end up using ArrayList ; the data structure itself (a link list ) has uses - but probably not in the form of that collection.
3
u/Yithar Intermediate Brewer Apr 30 '20 edited May 21 '20
As stated, you should almost always use ArrayList in Java.
The only time I'd use a List is if I'm doing tail recursion and that List class in Scala is immutable:
https://stackoverflow.com/a/5130311/
2
u/itzNukeey Apr 30 '20
You can use List interface if you arent sure which implementation will you use but Linked List is almost never worth using
1
u/chubbasnorlax Apr 30 '20
If you make your own hash table, queue or stack you need a linked list. You can also use a linked list for making a tree or graph but there are preferred methods.
1
u/mrorok Apr 30 '20
LinkedList are only good when you need to do lots of insertions and deletions as they can insert and delete in O(1). Whereas an ArrayList does so in O(n) because you need shift the called because the underlying data structure is an array. So depending on what you need to do it may be useful
1
u/LouGarret76 May 01 '20
Well, As far as I know arraylist in java does not keep the sequence in which you add the items. LinkedList does. So if you want to read the items in the order you add them this is almost impossible with arraylist.
This is a key difference in my opinion.
1
u/nutrecht Lead Software Engineer / EU / 20+ YXP May 01 '20
Well, As far as I know arraylist in java does not keep the sequence in which you add the items.
That's plain wrong. You're confusing Sets with Lists.
1
u/LouGarret76 May 01 '20
You are correct. It looks like this is no longer the case in the current implementation of openjdk
2
u/LFrancis Apr 30 '20
Thanks for all the inputs, guys!
It seems to be the consensus that LinkedLists are more dynamic, whereas the ArrayLists are easier to manipulate and the general choice.