LinkedList vs. ArrayList

In the previous topics, you have met two classes that are quite similar: ArrayList and LinkedList. They both implement the List interface and provide useful features for storing and accessing elements. Which one to use? The truth of life is that different problems require different approaches. To make the right choice you need to understand who is the winner in which situation. And today you finally will be prepared for making this choice: we are going on an exciting journey of comparing ArrayList and LinkedList in detail.

What is inside?

Let's start with a quick and illustrative overview of how our lists look inside.
On the inside, an ArrayList is a resizable array of objects, where every element has an index.

A LinkedList is a doubly-linked list based on connected nodes. LinkedList stores its head and tail.

A node is a class that has three fields: the element itself, the previous, and the next node.

Now, with these pictures in mind, it's time to think how fast standard operations will work for both of them and why.

First round: ArrayList

The logic of an ArrayList is simple: because internally it's an array, the operations get(int index) and set(int index, E element) will be fast. In other words, the time complexity for access by an index is O(1).

If you use the add(E e) operation, a new element will be added to the end of ArrayList. This would also be fast and take constant time to make, so the complexity would be the same: O(1).

But if you would like to insert an element into the ArrayList by using the add(int index, E element) operation the situation will be different. To put the new element into a specific index the ArrayList needs to move all subsequent elements.

In our example, after the insertion, an element "Array" will have an index of 4 and an element "List!" will have an index of 5. If there are a lot of subsequent elements this operation will be quite long with the time complexity O(n).

Let's take a look at what is really happening inside of Java.

When you want to add a new element to the full ArrayList, firstly, a new array with a bigger size will be created. Then all existing elements will be copied to that new array. And only then your new element will be added. So, the worst time complexity would be O(n).

The last operation is remove(int index). When you would like to remove an element all subsequent elements will have to be moved.

Because of moving all subsequent elements, this operation won't be very efficient for a long list, with the time complexity O(n).

Now you know what is happening with ArrayList and it's time to pay some attention to his rival LinkedList.

Final round: LinkedList

A LinkedList is not an array, so it doesn't support fast access by index. But it can reach an element by its index. In order to do this LinkedList decides what will be closer to that index: head or tail. And then going from either head or tail, LinkedList traverses all the elements before it reaches the required one.

firstElement.next.next.next.next.next.next...

Let's start with get(int index) and set(int index, E element) operations.

To get an element "am" with an index 1, LinkedList will start from the head. In our example, LinkedList will need to go only through one link: between element "I" and element "am". But if you have a long LinkedList and the required index is in the middle, these operations get(int index) and set(int index, E element) will take a lot of time. So, in a bad situation, the time complexity would be O(n).

Adding an element to the end of the LinkedList is a fast operation. LinkedList will connect the new element "Hello!" with the last element "List" and will make the element "Hello" the new tail.

So it always takes constant time and the complexity of add(E e) is O(1).

Besides the method add(E e) there are two other methods: addFirst(E e) and addLast(E e). As you can understand from their names, they add the element in the head and in the tail of the LinkedList respectively. Their internal mechanism is absolutely the same as with the method add(E e). And their complexity is also O(1). The method addLast(E e) is the equivalent to the method add(E e). The difference is that the method add(E e) returns boolean and the method addLast(E e) returns void.

And what about inserting an element at a specific index with the operation add(int index, E element)?

To add an element LinkedList needs to reach the required position and then only change the links of the new element neighbors.

And that's it: connect the new element with the previous and the next element, and the insertion is done. No need to move elements as in the ArrayList.

If you add new elements near the head or tail the time complexity of it would be O(1). In most situations, it's a fast operation. But if your list is a very long one then reaching the element in the middle wouldn't be so fast. So, in a bad situation, the time complexity would be O(n).

The last one is remove(int index) operation. The mechanism is the same, LinkedList needs to reach the element and change the links.

By changing the neighbors' links the unwanted element would be deleted. And again, for most situations, it's a fast operation. But for removing the element from the middle of a very long LinkedList the time complexity would be O(n).

LinkedList has two other useful methods: removeFirst() and removeLast(). For them, LinkedList doesn't need to traverse the elements. It just removes the first or last element and changes the head or tail respectively. The time complexity for both operations is O(1).

And the winner is...

Let's illustrate the main points with a table:

So, there is no absolute winner in our competition. Yes, ArrayList is more popular, but in fact, everything depends on the task you are working on. For all operations, it's impossible to say in advance whether they are fast or take a long time. It depends on what is the size of your list and with which part of it you are working. The most important thing for you to understand is how these operations work. Sometimes it may be difficult to make the right choice, but with this understanding, you will definitely avoid silly mistakes.

And there's another reason to pay special attention to this topic: there is a very good chance that you will be asked about the differences between ArrayList and LinkedList on the job interview.