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.

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

u/[deleted] 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.