Tuesday, December 4, 2018

ArrayList in Java With Examples

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.


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.

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.

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.

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.

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.

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

  1. How ArrayList Works Internally in Java
  2. How to Remove Duplicate Elements From an ArrayList in Java
  3. How LinkedList Class Works Internally in Java
  4. How to Sort ArrayList of Custom Objects in Java
  5. Java Collections Interview Questions

You may also like-

  1. CopyOnWriteArrayList in Java - The thread safe variant of ArrayList
  2. How to Iterate a HashMap of ArrayLists of String in Java
  3. How does HashMap internally work in Java
  4. varargs in Java
  5. What if run() method called directly instead of start() method
  6. Initializer Block in Java
  7. static import in Java
  8. Serialization in Java