Java ArrayList is one of the most used collection and most of its usefulness comes from the fact that it grows dynamically. Contrary to arrays you don't have to anticipate in advance how many elements you are going to store in the ArrayList. As and when elements are added ArrayList keeps growing, if required.
Though internally it is not really some "elastic" array which keeps growing, it is as simple as having an array with an initial capacity (default is array of length 10). When that limit is crossed another array is created which is 1.5 times the original array and the elements from the old array are copied to the new array.
- Refer How does ArrayList work internally in Java to know more about how does ArrayList work internally in Java.
- Hierarchy of the ArrayList
- Features of ArrayList
- Java ArrayList constructors
- Creating ArrayList and adding elements to it
- Java ArrayList allows duplicates
- Java ArrayList allows any number of nulls
- Removing elements from an ArrayList
- ArrayList is not synchronized
- Java ArrayList iterator
- Performance of Java ArrayList
Hierarchy of the ArrayList
To know the hierarchy of java.util.ArrayList you need to know about 2 interfaces and 2 abstract classes.
- Collection Interface- Collection interface is the core of the Collection Framework. It must be implemented by any class that defines a collection.
- List interface- List interface extends Collection interface. Apart from extending all the methods of the Collection interface, List interface defines some methods of its own.
- AbstractCollection- Abstract class which implements most of the methods of the Collection interface.
- AbstractList- Abstract class which extends AbstractCollection and implements most of the List interface.
ArrayList extends AbstractList and implements List interface too. Apart from List interface, ArrayList also implements RandomAccess, Cloneable, java.io.Serializable interfaces.
Features of ArrayList
In this post we'll see in detail some of the salient features of the ArrayList in Java which are as follows.
- ArrayList is a Resizable-array implementation of the List interface. It can grow dynamically if more elements are to be added after the capacity is reached. Same way when the elements are removed from the ArrayList it shrinks by shifting the other elements to fill the space created by the removed element.
- Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list.
- In ArrayList insertion order of the elements is maintained which means it is an ordered collection.
- ArrayList in Java can contain duplicate values. Any number of null elements are also allowed.
- ArrayList in Java is not thread-safe. In a multi-threaded environment if multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.
- The iterators returned by ArrayList's iterator and listIterator methods are fail-fast. If the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.
Java ArrayList constructors
ArrayList class has the following three constructors.
- ArrayList()- Constructs an empty list with an initial capacity of ten.
- ArrayList(Collection<? extends E> c)- Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
- ArrayList(int initialCapacity)- Constructs an empty list with the specified initial capacity.
Creating ArrayList and adding elements to it
List provides a method add(E e) which appends specified element to the end of the list. Using add(E e) method will mean keep adding elements sequentially to the list.
Apart from that there is another add method-
- add(int index, E element)- This method inserts the specified element at the specified position in this list.
There are other variants of add method too that can add the specified collection into the List. You can get the list of all methods in ArrayList class here.
public class ArrayListDemo {
public static void main(String[] args) {
// List with initial capacity as 2
List<String> cityList = new ArrayList<>(2);
cityList.add("London");
cityList.add("Paris");
cityList.add("Bangalore");
// With index
cityList.add(3, "Istanbul");
for(String name : cityList){
System.out.println("City Name - " + name);
}
}
}
Output
City Name - London City Name - Paris City Name - Bangalore City Name - Istanbul
In the code you can see that the ArrayList is created with the initial capacity as 2 still 4 elements are added to it. Internally ArrayList has been resized to accommodate more elements. Also from the output you can see that the elements are inserted in the same order as they are added, so the insertion order is maintained.
Java ArrayList allows duplicates
ArrayList in Java allows duplicate elements to be added.
public class LoopListDemo {
public static void main(String[] args) {
// Using Diamond operator, so with ArrayList
// don't need to provide String, this option is available from
// Java 7 onward
List<String> cityList = new ArrayList<>();
cityList.add("Delhi");
cityList.add("Mumbai");
cityList.add("Bangalore");
cityList.add("Mumbai");
cityList.add("Mumbai");
// Using for-each loop
System.out.println("With for-each loop - Java 5");
for(String name : cityList){
System.out.println("City Name - " + name);
}
}
}
Output
With for-each loop - Java 5 City Name - Delhi City Name - Mumbai City Name - Bangalore City Name - Mumbai City Name - Mumbai
Here it can be seen that Mumbai is added 3 times and when I am looping the list and displaying the elements in the list it is showing Mumbai 3 times.
Java ArrayList allows any number of nulls
In ArrayList any number of nulls can be added. Let's see it with an example.
public class LoopListDemo {
public static void main(String[] args) {
// Using Diamond operator, so with ArrayList
// don't need to provide String, this option is available from
// Java 7 onwards
List<String> cityList = new ArrayList<>();
cityList.add("Delhi");
cityList.add("Mumbai");
cityList.add("Bangalore");
cityList.add("Mumbai");
cityList.add(null);
cityList.add("Mumbai");
cityList.add(null);
// Using for-each loop
System.out.println("With for-each loop - Java 5");
for(String name : cityList){
System.out.println("City Name - " + name);
//cityList.remove(2);
}
}
}
Output
With for-each loop - Java 5 City Name - Delhi City Name - Mumbai City Name - Bangalore City Name - Mumbai City Name - null City Name - Mumbai City Name - null
It can be seen here that two null elements are added in the AraryList.
Removing elements from an ArrayList
ArrayList provides several methods to remove elements from the List. Since ArrayList internally uses array to store elements, one point to note here is that when an element is removed from the List internally the remaining elements are shifted to fill the gap created in the underlying array.
- clear()- Removes all of the elements from this list.
- remove(int index)- Removes the element at the specified position in this list.
- remove(Object o)- Removes the first occurrence of the specified element from this list, if it is present.
- removeAll(Collection<?> c)- Removes from this list all of its elements that are contained in the specified collection.
- removeIf(Predicate<? super E> filter)- Removes all of the elements of this collection that satisfy the given predicate. Note that removeIf is added in Java 8.
public class ArrayListDemo {
public static void main(String[] args) {
// List with initial capacity as 2
List<String> cityList = new ArrayList<>(2);
cityList.add("London");
cityList.add("Paris");
cityList.add("Bangalore");
cityList.add("Istanbul");
cityList.add("Delhi");
cityList.add("Houston");
System.out.println("Original List- ");
for(String name : cityList){
System.out.println("City Name - " + name);
}
// Removing element at index 3
String cityName = cityList.remove(3);
System.out.println("Removed from the List- " + cityName);
// using removeIf with a predicate
cityList.removeIf((String name )->name.equalsIgnoreCase("Bangalore"));
System.out.println("List after removal of elements-");
for(String name : cityList){
System.out.println("City Name - " + name);
}
}
}
Output
Original List- City Name - London City Name - Paris City Name - Bangalore City Name - Istanbul City Name - Delhi City Name - Houston Removed from the List- Istanbul List after removal of elements- City Name - London City Name - Paris City Name - Delhi City Name - Houston
Note that parameter for the removeIf is of type Predicate which is a functional interface, so it's method can be implemented using lambda expression.
- Refer How to remove elements from an ArrayList in Java to see Java program for removing elements from Arraylist.
ArrayList is not synchronized
ArrayList in Java is not synchronized. That means sharing an instance of ArrayList among many threads where those threads are modifying the collection (adding or removing the values) may result in unpredictable behaviour. If we need to synchronize an ArrayList you can use synchronizedList method provided by Collections class, which returns a synchronized (thread-safe) list backed by the specified list.
- Refer How and why to synchronize ArrayList in Java to read more about Synchronization and ArrayList.
- Refer CopyOnWriteArrayList in Java to know about a thread-safe variant of ArrayList.
Java ArrayList iterator
ArrayList provides iterator to traverse the list in a sequential manner. Since ArrayList implements List interface so it provides ListIterator too which is different from the iterator in a way that it provides iteration in both directions.
- Refer List iterator in Java to know more about List Iterator in Java.
- Refer How to loop/iterate an arraylist in Java to know more about How to iterate a List in Java.
One point to note here is that both iterator and listiterator are fail fast, fail-fast iterator fails if the underlying collection is structurally modified at any time after the iterator is created, thus the iterator will throw a ConcurrentModificationException if the underlying collection is structurally modified in any way except through the iterator's own remove or add (if applicable as in list-iterator) methods.
Structurally modifying ArrayList while iterating
public class ArrayListDemo {
public static void main(String[] args) {
// List with initial capacity as 2
List<String> cityList = new ArrayList<>(2);
cityList.add("London");
cityList.add("Paris");
cityList.add("Bangalore");
cityList.add("Istanbul");
Iterator<String> itr = cityList.iterator();
while(itr.hasNext()){
String city = itr.next();
if(city.equals("Paris")){
// removing using remove method
// of the ArrayList class
cityList.remove(city);
}
}
}
}
Output
Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901) at java.util.ArrayList$Itr.next(ArrayList.java:851) at org.netjs.examples.ArrayListDemo.main(ArrayListDemo.java:18)
As you can see ConcurrentModificationException is thrown here as there is an attempt to remove an element from the ArrayList.
Modifying ArrayList using iterator's remove method
public class ArrayListDemo {
public static void main(String[] args) {
// List with initial capacity as 2
List<String> cityList = new ArrayList<>(2);
cityList.add("London");
cityList.add("Paris");
cityList.add("Bangalore");
cityList.add("Istanbul");
Iterator<String> itr = cityList.iterator();
while(itr.hasNext()){
String city = itr.next();
if(city.equals("Paris")){
itr.remove();
}
}
// iterating after removal
for(String name : cityList){
System.out.println("City Name - " + name);
}
}
}
Output
City Name - London City Name - Bangalore City Name - Istanbul
Now ConcurrentModificationException is not thrown as iterator's remove method is used to remove element from the ArrayList.
- Refer fail-fast Vs fail-safe iterator in Java to know more about fail-fast and fail-safe iterator.
Performance of Java ArrayList
- Adding an element- If you are adding at the end using add(E e) method it is O(1). Even in the case of adding at the last ArrayList may give O(n) performance in the worst case. That will happen if you add more elements than the capacity of the underlying array, as in that case a new array (1.5 times the last size) is created, and the old array is copied to the new one. If you are using add(int index, E element) then it is O(n - index) and it'll become O(n) if every time element is added at the beginning of the list.
- Retrieving an element- Since ArrayList internally uses an array to store elements so get(int index) means going to that index directly in the array. So, for ArrayList get(int index) is O(1).
- Removing an element- If you are removing using the remove(int index) method then, in case of ArrayList getting to that index is fast but removing will mean shuffling the remaining elements to fill the gap created by the removed element with in the underlying array. It ranges from O(1) for removing the last element to O(n). Thus it can be said remove(int index) operation is O(n - index) for the arraylist.
- Refer Difference between ArrayList and LinkedList in Java to know about the performance of ArrayList and LinkedList for various operations.
That's all for this topic ArrayList in Java With Examples. If you have any doubt or any suggestions to make please drop a comment. Thanks!
Related Topics
You may also like-
