Friday, January 22, 2016

9 difference between Array vs ArrayList in Java

Both array and ArrayList are two important data structure in Java and frequently used in Java programs. Even though ArrayList is internally backed by an array, knowing the difference between an array and an ArrayList in Java is critical for becoming a good Java developer. If you know the similarity and differences, you can judiciously decide when to use an array over an AraryList or vice-versa. In this article, I'll help you understand the difference between ArrayList and array in Java. If you are coming from C or C++ background then you already know that array is one of the most useful data structure in the programming world. It offers O(1) performance for index-based search and one of the fundamental way to store data.

The ArrayList one the other hand is a class in Java Collection framework which was introduced as a dynamic array. Since an array is static in nature i.e. you cannot change the size of an array once created, So, if you need an array which can resize itself then you should use the ArrayList. This is the fundamental difference between an array and an ArrayList. 

It's also one of frequently asked Java interviews, and if you are preparing for your next job, then knowing these details could be really useful. You can also take benefit from the variety of questions from Java Programming Interview Exposed book, one of the best to prepare for Java programmer job interviews.

Array vs ArrayList in Java

It's best to compare two things on some points, this will make the differences easy to understand. So let's see what are the points on which you can compare an array with the ArrayList in Java

1) Implementation
The array is a native programming component or data structure but ArrayList is a class from Java Collections framework, an API. In fact, ArrayList is internally implemented using an array in Java. Since ArrayList is a class it holds all properties of a class e.g. you can create objects and call methods but even though the array is an object in Java it doesn't provide any method. It just exposes a length attribute to give you the length of the array, which is constant.

2) Performance
Since ArrayList is based upon array you would assume that it provides the same performance as an array. This is true at some extent but because of extra functionality ArrayList provides there is some difference in performance of ArrayList and array, mainly in terms of memory usage and CPU time. For index-based access, both ArrayList and array provides O(1) performance but add can be O(logN) in ArrayList if adding a new element triggers resize, as it involves creating a new array in background and copying elements from the old array to new array. The memory requirement for ArrayList is also more than an array for storing the same number of objects e.g. an int[] will take less memory to store 20 int variables than an ArrayList because of object metadata overhead on both ArrayList and wrapper class.

3) Type Safety
ArrayList is type safe because it supports generics which allows the compiler to check if all objects stored in ArrayList are of the correct type. On the other hand, the array doesn't support Generic in Java. Which means compile time checking is not possible but array provides runtime type checking by throwing ArrayStoreException if you try to store an incorrect object into array e.g. storing a String into an int array.

4) Flexibility
Flexibility is the single most important thing which separates array and ArrayList. In short, ArrayList is more flexible than a plain native array because it's dynamic. It can grow itself when needed, which is not possible with the native array. ArrayList also allows you to remove elements which are not possible with native arrays. By remove, we mean not just assigning null to the corresponding index but also copying rest of elements one index down, which ArrayList automatically does for you. You can learn more about removing objects from ArayList in my article difference between clear() and removeAll().

5) Primitives
If you first start using ArrayList then you will realize that you cannot store primitives on ArrayList. This is a key difference between array and ArrayList because array allows storing both primitives and object. For example int[] numbers are valid but ArrayList of int is not valid. how do you deal with this problem? Suppose you want to store int primitives into ArrayList than how do you that? Well, you can use the wrapper class. This is one of the reasons why wrapper class was introduced in Java. So if you want to store int 2 into ArrayList just put it, autoboxing will do the rest. Btw, this difference is not so obvious from Java 5 onwards because of auto-boxing as you will see that ArrayList.add(21) is perfectly valid and works.

6) Generics
One more significant difference between an ArrayList and an array is that former supports Generic but later doesn't. Since an array is of covariant type, you can use Generics with them. This means it's not possible for a compiler to check the type-safety of an array at compile time but they can verify type-safety of Array. So how do you deal with this problem while writing a type-safe class in Java? Well, you can use the technique shown in Effective Java, where you can declare an array like E[] and later use type casting.

7) Iteration
ArrayList provides more ways for iteration i.e. accessing all elements one by one than an array. You can only use loop e.g. for, while, enhanced for loop and do-while to iterate over an array but you can also use Iterator and ListIterator class to iterate over ArrayList. See here to learn different ways to iterate over ArrayList in Java.

8) Supported Operations
Since ArrayList is backed by an array internally, it exposes the operation which is possible with an array but given its dynamic nature it also added operation which is not possible with native array e.g. you can store elements in both array and ArrayList, but only ArrayList allows you to remove an element. Though you can simulate that with an array by assigning null to respective index, it won't be like remove unless you also move all element above that index in the array to one level down.

Both ArrayList and array also provides ways to retrieve element e.g. get() method of ArrayList uses an index to get an element from array e.g. version[0] will return the first element.
ArrayList also provides an operation to clear and reuse e.g. clear() and removeAll(), the array doesn't provide that but you can loop over Array and assign each index null to simulate that.

9) Size() vs length
Array only provides a length attribute which tells you the number of slots in the array i.e. how many elements it can store, it doesn't provide you any method to find out how many are filled and how many slots are empty i.e. the current number of elements. While ArrayList does provides a size() method which tells a number of objects stored in ArrayList at a given point of time. The size() is always different than length, which is also the capacity of ArrayList. If you want to know more, I suggest you read the difference between size() and length in ArrayList article.

10) Dimension
Another significant difference between an array and an ArrayList is that array can be multi-dimensional e.g. you can have a two-dimensional array or a three-dimensional array, which makes it a really special data structure to represent matrices and 2D terrains. On the other hand, ArrayList doesn't allow you to specify dimension. See this tutorial learn more about how to use a multi-dimensional array in Java.

Here is the nice slide highlighting all important difference between Array and ArrayList in Java:

Difference between an Array vs ArrayList in Java

Similarity between Array and ArrayList

So far you have seen the difference between an ArrayList and an array, now let's concentrate on some of the similarities. Since ArrayList internally uses array, it's bound to have lot of similarities as seen below:

1) Data Structure
Both allows you to store objects in Java and both are an index-based data structure which provides O(1) performance to retrieve an element, but search without an index is still log(N) if your array is sorted and you use binary search algorithm.

2) Order
Both array and ArrayList maintains order on which elements are added into them.

3) Search
You can search for an element using an index, that's O(1) otherwise you can use linear search if your array is not sorted, which takes around O(n) time or you can use binary search after sorting an array in Java, this is sorting + O(logN).

4) Null values
Both array and ArrayList allows null values but remember only object array allows null primitive array doesn't they store the default value of primitive type e.g. zero for int and false for boolean.

5) Duplicates
Both array and ArrayList allows duplicates. It's also one of the common array based coding questions to write a program to find out duplicates from an array in place.

6) Performance
ArrayList mimic array's performance e.g. O(1) access if you know the index but it has additional memory overhead because it's an object and also holds additional data to automatic resize the ArrayList.

7) Zero-based Index
Both array and ArrayList have zero-based index i.e. first element starts at zeroth index.

That's all about the real difference between an array and an ArrayList in Java. The most important difference you should remember is that array is static in nature i.e. you cannot change their size once created but ArrayList is a dynamic array, which can resize itself if a number of elements in the ArrayList are more than the resize threshold. Based upon this difference, you should use an array as a data structure to store objects if you know the size in advance and sure it's not going to change, if you are unsure then just use the ArrayList.

Further Learning
Java In-Depth: Become a Complete Java Engineer
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz


Unknown said...

> add can be O(logN) in ArrayList if adding a new element triggers resize, as it involves creating a new array in background and copying elements from the old array to new array.

Is it really O(logN)? Copying should take O(n)

javin paul said...

@Unknown, Yes, array copy is theoretically O(n) but ArrayList.add() internally uses System.arrayCopy() to copy data. Since System.arraycopy() is a native call which does copy operation directly at memory, it's much faster than O(n). It also depends where you are adding element e.g. if you append it's constant or logarithmic but if insert it at the middle than it could be linear or (nlogn) if growing, but remove is always liner because it always perform complete copy.

Unknown said...

Type Safety statement is incorrect: You will get compilation error if you try to store the String in int array.

Anonymous said...

Even if you are using System.arrayCopy, it is still O(N), it doesn't matter if it is Java/Ruby/Aseembly or you are using RAM, HD or CPU Cache, what matter is the algorithm used to copy

Anonymous said...


Success for this site.

Anonymous said...

If you enjoy following Javarevisited, you should checkout the Wellness Mama fan page. She's been publishing some awesome content you should consider liking her fana page

shout-out-for-shout-out deals

Somanath K. said...

Really Nice Explanation.
Thank you!!

Post a Comment