LinkedList is faster than ArrayList while inserting and deleting elements, but it is slow while fetching each element.
- LinkedList is faster in add and remove compared to ArrayList. ArrayList is faster in get().
Elements to be added or removed are too large, go for LinkedList. Usage of get() is more, go for ArrayList. Again, if you don’t have element access in a large number, go for LinkedList.
LinkedList could be used for large lists of data since the total elements vary accordingly. In an ArrayList, the maximum elements in the list will be known, and it can be used for small lists.
If you are using retrieval operations frequently, go for ArrayList. Retrieval operation means collecting the data from a data structure, which can be stored, viewed and printed. ArrayList performs shift operations internally, so the insertion of data in the middle or deletion in the middle is complicated. If you are opting these operations, ArrayList won’t be the best. It stores elements in different memory locations, and hence the process of retrieval will be convenient. If you are performing insertion of data in the middle or deletion of data in the middle is relatively easy, hence go for LinkedList. It works best for frequent addition or deletion in the middle. They do not store elements in different memory locations, and therefore, if you are looking for more Retrieval operations, LinkedList is not the best one. In a retrieval operation, the elements should be stored in consecutive memory locations else it won’t be easy.
- ArrayList vs LinkedList in terms of
Time Complexity
| Operation | ArrayList | LinkedList | Winner |
|---|---|---|---|
| get(index) | O(1) | O(n) for n/4 steps in avg | ArrayList |
| add(E) | O(1) BUT O(n) in worst case | O(1) | Linked List |
| add(index, E) | O(n) for n/2 steps | O(n) for n/4 steps BUT O(1) if index = 0 | Linked List |
| remove(index, E) | O(n) for n/2 steps | O(n) for n/4 steps | Linked List |
| Iterator.remove() ListIterator.add() | O(n) | O(1) | Linked List |
| ArrayList | LinkedList |
|---|---|
| Allows fast read access | Retrieving element takes O(n) |
| Adding an element require shifting all the later elements | o(1) [but traversing takes time] |
| To add more elements than capacity new array need to be allocated |
Detailed difference between ArrayLists & LinkedLists
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).
ArrayList is a resizable array, so when you fill up its initial size, it becomes bigger and that will happen again and again.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.
fistElement.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 the inserting element into the concrete 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.