Why do we use List instead of ArrayList in Java?

The difference between ArrayList and LinkedList is also an important Java collection interview question, as much popular as Vector vs ArrayList or HashMap vs HashSet in Java. Sometimes this is also asked as for when to use LinkedList and when to use ArrayList in Java.

In this Java collection tutorial, we will compare LinkedList vs ArrayList on various parameters which will help us to decide when to use ArrayList over LinkedList in Java.

Btw, we will not focus on the array and linked list data structure much, which is subject to data structure and algorithm, we'll only focus on the Java implementations of these data structures which are ArrayList and LinkedList.

If you want to learn more about the array and linked list data structure itself, I suggest you checkData Structures and Algorithms: Deep Dive Using Javacourse by Tim Buchalaka on Udemy.

It explains essential data structure in Java programming language and most importantly teaches you when to use which data structure, a good refresher for those who are preparing for coding interviews too.

When to use ArrayList vs LinkedList in Java

Before comparing differences between ArrayList and LinkedList, let's see What is common between ArrayList and LinkedList in Java :

1] Both ArrayList and LinkedList are an implementation of the List interface, which means you can pass either ArrayList or LinkedList if a method accepts the java.util.List interface.

Btw, if you are new to Java's collections framework then I suggest you first go throughJava Fundamentals: Collectionsby Richart Warburton. It's an online Java course on Pluralsight, which you can avail of free by signing their 10-day free trial. IMHO, it's worth going through that course to learn Java collections in the right way.

2] Both ArrayList and LinkedList are not synchronized, which means you can not share them between multiple threads without external synchronization. See here to know How to make ArrayList synchronized in Java.

3] ArrayList and LinkedList are ordered collection e.g. they maintain insertion order of elements i.e. the first element will be added to the first position.


4] ArrayList and LinkedList also allow duplicates and null, unlike any other List implementation e.g. Vector.

5] An iterator of both LinkedList and ArrayList are fail-fast which means they will throw ConcurrentModificationException if a collection is modified structurally once the Iterator is created. They are different than CopyOnWriteArrayList whose Iterator is fail-safe.

Difference between LinkedList and ArrayList in Java

Now let's see some differences between ArrayList and LinkedList and when to use ArrayList and LinkedList in Java.


1. Underlying Data Structure
The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList. This will lead to further differences in performance.


2. LinkedList implements Deque
Another difference between ArrayList and LinkedList is that apart from the List interface, LinkedList also implements theDeque interface, which provides first in first out operations for add[] and poll[] and several other Deque functions.

Also, LinkedList is implemented as a doubly-linked list and for index-based operation, navigation can happen from either end [seeComplete Java MasterClass].


3. Adding elements in ArrayList
Adding an element in ArrayList is O[1] operation if it doesn't trigger re-size of Array, in which case it becomes O[log[n]], On the other hand, appending an element in LinkedList is O[1] operation, as it doesn't require any navigation.


4. Removing an element from a position
In order to remove an element from a particular index e.g. by calling remove[index], ArrayList performs a copy operation which makes it close to O[n] while LinkedList needs to traverse to that point which also makes it O[n/2], as it can traverse from either direction based upon proximity.


5. Iterating over ArrayList or LinkedList
Iteration is the O[n] operation for both LinkedList and ArrayList where n is a number of an element.


6. Retrieving element from a position
The get[index] operation is O[1] in ArrayList while its O[n/2] in LinkedList, as it needs to traverse till that entry. Though, in Big O notation O[n/2] is just O[n] because we ignore constants there.

If you want to learn more about how to calculate time and space complexity for your algorithms using Big O notation, I recommend reading Grokking Algorithms by Aditya Bhargava, one of the most interestingbooks on this topic I have read ever.

7. Memory
LinkedList uses a wrapper object, Entry, which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array.

So memory requirement seems less in the case of ArrayList than LinkedList except for the case where Array performs the re-size operation when it copies content from one Array to another.

If Array is large enough it may take a lot of memory at that point and trigger Garbage collection, which can slow response time.

From all the above differences between ArrayList vs LinkedList, It looks like ArrayList is the better choice than LinkedList in almost all cases, except when you do a frequent add[] operation than remove[], or get[].

It's easier to modify a linked list than ArrayList, especially if you are adding or removing elements from start or end because the linked list internally keeps references of those positions and they are accessible in O[1] time.

In other words, you don't need to traverse through the linked list to reach the position where you want to add elements, in that case, addition becomes an O[n] operation. For example, inserting or deleting an element in the middle of a linked list.

In my opinion, use ArrayList over LinkedList for most of the practical purposes in Java.


Further Learning
Java In-Depth: Become a Complete Java Engineer

Collection in Java - Educative
Algorithms and Data Structures - Part 1 and 2

Other Java Collection Articles you may like

• How to sort a Map by keys and values in Java? [tutorial]
• Top 10 Courses to learn Java for Beginners [best courses]
• How to sort an ArrayList in ascending and descending order in Java? [tutorial]
• 10 Free courses to learn Java in-depth [courses]
• The difference between HashMap and ConcurrentHashMap in Java? [answer]
• 10 courses to learn Data Structure in-depth [courses]
• The difference between HashMap and LinkedHashMap in Java? [answer]
• Difference between ArrayList and HashSet in Java? [answer]
• Top 5 Courses to learn Java Collections and Stream [courses]
• What is the difference between TreeMap and TreeSet in Java? [answer]
• The difference between HashSet and TreeSet in Java? [answer]
• 7 Best Courses to learn Data STructure and Algorithms [best courses]
• 20+ basic algorithms interview questions for programmers [questions]
• Top 5 Courses to become full-stack Java developer [courses]
• The difference between Hashtable and HashMap in Java? [answer]
• 50+ Core Java Interview Questions and Answers [questions]

Thanks for reading this article so far, if you like this article then please share it with your friends and colleagues. If you have any questions or doubts then please drop a note.

P. S. -If you are keen to learn Java Programming in-depth but looking for free online courses then you can also check outJava Tutorial for Complete Beginners [FREE]course on Udemy. It's completely free and you just need an Udemy account to join this course.