1. Introduction
The Java Collection is your one-stop shop for managing a group of elements – but it’s important to know which list structure will best accommodate different tasks. This article dives into exploring when to use ArrayList over LinkedList and how each performs when adding, removing and retrieving data.
2. Time Complexity

Here we can see an average performance of common operations on each list. When we use an iterator to perform the removal and addition of elements, the time complexity changes significantly.
3. ArrayList vs LinkedList
LinkedList and ArrayList both are different implementations of a list interface.

Elements in a LinkedList are maintained using nodes with two pointers that point to the next and previous element. ArrayList internally uses a dynamic array that provides fast random access to elements in constant time. Upon reaching total capacity, it will dynamically resize to 1.5 of its current size.
3.1 Accessing Elements
Direct access to elements references is a crucial advantage of ArrayList. It allows consistent access in constant time of O(1).

The LinkedList, on the other hand, require sequential access to the elements, and it will traverse from the beginning or end, depending on which is closer. Therefore, access to elements equals to O(n) but on average takes (n/4). LinkedList data structure implementation (double linked list) contains two pointers to the first and the last element. Hence it’s possible to achieve constant time if the searched element is correct at the start or the end of the list.
Iterating over each element is very similar in terms of performance. While ArrayList seems slightly faster, the difference is insignificant and should not be a concern unless developing performance-critical application.
3.2 Adding Elements
The ArrayList time complexity for adding elements is generally constant time O(1). When the total capacity is reached, all the elements are copied into a new array equal to 1.5 times the size of the current collection; hence for this specific case, adding elements is much more expensive O(n).
Similarly, LinkedList can also add elements in O(1). When a new node is added the current last node will need to add a pointer to the new node, and the pointer that points to the previous node is repointed to this new element.
When adding elements at a specific index, both implementations will achieve O(n).
3.3 Removing Elements
When removing an element from an ArrayList, all the elements after will need to be shifted by one index. The performance of the shift depends on how close the element is to the beginning; the closer it is, the more elements will require moving. The time complexity averages O(n/2) while it can be O(1) if the removed element is last.
LinkedList remove method will remove the first element at the head, and the second element becomes the new “head” after redirecting pointers. The time complexity for this operation is O(1). If the element is at a specific index inside the collection, then it will traverse sequentially from the beginning or end, depending on which is closer. The average time complexity is O(n/4).
3.4 Sequential processing via Iterators
Looking at the time complexity table from the 1.2 section, using iterator for ArrayList doesn’t make sense due to the decrease in performance. However, utilizing existing iterators for LinkedList to insert and remove elements can be achieved in constant time O(1) by amending the list locally.
4. When to use ArrayList and when LinkedList?
If uncertain about which implementation to choose ArrayList is a more practical choice due to lower memory consumption. Especially when a collection is vast because LinkedList will store extra two pointers per node element, the ArrayList allocates memory regarding current capacity regardless of the number of elements it currently holds.
Depending on the nature of the application the dominant operations may dictate the best implementation. For example, if your application is going to retrieve elements mainly, then ArrayList will be more suitable because of fast random access. If removing or adding a custom index is the dominant operation then LinkedList could be a better choice. But only if you can afford the extra overhead caused by the extra storage.
5. Summary
Whether you opt for an ArrayList or LinkedList, there are pros and cons to consider. Personally I usually go with the former – it consumes less memory and generally provides better results than its counterpart. However if your problem demands certain capabilities only a Linkedlist can provide, then that’s probably where you want to start!
Daniel Barczak
Daniel Barczak is a software developer with a solid 9-year track record in the industry. Outside the office, Daniel is passionate about home automation. He dedicates his free time to tinkering with the latest smart home technologies and engaging in DIY projects that enhance and automate the functionality of living spaces, reflecting his enthusiasm and passion for smart home solutions.
Leave a Reply