ArrayList vs LinkedList

Someone who is new in programming will eventually come across ArrayList and LinkedList. ArrayList and LinkedList can be found in various programming languages, including Java, C, and Python. Both ArrayList and LinkedList are used to implement a list interface. Here, you can store data according to a certain order for easier and more practical organization. However, despite the apparently similar functionality, ArrayList and LinkedList are still different from each other – especially in how they work internally. Depending on the need and condition, either ArrayList or LinkedList will be more suitable for a particular purpose. Choosing between the two can be quite confusing for a first timer, but don’t worry; below, we will see the differences between ArrayList and LinkedList, along with the recommended applications for each of them. We will put our focus in Java, but the characteristics are more or less similar in other programming languages, too.

The Similarities

First, let’s see how ArrayList and LinkedList are similar to each other. Obviously, both ArrayList and LinkedList are implementations of the List interface. Both ArrayList and LinkedList maintain the insertion order. In other words, if you insert identical elements into both ArrayList and LinkedList in the same order, the result sets will be identical, too, with the same order of elements. Both ArrayList and LinkedList are non-synchronized classes, but you can make them synchronized explicitly by using the Collections.synchronizedList method. Finally, perhaps the least noticeable thing about these classes is that the iterator and listIterator returned by both ArrayList and LinkedList are fail-fast. If the list is structurally modified at any point after the iterator is created without using the iterator’s own add and remove methods, it will produce a ConcurrentModificationException.

The Data Structure

So, how are the two different from each other? Let us start from the fundamental difference, the data structure. ArrayList is an index-based data structure. It uses a dynamic array to store the elements. You can say that the elements in an ArrayList are independent of each other. The elements in an ArrayList are not related to each other. It only implements the List interface, so it can only act as a list. Imagine a line of people in front of the cashier in a minimarket – that’s ArrayList. There is an index (an order) that identifies which element is inserted first, second, third, until the last. But the elements, the people, are not related to each other.

On the other hand, LinkedList utilizes a doubly linked list to store the elements. It can act as a list and a queue because it implements both List and Deque interfaces. Imagine a train with connected carriages, or a line of people who are holding hands with the ones on their sides. The carriages and the people are connected to each other – they are analogue to the elements in a LinkedList. LinkedList does not provide random or index-based access, so it requires you to iterate over in order to retrieve an element.

Searching

How does the difference in data structure affect the performance? First of all, let’s see the performance levels of ArrayList and LinkedList in performing searching. If you have learned about the Big O notation (that is a mathematical notation that is usually used to measure a function’s performance), you should know that ArrayList has the performance of O(1) whereas LinkedList has the performance of O(n). ArrayList is faster than LinkedList in doing searching, and the gap in performance grows with more number of elements. The reason? The index-based array data structure in ArrayList is much more efficient for searching an element in a list. You can access a specific element directly by addressing the index. On the other hand, LinkedList does not have any index. The doubly linked list requires you to traverse through the first to the last (or the last to the first) until you find an element.

Insertion and Deletion

However, LinkedList consistently gives the O(1) performance in doing insertion and deletion, whereas ArrayList gives the O(n) performance in the worst case and the O(1) performance in the best scenario. So, for insertion and deletion, LinkedList is faster than ArrayList. This is because LinkedList’s doubly linked list puts two pointers on each element, both of which refer to the neighboring elements in the list. As the effect, insertion or deletion simply requires changes in the pointers in the neighboring elements, without having to shift the elements. On the other hand, ArrayList has to shift its elements to create a space for the new element in an insertion operation, or to fill the empty space created by the deleted element in a deletion operation.

Memory

ArrayList eats up less memory than LinkedList. In an ArrayList, an element only has one index as the ‘additional’ information to be stored in the memory. Meanwhile, in a LinkedList, an element has two pointers as the ‘additional’ information to be stored in the memory. Hence, the memory consumption of an ArrayList is lower than that of a LinkedList.

When Should We Use ArrayList / LinkedList?

You may have noticed that ArrayList is quite more popular than LinkedList, but each of them has each own purposes. An ArrayList is more suited for an application that requires random access and performs a lot of searching or data retrieval. On the other hand, if your application can live without random access and it performs more data manipulation (insertion and deletion), a LinkedList will give a better performance.

ArrayListLinkedList
- Internally uses an index-based dynamic array to store elements - Internally uses a doubly linked list to store elements
- Faster in searching and data retrieval- Slower in searching and data retrieval
- Slower in insertion and deletion data manipulation because of the bit shifting- Faster in insertion and deletion data manipulation because no bit shifting is required
- Only acts as a list because it only implements the List interface- Can act as a list and a queue because it implements List and Deque interfaces
- Lower memory consumption- Higher memory consumption

Conclusion

ArrayList and LinkedList are both implementations of the List interface with different data structures. ArrayList is index-based, thus more efficient for searching and data retrieval. It also eats up less memory. LinkedList uses a doubly linked list, and is more efficient for data manipulation, with higher memory consumption.

Leave a Reply