Choosing between ArrayList and LinkedList - JEP Cafe #20

Подписаться 179 тыс.

Просмотров 20 тыс.

50% 1

How you can choose between ArrayList and LinkedList for your application: the full tutorial.
The Collections Framework offers two implementation for the List interface: ArrayList and LinkedList. How can you choose the best one for your application? This JEP Café shows you how you can bench each implementation, and the amount of memory they consume.
⎯⎯⎯⎯⎯⎯ Chapters ⎯⎯⎯⎯⎯⎯
0:00 Intro
0:57 Choosing the best implementation for your use case
1:53 Choosing the most common operations for benchmark
2:43 Can you apply the O(n) complexity to your use case?
5:00 Using JMH to run your benchmarks
6:25 Reading elements from the beginning and the end of a list
9:03 Reading elements from the middle of a list
11:01 Introducing pointer chasing
12:51 Benching the impact of pointer chasing on LinkedList
14:27 Iterating over a list with an index or an Iterator
16:48 Creating an array-based list to speed up your iterations
17:53 Wrapping up pointer chasing
18:20 ArrayList caveats: insertion, deletion, and resizing
20:01 Benching insertion and resizing for ArrayList
21:48 Comparing inserting and adding for ArrayList and LinkedList
23:25 Comparing the memory consumption of ArrayList and LinkedList
26:27 Reducing your memory footprint by using trimToSize()
28:08 Wrapping up performances and memory consumption
30:26 Outro
⎯⎯⎯⎯⎯⎯ Resources ⎯⎯⎯⎯⎯⎯
◦ JMH on GitHub, with doc and samples ➱ github.com/openjdk/jmh
◦ Alexey Shipilev's blog ➱ shipilev.net/
◦ Alexey Shipilev on JMH ➱ • Java Microbenchmark Ha...
◦ Java Object Layout on GitHub, with doc and samples ➱ github.com/openjdk/jol
◦ Don Raab on Java Object Layout ➱ betterprogramming.pub/sweatin...
◦ Dev.java ➱ dev.java
◦ Inside.java ➱ inside.java
◦ JDK 21 ➱ openjdk.org/projects/jdk/21
◦ OpenJDK ➱ openjdk.org
◦ Oracle Java ➱ www.oracle.com/java/
Tags: #Java #Java21 #OpenJDK #JDK #JDK21 #Collection #JEPCafe #insidejava

Наука

Опубликовано:

27 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 65

@JosePaumard 9 месяцев назад

Thanks to everybody who were there for Premiere, it was great chatting with you!

@AleksandarT10 9 месяцев назад

Great video I think we need some more similar videos on sets and maps. Keep up the good work

@JosePaumard 9 месяцев назад

Thank you!

@danthe1st 9 месяцев назад

Thank you for making the "measure, don't guess" principle clear once more and telling everyone to use JMH

@JosePaumard 9 месяцев назад

You are welcome!

@TheTubeYou251 9 месяцев назад

Nice video! I think ArrayDeque would have deserved a mention. It‘s basically an variant of ArrayList that outperforms LinkedList in those queue operations like adding to the front. So even if LinkedList would be better for them as ArrayList, there is no reason to use it, because you can use ArrayDeque instead.

@user-no3jj5ei9o 9 месяцев назад

He drinks coffee so timely that its almost synced with the video !! #Coffee-drinking-skill And off course, with great content.

@JosePaumard 9 месяцев назад

😄Maybe it's the opposite?

@m77mo65 9 месяцев назад

More like this please. Thanks for this video

@JosePaumard 9 месяцев назад

Thank you, glad you liked it!

8 месяцев назад

Great video, very clear and concise delivery. I like these small breaks giving audience time to digest the information. This is what Java community needs, much appreciated!

@JosePaumard 8 месяцев назад

Thank you, I really appreciate it!

@marcteufel8348 9 месяцев назад

I love the JEPCafe and I esspecially love your french styled englisch ! Keep on doing this series, its so great and informative ! Thumbs up!

@JosePaumard 9 месяцев назад

Thank you! I guess my French accent is incidental though... 😄

@cesar.vasconcelos 9 месяцев назад

Great video and what a awesome professor! I have read Core Java from Horstmann which is a great book btw but Mr. Paumard’s analysis in this video goes even further than what is presented in the book chapter regarding the comparison between ArrayList and LinkedList. I always learn some something new with Mr. Paumard videos (specially Stream API videos). This JEP was really good. Thanks, José.

@JosePaumard 9 месяцев назад

Thank you for your kind words, I really appreciate them!

@enocholisa 9 месяцев назад

Same here. The Stream API course on Pluralsight helped me really understand the map, filter, and reduce operations better.

@KhanhVuy 9 месяцев назад

This video is so great. Thanks for making this, Mr. Paumard. I like watching your videos.

@JosePaumard 9 месяцев назад

Thank you!

@poojapatole3573 9 месяцев назад

This was enlightening. Thank you

@svalyavasvalyava9867 9 месяцев назад

awesome explanation, thank you ☺️

@jorgericardosoares2790 8 месяцев назад

Great explanation 😊

@matdryz 9 месяцев назад

Because of the way processors work (i.e. how pages are cached in the processor) you can't really go wrong with an ArrayList, but let's see what we learn from the video

@pavlg3944 9 месяцев назад

There are many things to consider regarding the usage of Array list, the array list is an API and not just an array of objects, you have to consider memory consumption (and CPU capabilities), time complexity when dispatching (contains and remove by value), sorted cases and concurrency, those must be in our minds before implementing a data structure.

@pavlg3944 9 месяцев назад

One famous scenario, you can go wrong with an ArrayList by simply trying to structurally modify the array from another thread while iterating over its elements, this is known as ConcurrentModificationException, the ConcurrentModificationException prevents the race conditions.

@matdryz 9 месяцев назад

@@pavlg3944 same would happen with LinkedList afair, and the title of the video is "Choosing between ArrayList and LinkedList(...)" and I was referring to choosing between one of those.

@matdryz 9 месяцев назад

@@pavlg3944 in case of java it's quite obvious, we're talking about a specific implementation java.util.ArrayList, no one is implementing anything, it's just about choosing implementation and not the API that is quite similar (if not the same) as it is for LinkedList since both implement List interface. There may be some cases when LinkedList is better, but it's a quite small subset of cases imho (e.g. if you remove elements from the list very often and don't iterate through it too often) that's why I'd say in vast majority of cases defaulting to arraylist will do the trick, and even if the LinkedList is a better solution for a particular case, the benefits won't be that big

@JosePaumard 9 месяцев назад

@@pavlg3944 Hmm not quite. You can trigger the ConcurrentModificationException with only one thread.

@Speiger 9 месяцев назад

@José Paumard To continue the argument here. My point i am making that a hashmap/set could benefit from a resize/prune function is. - Yes a put all function exists, but it does require you know almost exactly how many elements you have. Or know in what power of two you roughly fall into, not to trigger a second rehash, while a hashmap that has a ensureCapacity function you just have a rough estimate and you are way less likely to hit a rehash because you are already dealing with higher powers of two with larger gaps. - If you have a lot of elements that have a lot of hash collisions, you can actually force a treeify/untreeify with trim/ensureSize, because you can decide how tightly packed the map is. Also just to answer your question if that solves my "problem": I don't have a problem with the java implementations, a problem would mean i don't have a "fix" for it that i am not actively using. I am suggesting something that could increase quality of life, and could be moved into a dedicated interface. I mean "Sequenced Collections" is also just a Quality of life interface of the same nature. I rarely use actually java collection implementations anyways, because FastUtils/PrimitiveCollections (my version of FastUtil) have just better implementations and are all i need anyways and are in general faster. Which i benchmarked, though it is biased since it tests primitive speeds. I am not sure if i am allowed to post links so unless you ask i won't. End point was: It was a suggestion, because i would like to see no need for my implementations xD

@JosePaumard 9 месяцев назад

Thanks for your contribution, and when I said "problem" I was more thinking of something that would be bothering you than a real problem. I guess you are aware of the newHashMap(int numMappings) factory method on HashMap, that allows you to create a hash map with the right capacity to accomodate a given number of entries. But indeed you cant "shrink" it in case you need it. All you can do is putAll(), which creates another map. Something a shrinking method would have to do anyway. I think your implementation is great! Why would you see no need for it? :) And I guess that the next big update of the Collections Framework will be when Valhalla, value types, and non-nullable value types are there. At that point having maps with value type keys should basically enable the int key based map implementations, with objects.

@Speiger 9 месяцев назад

@@JosePaumard > I guess you are aware of the newHashMap(int numMappings) Yes i am aware of that, but it doesn't really solve the underlying issue with lack of control for the user. And putAll only takes the inputted hashmap into account for resizing it, not even the hashmaps content itself, making it technically not even optimized for already filled hashmaps... (merging 2 hashmaps to make it clear) (Love when you have like a map of 2k elements and you want to insert another 2k elements, => SHITTY SLOW xD) Edit: Isn't that a bug? > I think your implementation is great! Why would you see no need for it? :) Well even when Valhalla shows up i am pretty sure the implementation need for custom frameworks is there, though they will massively shrink, by a factor of 72... Though it would be nice if java could do it on its own and not require such large custom implementations. Also thank you :)

@JosePaumard 9 месяцев назад

@@Speiger > Edit: Isn't that a bug? Let me ask!

@Speiger 9 месяцев назад

@@JosePaumard to be fair, that is a tiny bug, but the moment you have to insert multiple maps into each other that can get painful... Because you can't batch the resizes.

@Speiger 9 месяцев назад

@@JosePaumard Oh yeah i found a way/exploit to implement a expand method into HashMaps/Sets without actually requiring to override the existing implementations. Simply implement a abstractMap that gives a wrong size parameter and has a empty iterator. Thanks to that the putAll/addAll method will simply grow the array and not add any elements or crash. I love exploits!

@alexandern9266 8 месяцев назад

In terms of memory usage for the typical usage examples (like get data from db, procees it and send to let's say kafka) I think it worth to mention that ArrayList will hold references to the data objects until iteration is over. Making the GC not able to free memory of processed elements. And it can be the case that one data element holds more memory then the list itself. Probably the solution is to iterate from the end and call remove or ... to use LinkedList queue capabilities.

@danthe1st 9 месяцев назад

Honestly when I want a stack, I typically use ArrayDeque and not LinkedList.

@qlinuxm 7 месяцев назад

Sso nice video!

@grizgrox2000 9 месяцев назад

Thanks

@mikolajpodbielski 9 месяцев назад

14:58 creating iterator contributes to huge allocation increase in my application. That's why I had to hardcode to ArrayList and use get(index) instead EDIT: 16:18 and yes, JVM creates all those iterators. I can see it in JFR recording. It also results with many additional GC cycles

@jcsahnwaldt 9 месяцев назад

Thanks for the video! Minor correction: At 20:15, you said that adding an element to an ArrayList is O(log(n)). That's not correct. The worst case complexity is O(n), but the amortized complexity is still O(1).

@JosePaumard 9 месяцев назад

How do you compute O(n)?

@jcsahnwaldt 9 месяцев назад

Example for worst case complexity: When the ArrayList currently has capacity 100 and size 100 and I want to add another element, all 100 elements have to be copied to a new array. In general: In case the array is full, adding an element is O(n) because all n elements have to be copied.

@JosePaumard 9 месяцев назад

@@jcsahnwaldt Yes, but it happens only once in a while, and the number of time it happens decreases with n. Thus the O(log(n)) complexity.

@jcsahnwaldt 9 месяцев назад

@@JosePaumard Yeah, O(log(n)) feels like it should be right, but it's actually O(1). Let's do the math... Let's say g is the growth factor for each resizing. If we add g^k elements one ofter the other, we have to resize/copy the array k times, and the sizes of the copies are 1+g+g^2+...+g^k = (g^(k+1)-1)/(g-1), which we can approximate as g^(k+1)/(g-1)=g^k*g/(g-1), which is the final size g^k multiplied by the constant factor g/(g-1). So to add an element we have to copy g/(g-1) elements on average. That's a constant, i.e. O(1). I'm not sure I explained this very well, but the Javadoc for ArrayList also says: "The add operation runs in amortized constant time, that is, adding n elements requires O(n) time." docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayList.html

@JosePaumard 9 месяцев назад

@@jcsahnwaldt I'm sorry to disagree. The growth factor is 2, that is, everytime you grow the internal array, you double it's capacity, up to a certain point of course. So if you need to add N elements, to determine the number of times you grew the array, you need to find the smallest k that satisfy N

@RiccardoPasquini 9 месяцев назад

It seems to me that head/tail recursion is a good use case for linked lists... but it is sad the lack of tail recursion in java...

@qsergii 7 месяцев назад

15:04 Shouldn't be for(var v : ints){ (without = 0)?

@danny__921 9 месяцев назад

Where did you get that coffee mug from? :)

@JosePaumard 9 месяцев назад

I got it years ago on a booth at JavaOne. Not sure you can find it anywhere...

@_SG_1 9 месяцев назад

At 2:51, shouldn't it be O(n) for Array and O(1) for LinkedList for "Inserting middle"? And "Inserting first" for Array should be O(n)?

@PavelRappo 9 месяцев назад

> O(1) for LinkedList for "Inserting middle" Unless you use ListIterator which is already positioned at the specified index, add(int index, E element) first needs to reach that index, which is O(n).

@thx01138 9 месяцев назад

Yes to the first part -- inserting an additional element into the array list anywhere before the end is O(n) with n elements after the insert.

@liver.flush.maestro 8 месяцев назад

The coffee doesn't go down in your cup between sections 🤣

@sjavaoradev 5 месяцев назад

Sry , I didn't understand why if a = 10, error is < 1%

@PianoMastR64 9 месяцев назад

So, what if the LinkedList not only had the previous and next elements stored in each node, but also the element +/- 10 elements away and +/- 100 elements away and so on? That way it can take shortcuts to wherever you need to access. Each element would be less space efficient, but much more time efficient in theory. Actually, after writing this, I did a bit of research and discovered the concept of Skip Lists, which seems to be more of less what I just proposed. And there he goes mentioning it at 8:16 lol

@JosePaumard 9 месяцев назад

Skip lists makes the O(n) access time to O(log(n)). Which is better! But it consumes more memory.

@bentels5340 9 месяцев назад

Ummm... So essentially nothing has changed in 25 years... because all your results were also true in Java 1.2....

@kshitijpatil2019 6 месяцев назад

For all folks saying "ArrayDeque would have performed better", I ran a benchmark of adding 10,000 elements at the end of list without specifying any initial capacity (consider it as a stack) and here are the results Benchmark Mode Cnt Score Error Units ArrayList avgt 5 40593.366 ± 267.998 ns/op ArrayDeque avgt 5 45781.272 ± 1182.283 ns/op LinkedList avgt 5 29307.404 ± 32.218 ns/op LinkedList performs much better than anything else