Sunday, 13 December 2015

ArrayList in Java

ArrayList is one of the most used collection and most of its usefulness comes from the fact that it grows dynamically. You don't have to anticipate, how many elements you are going to store in the arraylist, in advance like in the case of array. As and when elements are added list keeps growing.

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.

In this post I'll list out some of the salient features of the arraylist.

Hierarchy of the ArrayList

To know about the hierarchy of the ArrayList we 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.

Adding elements to ArrayList

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.

Third method
addAll(int index, Collection<? extends E> c)

Inserts all of the elements in the specified collection into this list, starting at the specified position.

Allows duplicates

In list there is no such restriction that duplicates elements can not be added. List does allow 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 onwards
        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.

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 the list

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

Example code using removeIf

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("Mumbai");
        
        cityList.removeIf((String name )->name.equalsIgnoreCase("Bangalore"));
        // 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 - Mumbai
City Name - Mumbai

It can be seen that Bangalore is removed from the list based on the condition provided with removeIf. 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 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.

Iterator for an ArrayList

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.

Performance of 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. 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 sort arraylist in Java
  3. How to remove duplicate elements from an ArrayList in Java
  4. How Linked List class works internally in Java
  5. How to sort arraylist of custom objects in Java
  6. CopyOnWriteArrayList in Java - The thread safe variant of ArrayList
  7. Java Collections interview questions

You may also like -

2 comments:

  1. Very nice and comprehensive reference about ArrayList.

    ReplyDelete