"How about a little training for your brain? I hope it's still in working order."

"Earlier, in the table of containers and collections you saw that the same interface can have multiple implementations. I'll now tell you why we need that. And how ArrayList differs from LinkedList."

"The thing is, collections may be implemented in different ways and no implementation is always ideal. In one approach, some operations are fast, but others are slow. The opposite can be true for another approach. There is no perfect one-size-fits-all solution."

"That's why the decision was made to implement several versions of the same collection. Each implementation should be optimized for some narrow set of operations. This is how different collections came to be. Let's study two classes as examples: ArrayList and LinkedList."

ArrayList vs. LinkedList - 1

"Internally, ArrayList is implemented as an ordinary array. That's why inserting an element in the middle requires that we first shift all the succeeding elements by one, and then put the new element into the free slot. Getting and setting elements (get, set) is fast, since these operations simply address the relevant array element."

"LinkedList has a different internal structure. It's implemented as a list with interconnected elements: a set of distinct elements, each of which stores references to the next and previous elements in the list. To insert an element into the middle of such a list, you only need to change the references of its future neighbors. However, to get element No. 130, you have to run through each object from 0 to 130. In other words, get and set operations will be slow. Look at the following table:"

Description Operation ArrayList LinkedList
Get an element get Fast Slow
Set an element set Fast Slow
Add an element (to the end of the list) add Fast Fast
Insert an element (at an arbitrary position) add(i, value) Slow Fast
Remove an element remove Slow Fast

"I see. I'm starting to understand it now. Are there any criteria or rules that would help me know which collection is best in a particular situation?"

"To keep it simple, I'll give you the following rule: if you are going to frequently insert (or remove) elements in the middle of the collection, it's better to use LinkedList. In all other cases, ArrayList works better."

"We'll delve into how they are structured in more advanced lessons, but for now we'll just practice using them."