Java Notes — ArrayList vs LinkedList

Both LinkedList and ArrayList are implemented List interface. Both classes have all methods of List such as “boolean add(E e);”.

If both classes have the same functionality why do we need both?

ArrayLists are using an Array under their structure.

In Java, you can create Arrays like below

4 is the length of your Array here and the length of Array doesn’t increase automatically when you add more items than its size. You need to increase the size of the Array manually if ArrayList doesn’t exist. It would be a lot of work to handle resizing the Array. This is one of the biggest problems the ArrayList class solves for us. These resizing operations can spend a lot of time and resources.

On the other hand, LinkedList has nodes instead of having Array to contain the data. If we would like to implement our version of the structure simply it might look something like below.

This of course not a functional implementation but It gives us a quick understanding of the structure.

If we use the get method of both implementations the processes underneath are very different.

Since ArrayLists uses an Array and Array can access its values in constant time the get method implementation for ArrayList works faster.

On the other hand, LinkedList uses Nodes, and Nodes are chained to each other therefore to get an index of LinkedList Java has to go through the Nodes.

However, adding or removing elements to the LinkedList is way faster than ArrayList. For example, if we add some node to an index of the LinkedList the change will occur only on the element of the index and its next and prev attributes. All other elements of the Nodes chain will be unchanged. Adding elements to ArrayList is slower because ArrayList has to create a new Array to achieve the same.

If optimization is not that important for your case maybe it doesn’t matter but if you are optimization focused care about this difference between both implementations.

Use LinkedList if your use case needs to add and remove elements fastest.

Use ArrayList if you need to reach the elements fastest and your use case needs a more static List.