ArrayList in Java
Learn via video course
FreeOverview
ArrayList is a class in java.util package which implements dynamic-sized arrays in Java. ArrayList dynamically grows and shrinks in size on the addition and removal of elements respectively.
ArrayList inherits the AbstractList class and implements the List, RandomAccess and Serializable interfaces. Addition of elements to an ArrayList takes amortized constant time: O(1).
Introduction
ArrayList in Java supports dynamic arrays and it is based on array data structure. Unlike built-in arrays, ArrayLists are resizable which means they can grow and shrink dynamically as we add and remove elements. It is relatively slower than built-in arrays but can be of great use in lots of array manipulation programs.
What is ArrayList in Java?
The ArrayList class is a part of Collection framework, extends AbstractList class and implements the List interface. This class is declared in java.util package. It is used for creating dynamic arrays that are resizable in nature. Apart from this, we can also use pre-defined methods of this class to manipulate the ArrayList elements.
Syntax:
Important Features of ArrayList Java
- Dynamic Resizing: ArrayList grows dynamically as we add elements to the list or shrinks as we remove elements from the list.
- Ordered: ArrayList preserves the order of the elements i.e. the order in which the elements were added to the list.
- Index based: ArrayList in Java supports random access from the list using index positions starting with ‘0’.
- Object based: ArrayList can store only Objects data types. They cannot be used for primitive data types (int, float, etc). We require a wrapper class in that case.
- Not Synchronized: ArrayList in Java is not synchronized, we can use the Vector class for the synchronized version. It means ArrayList operations are not thread-safe and multiple threads should not operate on the same ArrayList object at the same time.
Time Complexities of key ArrayList operations:
- Random access takes O(1) time
- Adding element takes amortized constant time O(1)
- Inserting/Deleting takes O(n) time
- Searching takes O(n) time for unsorted array and O(log n) for a sorted one
How ArrayList Works?
ArrayList can change its size as one adds or removes elements. Internally, the actual implementation is a lot of work and complex but the basic idea of how ArrayList works when it becomes full and we want to add new elements is shown below.
When an ArrayList is created, its default capacity or size is 10 if not provided by the user. The size of the ArrayList grows based on load factor and current capacity.
- The Load Factor is a measure to decide when to increase its capacity. The default value of load factor of an ArrayList is 0.75f
- ArrayList in Java expands its capacity after each threshold which is calculated as the product of current capacity and load factor of the ArrayList instance.
For example, if the user creates an ArrayList of size 10,
This means after adding the 7th element to the list, the size will increase as it has reached the threshold value. Internally, a new ArrayList with a new capacity is created and the elements present in the old ArrayList are copied in the new ArrayList, as shown in the following image.
In Java 8 and later, the new capacity of the ArrayList is calculated to be 50% more than its old capacity.
new_capacity = old_capacity + (old_capacity >> 1)
In the above formula, the new capacity is calculated as 50% more than the old capacity. Here, (old_capacity >> 1) gives us half of the old capacity. For more details on how the Right Shift Operator works, follow this article.
For example, if the array size is 10 and it has reached the threshold value, we have to increase its capacity to add new elements. The new capacity will be 10 + (10 >> 1) => 10 + 5 => 15. Hence, the size is increased from 10 to 15.
Note:
Even if it provides flexibility, this process takes up a lot of space and time. As a result, choosing the initial capacity while keeping the number of expected elements in mind would be a wise strategy.
The default load factor of 0.75f ensures that the ArrayList always provides the optimal performance in terms of both space and time.
Takeaway:
- The backing data structure of ArrayList is an array.
- When the array becomes full and we want to add new elements, a new ArrayList with a new capacity is created.
- The elements present in the old ArrayList are copied in the new ArrayList, while deleting the old ArrayList.
Constructors in the Java ArrayList
Since ArrayList is a generic class, you can parameterize it with any type you want, and the compiler will ensure that, for example, you can't place Integer values inside a collection of Strings. In addition, while accessing elements from an ArrayList, you do not need to cast them.
1. ArrayList<>(): This constructor is the default one, it creates an empty ArrayList instance with default initial capacity i.e. 10.
Syntax:
2. ArrayList(int capacity): This constructor creates an empty ArrayList with initial capacity as mentioned by the user.
Syntax
3. ArrayList(Collection list): This constructor creates an ArrayList and stores the elements that are present in collection list.
Syntax
Note:
If you want to create an ArrayList instance which can store Objects of multiple types, don't parameterize the instance.
Syntax:
Methods in Java ArrayList
In Java, ArrayList class provides various predefined methods which can be accessed using object of ArrayList class. Let’s discuss a few important methods of the ArrayList class.
| Method | Description |
|---|---|
| add(Object o) | Adds a specific element at the end of ArrayList. |
| add(int index, Object o) | Inserts a specific element into the ArrayList at the specified index. |
| addAll(Collection c) | This method is used to add all the elements present in a specified collection at the end of the ArrayList. |
| addAll(int index, Collection c) | Inserts all the elements present in a specified collection into the ArrayList starting with the specified index. |
| remove(Object o) | Removes the first occurrence of the specified element from the ArrayList if present. |
| remove(int index) | Removes the element present at specified index from the ArrayList. |
| removeAll(Collection c) | Removes all the elements present in a specified collection from the ArrayList. |
| clear() | This method is used to remove all the elements from the ArrayList. |
| contains(Object o) | Returns true if the ArrayList contains the specified element. |
| get(int index) | Returns the element at the specified index in the ArrayList. |
| indexOf(Object o) | Returns the index of the first occurrence of the specified element in the ArrayList, or -1 if the list does not contain the element. |
| isEmpty() | Returns true if the ArrayList contains no elements. |
| lastIndexOf(Object o) | Returns the index of the last occurrence of the specified element in the ArrayList, or -1 if the list does not contain the element. |
| listIterator() | Returns a list iterator over the elements in the ArrayList in proper sequence. |
| listIterator(int index) | Returns a list iterator over the elements in the ArrayList in proper sequence, starting at the specified index in the list. |
| set(int index, Object o) | This method is used to replace the element at the specified position in the ArrayList with the specified element. |
| toArray() | This method returns an array containing all the elements present in the ArrayList in proper sequence. |
| subList(int fromIndex, int toIndex) | Returns a view of the portion of this list between the specified fromIndex (inclusive) and toIndex (exclusive). |
| trimToSize() | Trims the capacity of the ArrayList instance to the list’s current size. |
| size() | Returns the number of elements present in the ArrayList. |
How to Create ArrayList in Java?
We can only add objects in the ArrayList but if we want to add primitive data types such as int, float, etc., we can use wrapper class for such cases. To create an ArrayList in Java, we first need to create an instance of the ArrayList class. This can be done by the following statement:
The following Java program creates an ArrayList with the help of constructors.
Output:
How to Add Elements to an ArrayList?
We can add elements to an ArrayList with the help of add() method. This method is overloaded, allowing it to do several operations based on various parameters. Here's what they are:
Syntax:
- add(Object o): This method is used to directly add the specified element at the end of the ArrayList.
- add(int index, Object o): This method is used to insert the specified element in the array list at the specified index.
The following Java program adds new elements to an ArrayList using the add() method:
Output:
How to Get Element from ArrayList?
We can randomly access elements from the ArrayList using the get() method.
Syntax:
- get(int index): In this method, we provide the index and it returns the element present at the specified index.
The following Java program accesses elements from an ArrayList using the get() method:
Output:
Note:
The get(int index) method throws java.lang.IndexOutOfBoundsException if the index is greater than or equal to the size of the ArrayList.
How to Sort ArrayList in Java?
We can sort an ArrayList using the sort() method of the Collection framework in Java.
Syntax:
- Collections.sort(ArrayList): As an argument, it takes the object of an ArrayList and sorts the ArrayList in the ascending order according to the natural ordering of its elements.
The following Java program sorts an ArrayList using the sort() method:
Output:
Takeaway:
- sort() method doesn't return anything.
- The implementation is iterative merge sort and takes O(n * log(n)).
Change an element in ArrayList
In order to change an element in the ArrayList, we can use the set() method.
Syntax:
- set(int index, E element): In this method, we provide the index and the new element as arguments which in return replaces the element present at the specified index with the new element.
The following Java program changes an element in the ArrayList using set() method.
Output:
Note:
set() method will also throw IndexOutOfBoundsException, if the index is out of range.
How to Remove Elements from ArrayList?
We can remove elements from an ArrayList with the help of remove() method. This method is also overloaded, allowing it to do several operations based on various parameters. Here's what they are:
Syntax:
- remove(Object o) : This method is used to directly remove the specified element from the ArrayList.
- remove(int index) : This method is used to remove the element present at the specified index from the ArrayList.
The following Java program deletes elements from the ArrayList using remove() method.
Output:
Note:
- remove() method of the ArrayList class is overloaded.
- remove(int index) method will also throw IndexOutOfBoundsException, if the index is out of range.
Iterating ArrayList
There are many ways of iterating through an ArrayList. In the above examples, we were displaying the elements just by calling the ArrayList instance which isn't the best approach to show the elements. The simple method to iterate through an ArrayList is a simple loop or an advanced one.
The following Java program iterates through an ArrayList using loops.
Using Loops
Output:
Explanation:
- While using simple for loop, we are accessing elements with the help of get() method by passing index positions.
- Whereas for each loops are mainly used for traversing items in a collection, so we are able to directly access the elements as per the implementation.
Using listIterator()
An iterator is an object that enables a programmer to traverse through collections such as ArrayList, HashSet, etc.
Syntax:
- public ListIterator<E> listIterator(): This method returns a list iterator over the elements in the ArrayList in proper sequence. The returned list iterator is fail-fast.
The following Java program iterates through an ArrayList using the listIterator() method.
Output:
Note:
Fail-Fast iterators immediately throw ConcurrentModificationException if there is structural modification of the collection. Structural modification means adding, removing any element from collection while a thread is iterating over that collection.
Finding the length of the ArrayList
In order to find the length of an ArrayList, we can use the size() method.
Syntax:
- size(): It returns the number of elements present in an ArrayList.
The Java program given below demonstrates how to find the size of an ArrayList.
Output:
Note:
The size of an ArrayList is not necessarily equal to its capacity.
How to check if ArrayList is Empty in Java?
In order to find out if an ArrayList is empty or not, we can use the isEmpty() method.
Syntax:
- public boolean isEmpty(): This method returns true if an ArrayList is empty.
The following Java program demonstrates if an ArrayList is empty or not.
Output:
How to synchronize ArrayList in Java?
ArrayLists in Java are not synchronized, this means it must be synchronized externally if a thread modifies it structurally and multiple threads try to access it at the same time.
This can be done using the following methods:
- Collections.synchronizedList() method.
- Using CopyOnWriteArrayList (thread-safe variant of ArrayList)
The crucial thing to remember is that under this type of synchronization, the iterator must be in a synchronized block, as demonstrated in the example below.
Output:
The following Java program synchronizes an ArrayList externally using CopyOnWriteArrayList.
Output:
Takeaway:
- ArrayList is not Synchronized, we need to synchronize it externally.
- Vector is the synchronized class in Java. It can used as an alternative to ArrayList class if synchronization is required.
Java Array vs ArrayList
The key differences between Array and ArrayList are listed in the table below:
| Array | ArrayList |
|---|---|
| Array is a data structure in Java used for storing elements. | ArrayList is a class of Collection framework which implements the List interface. |
| The size of an array is fixed and cannot be changed. | The size of an ArrayList is not fixed. We can increase or decrease its size as one adds or removes elements. |
| We need to mention its size while creating an array. | We can create an ArrayList instance without mentioning its size. |
| Arrays can hold both primitive data types and objects of a class. | ArrayList only accepts object entries. We need to provide wrapper classes for primitive data types. |
| Arrays are faster as they are of fixed length. | ArrayList are relatively slower because of its dynamic nature. |
Benefits of ArrayList
- The fact that ArrayList is dynamic in size is one of its main advantages. We can increase and decrease the size of ArrayList dynamically.
- ArrayList has various predefined methods which help to manipulate the stored objects.
- In ArrayList, we can randomly insert and delete elements.
- We can add different types of objects into the ArrayList.
- In ArrayList, listIterator() allows us to traverse in both directions.
FAQs
1. What is ArrayList in Java used for?
ArrayList in Java is used to store elements. When we are uncertain about the number of elements to be stored and we want to preserve its order of insertion, we can use ArrayList.
2. Is ArrayList and List the same?
No, they are not the same, List is an interface while ArrayList is a class which implements List interface. ArrayList is a non-generic collection of objects whereas List is the generic version of the ArrayList, it contains elements of a specified type.
3. Is ArrayList a list or array?
ArrayList is basically a class in Java Collection Framework which implement List interface and is based on array data structure. Internally, it uses an backing array for storing objects.
4. Which is faster, List or ArrayList?
Lists are faster than ArrayList as it avoids boxing. Lists don't have to box the values that are added to them whereas ArrayList only "accepts" objects, so that means when you add any object to the ArrayList, it will have to be boxed (implicitly) and then it has to be unboxed again (explicitly) when you need the values.
Conclusion
- The ArrayList class in Java is a part of the Collection framework, and it implements the List interface.
- The backing data structure of ArrayList is an array of Object classes. ArrayList can grow and shrink dynamically.
- ArrayList class in Java has various predefined methods through which we can manipulate the elements.
- The time complexity of various operations:
- Random access takes O(1) time
- Adding element takes amortized constant time O(1)
- Inserting/Deleting takes O(n) time
- Searching takes O(n) time for unsorted array and O(log n) for a sorted one
- The implementation of an ArrayList is not synchronized, it must be synchronized externally.
- The iterators returned by the ArrayList class's iterator and listIterator methods are fail-fast, the fail-fast behavior of the iterators should be used only to detect bugs.
- Java's ArrayList overcomes the disadvantages of using arrays and makes Java programming much easier.