Performance oriented development is one key aspect of any serious developer. Sometimes we are very accustomed to some practice, or use of a specific programming language feature, that we might forget there are other options that can work better on different scenarios. This could be the case of the different collections provided by Java. In the past I used to create all my list collections using ArrayList and never wondered about the pros/cons of using alternatives like LinkedList until I read some literature explaining the best scenarios for each one.
Pros of ArrayList
1. ArrayList uses internally an array for internal storage. That makes it particularly fast for random access - get(#n).
Cons of ArrayList
1. ArrayList is slower for modification operations like add or delete elements in the beginning or middle of the collection. This is due to the need of relocate all subsequent elements one position to the right (or left in case of deletion) in order to make space to the new element.
Let's show this graphically. Let's suppose we have a list of six elements.
And we want to insert an element before the second one.
To be able to add this element, internally, the list needs to copy all elements from index 1 to 5 one position to the right.
2. Similar to before described process. ArrayList has some performance downside when the internal array is completely full, and therefore has to create a bigger array and relocate all elements to new array.
Pros of LinkedList
1. LinkedList follows a different approach. It's more efficient in adding or deleting elements in the beggining or middle of the collection. If you ever programmed from scratch a list data structure, you will remember you have nodes with pointers/references to the next element.
In this case what is done to insert a new node in the middle of the list is to create a new node pointing to the next element (->c), and the before element is updated to point to the new created node (->b).
2. Given the nature of the internal structure which is not restricted to an initial size, LinkedList has no growing problems as ArrayList.
Cons of LinkedList
1. Random access to LinkedList elements are expensive, because in worst case scenarios the entire list has to be traversed to retrieve the desired element (O(n)).
We could say that we should use ArrayList if we have many random accesses. If we think our lists are going to grow unexpectedly, we should favor LinkedList. This is just one scenario. We could have both needs in which case a combination of both approaches could be use. Like using LinkedList to create the list, and then use ArrayList for read access.
