Internal implementation of ArrayList

An ArrayList is a very common data structure used by Java developers. It is an implementation of the List interface and is used to store a list of values/ objects. Unlike normal arrays in Java, it is a dynamic data structure which means its size dynamically increases when its current capacity is exhausted.


The AbstractList class

The ArrayList extends the AbstractList class, which provides a skeletal implementation of the List interface to provides random access to the objects in the list. For sequential access AbstractSequentialList can be used, since ArrayList provides random access it extends the AbstractList class.

The AbstractList class also provides implementations of Iterator and ListIterator on top of random access methods like get(), set(), add() and remove(), so that the programmer does not have to provide his own implementation while implementing a List.


Internal Storage and Growth Policy

An ArrayList stores data in an internal array, which it initializes to a default size of 10, if not otherwise specified in the constructor.

transient Object[] elementData;

private static final int DEFAULT_CAPACITY = 10;

It dynamically increases size of the internal array when the available size is exhausted. Shown below is the code snippet from ArrayList class which is used to grow the internal array size.

public void  ensureCapacity(int minCapacity) {
   modCount++;
   int oldCapacity = elementData.length;
   if (minCapacity > oldCapacity) {
   	Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity) newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity); } }

Note that the growth policy may differ with different versions of JDK, the above code shows the growth policy of ArrayList in JDK 6.


ModCount

ArrayList is roughly similar to Vector, except that it is unsynchronized. If an ArrayList is supposed to be used in a multi-threaded application it should be synchronized externally.

To synchronize an ArrayList we can use the Collections.synchronizedList() method as shown below:

List myList = Collections.synchronizedList(new ArrayList());

It maintains a ‘modCount’ variable, declared in AbstractList, to keep track of the structural modifications made to it. The modCount increases each time the ArrayList is modified structurally. A structural modification is any operation that adds or deletes one or more elements in the ArrayList.

The ‘modCount’ serves as a version that keeps track of modification to the ArrayList and is used to throw ConcurrentModificationException in a multi-threaded environment, when any thread tries to modify the ArrayList, while another thread is iterating on it.

RELATED ARTICLES

Understanding equals() and hashCode() methods

The equals() and hashCode() are two primary methods of Java's Object Class which work together to uniquely identify any object in Java.

View Article

Internal Implementation of HashMap

HashMap is popular data structure in Java which stores data in key-value format. This article describes the internal implementation to store and retrieve data in a hashmap.

View Article

Internal Implementation of HashSet

HashSet is a member of the Java Collection Framework which is used to store unique entries. This article describes how a HashSet is internally implemented to store unique entries.

View Article

Identity HashMap in Java

IdentityHashMap in Java is a special implentation of the Map interface designed to be used in special cases where reference equality is required.

View Article

Iterator and ListIterator in Java

The Java API provides the Iterator and ListIterator that are used to iterate over a Collection. This article covers the difference between the two and discuss how Emumeration is different from Iterat.

View Article

Introduction to Java Collections

The Java collections framework is a library that provides commonly reusable collection data structures. It consists of a set of various interfaces, implementations and algorithms used to represent...

View Article

Understanding TreeMap

A TreeMap is an implementation of the Map interface used to store key-value pair in sorted order of their keys. This articles describe how a Treemap is implemented in Java.

View Article