How ArrayList Works Internally in Java

ArrayList arguably would be the most used collection along with the HashMap. Many of us programmers whip up code everyday which contains atleast one of these data structures to hold objects. I have already discussed how HashMap works internally in Java, in this post I'll try to explain how ArrayList internally works in Java.

As most of us would already be knowing that ArrayList is a Resizable-array implementation of the List interface i.e. ArrayList grows dynamically as the elements are added to it. So let's try to get clear idea about the following points-

• How ArrayList is internally implemented in Java.
• What is the backing data structure for an ArrayList.
• How it grows dynamically and ensures that there is always room to add elements.

Because of all these side questions it is also a very important Java Collections interview question.

Note that the code of ArrayList used here for reference is from Java 17

Table of contents

1. Where does ArrayList internally store elements
2. What happens when ArrayList is created
3. How does ArrayList grow dynamically
4. What happens when an element is removed from ArrayList

Where does ArrayList internally store elements

Basic data structure used by Java ArrayList to store objects is an array of Object class, which is defined as follows-

transient Object[] elementData;

I am sure many of you would be thinking why transient and how about serializing an ArrayList then?
ArrayList provides its own version of readObject and writeObject methods so no problem in serializing an ArrayList and that is the reason, I think, of making this Object array as transient.

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.

Refer How does ArrayList work internally in Java to know more about how does ArrayList work internally in Java.

Table of contents

1. Hierarchy of the ArrayList
2. Features of ArrayList
3. Java ArrayList constructors
4. Creating ArrayList and adding elements to it
5. Java ArrayList allows duplicates
6. Java ArrayList allows any number of nulls
7. Removing elements from an ArrayList
8. ArrayList is not synchronized
9. Java ArrayList iterator
10. 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.

Difference Between ArrayList And Vector in Java

In many ways Vector class in Java is just like ArrayList apart from some differences and this post is about those differences between the ArrayList and Vector in Java.

There are many similarities between Vector and ArrayList classes in Java. Vector, just like ArrayList, is also a growable dynamic array. As of Java v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework.

With JDK 5 it was also retrofitted for generics and implements Iterable interface too which means it can also use enhanced for loop.

ArrayList Vs Vector in Java

• ArrayList is not synchronized whereas Vector is Synchronized. Which means that the methods in the Vector class are Synchronized making Vector thread-safe and ready to use as-is in a multi-threaded environment.
  ArrayList, if needed in a multi-threaded environment, has to be synchronized externally using Collections.synchronizedList method which returns a synchronized (thread-safe) list backed by the specified list.

Refer How and why to synchronize ArrayList in Java to know how to synchronize an ArrayList.

• A Vector, by default, doubles the size of its array when it needs to expand the array, while the ArrayList increases its array size by 50 percent.
• As mentioned though Vector is retrofitted to implement the List interface it still has legacy methods which are not there in ArrayList. As Example methods like addElement(), removeElement(), capacity() which are there in Vector class but not in ArrayList.
• Performance wise Vector is comparatively slower than the ArrayList because it is synchronized. That means only one thread can access method of Vector at the time and there is an overhead of acquiring lock on the object too.
• For traversing an ArrayList as well as Vector, Iterator or ListIterator can be used. That Iterator/ListIterator is fail-fast and throws ConcurrentModificationException if any other Thread modifies the map structurally by adding or removing any element except Iterator's own remove() method.
  For Vector enumeration can also be used for traversing which is not fail-fast.

That's all for this topic Difference Between ArrayList And Vector in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page | Return to Java Collections Framework Tutorial Page>>>

---

Related Topics

1. Difference Between ArrayList And LinkedList in Java
2. Difference Between Array And ArrayList in Java
3. Difference Between ArrayList And CopyOnWriteArrayList in Java
4. How to Remove Elements From an ArrayList in Java
5. Java Collections Interview Questions And Answers

You may also like-

1. Fail-Fast Vs Fail-Safe Iterator in Java
2. How to Sort HashSet in Java
3. Difference Between Comparable and Comparator in Java
4. Polymorphism in Java
5. Array in Java With Examples
6. finalize method in Java
7. Nested Try Statements in Java Exception Handling
8. Spring Boot Event Driven Microservice With Kafka

How to Sort an ArrayList in Descending Order in Java

In Java ArrayList elements are added in sequential order and while iterating an ArrayList same sequential order will be used to retrieve the elements. Sometimes you may have a requirement to sort an ArrayList in ascending or descending order. In this post we'll see how to sort an ArrayList in descending order in Java.

Sorting ArrayList in descending order

For sorting ArrayList in descending order in Java there are following options

1. Use method reverseOrder() provided by Collections class. See example.

General form and description

public static <T> Comparator<T> reverseOrder()

Returns a comparator that imposes the reverse of the natural ordering on a collection of objects that implement the Comparable interface.

There is also a Comparator.reverseOrder() method Java 8 onward that can also be used.

2. Using a custom comparator. See example.

3. You can also sort Java ArrayList in descending order using Java Stream API's sorted() method and then collect it into a separate List. That way you can retain the original list. See example.

You must also know about the overloaded sort method provided by the Collections class.

• public static <T> void sort(List<T> list, Comparator<? super T> c)- Sorts the specified list according to the order induced by the specified comparator. All elements in the list must be mutually comparable using the specified comparator (that is, c.compare(e1, e2)must not throw a ClassCastException for any elements e1 and e2 in the list).

Sorting ArrayList Using reverseOrder method

reverseOrder() method mentioned above can be provided as the second parameter in the sort() method mentioned above and you will get the ArrayList sorted in reverse order. Let's see an example.

In the program Collections.reverseOrder() method is passed as an argument to the Collections.sort() method to sort ArrayList in reverse order.

public class SortListDemo {
  public static void main(String[] args) {
    // Using diamond operator (Right side no type specified)
    // Available from Java7 onwards
    List<String> cityList = new ArrayList<>();
    cityList.add("Delhi");
    cityList.add("Mumbai");
    cityList.add("Bangalore");
    cityList.add("Chennai");
    cityList.add("Kolkata");
    cityList.add("Mumbai");
    // sorting the list in descending order
    Collections.sort(cityList, Collections.reverseOrder());
    //Displaying the list
    for(String city : cityList){
      System.out.println("Name " + city);
    }
  }
}

Output

Name Mumbai
Name Mumbai
Name Kolkata
Name Delhi
Name Chennai
Name Bangalore

Java 8 onward there is also a Comparator.reverseOrder() method that can be used to sort an ArrayList in descending order in Java.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class SortListDemo {
  public static void main(String[] args) {
    List<String> cityList = new ArrayList<>();
    cityList.add("Delhi");
    cityList.add("Mumbai");
    cityList.add("Bangalore");
    cityList.add("Chennai");
    cityList.add("Kolkata");
    cityList.add("Mumbai");
    
    cityList.sort(Comparator.reverseOrder());
    System.out.println(cityList);

  }
}

Sorting Java ArrayList