In this article, we will go over the ArrayList in great detail.

The ArrayList is part of the collection framework and it implements the List interface. As part of the collection framework, the main idea of ArrayList is to work with a group of objects.

ArrayList internally based on the array and mainly used as a dynamically sized list. We can think of ArrayList as a resizable array implementation. I think it would be useful to see the differences between ArrayList and regular array to start.

Now let’s see the code

// assume all importsList<String> colors = new ArrayList<>();
colors.add("red");
colors.add("green");
colors.add("blue");
colors.add("yellow");
System.out.println(colors); // [red, green, blue, yellow]
  • The first thing to notice in the above example is that we didn’t specify the size of our list. Because it dynamically sized list.
  • <String> this is the way we specify what data type our list should be. In our case, it is a list of Strings.
  • add(value) this method adds value to our list. It adds to the back of the list.
// assume all imports// List<int> numbers = new ArrayList<>(); does not workList<Integer> numbers = new ArrayList<>():
numbers.add(1);
numbers.add(3);
numbers.add(5);
numbers.add(7);
System.out.println(numbers); // [1, 3, 5, 7]int firstElement = numbers.get(0);
System.out.println(firstElement); // 1
System.out.println("Number of elements: " + numbers.size());int lastElement = numbers.get(numbers.size() - 1);
System.out.println(lastElement); // 7
  • ArrayList and overall the collections can work only with objects. You can see I have tried to create List<int> and it just simply didn’t compile. So I had to use the Wrapper version Integer which is an object representation of int.
  • ArrayList does maintain indexes of elements and we can get a single element by using get(index).
  • size() method returns the number of elements in the list.
// assume all importsList<String> colors = new ArrayList<>();
colors.add("green");
colors.add("red");
colors.add("blue");
colors.add("white");
System.out.println(colors); // [green, red, blue, white]// insert element at specified position
colors.add(0, "yellow");
System.out.println(colors); // [yellow, green, red, blue, white]
// set new value for element by index
colors.set(0, "black");
System.out.println(colors); // [black, green, red, blue, white]
// remove element by index
colors.remove(1);
System.out.println(colors); // [black, red, blue, white]
// remove element by value
colors.remove("blue");
System.out.println(colors); // [black, red, white]
// find index of specific element
int index = colors.indexOf("red");
System.out.println(index); // 1
// check if list contains specified element
boolean isThere = colors.contains("red");
System.out.println(isThere); // true
  • colors.add(0, "yellow"); we can insert an element at a specific position. The existing element under this index will shift to the right.
  • colors.set(0, "black"); we can change the value of the existing element by using its index.
  • colors.remove(1); we can remove elements by index.
  • colors.remove("blue"); we can remove elements by value as well.
  • colors.indexOf("red"); get an index of the specific element.
  • colors.contains("red"); check if the list contains this element.

Let’s see the ways we can iterate over the list

// assume all imports// Arrays.asList() will create fixed sized list. if you will try to add or remove value, it will throw exceptionList<Integer> list = Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15);// By using regular loop and indexes to get each element
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.pritnln();
// By using Iterator
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
// By using for each loop
for (Integer num : list) {
System.out.print(num + " ");
}
System.out.println();
// By using forEach function
list.forEach(e -> System.out.print(e + " "));
System.out.println();
// assume all imports List<Integer> list = Arrays.asList(5, 17, 42, 14, 1, 2);
System.out.println(list); // [5, 17, 42, 14, 1, 2]

// to sort list
Collections.sort(list);
System.out.println(list); // [1, 2, 5, 14, 17, 42]

// perform binary search
int index = Collections.binarySearch(list, 17);
System.out.println(index); // 4

// to reverse list
Collections.reverse(list);
System.out.println(list); // [42, 17, 14, 5, 2, 1]

// to get max number using
int max = Collections.max(list, Comparator.naturalOrder());
System.out.println(max); // 42

// to get max number using
int min = Collections.min(list, Comparator.naturalOrder());
System.out.println(min); // 1
  • Collections is helper class to work with collection framework. We need to imort it from java.util package.

One more thing I want to talk about is using streams and collections together. In our case list with stream. We can use streams starting from Java 8. The sream in Java is sequance of data or stream of data. In the flow of the stream we can inject operations that will perform some manipulations on our data and in the end we can collect the data back.

import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;

public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(4);
list.add(5);
list.add(2);
list.add(1);

System.out.println(list); // [4, 5, 2, 1]

List<Integer> evenList = list
.stream()
.filter(e -> e % 2 == 0)
.collect(Collectors.toList());
System.out.println(evenList); // [4, 2]
}
}
  • list.stream() it will make stream out of list. Basically, we are using our list as a data source for the stream.
  • filter(e -> e % 2 == 0) this is filter operation we have in our stream that accepts undefned predicate function. Basically, it’s filtering out data and keeping only even elements.
  • collect(Collectors.toList())

There is a lot more we can do with Streams in Java. This was just an example of filtering.

How does ArrayList work internally?

Ok, so far we have been playing arround with List APIs and saw how we can use it. Now, let’s dive in into internal implamentation of ArrayList.

Firstly, ArrayList is not asynchronous. It means it’s not thread safe. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

We will be mainly interested the way it grows and “shrinks” automatically.

That’s how ArrayList class declaration looks like:

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList is based on array internally and the default value of that inernal array is 10. When we will create empty ArrayList the initial size of buffer array will be 0 and when first element will get added it will have size 10.

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

and this is actual internal array:

/**
* The array buffer into which the elements are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
transient Object[] elementData; // non-private to simplify nested class access

Let’s take a look into some constructors of ArraList:

/**
* Constructs an empty list with the specified initial capacity.
*
*
@param initialCapacity the initial capacity of the list
*
@throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//That's how DEFAULTCAPACITY_EMPTY_ELEMENTDATA is look like
//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Let’s see size. This variable will represent the size of ArrayList. When new element added it will increament and when removed it will decrement.

/**
* The size of the ArrayList (the number of elements it contains).
*
*
@serial
*/
private int size;
// and our size() method /**
* Returns the number of elements in this list.
*
*
@return the number of elements in this list
*/
public int size() {
return size;
}

Now let’s see add(V) method and let’s analyze the way it grows automatically

/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}

/**
* Appends the specified element to the end of this list.
*
*
@param e element to be appended to this list
*
@return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
  • add(e, elementData, size) add method will add element to the back of the ArrayList so they are passing to helper method: e — element to add, elementData — internal buffer array, size — current size of ArrayList. New element will get added to the back of the ArrayList and size will be the index where new element will be added to internal array.
  • In the helper class s == elementData.length so if size(index where we need to add new element) is equal to the size of internal array then it’s full and they need grow array. So the grow() method getting called.
  • elementData[s] = e; and then just add value to internal array.
  • size = s + 1; increase size of ArrayList.

How do they grow the array? Let’s take a look:

/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
*
@param minCapacity the desired minimum capacity
*
@throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}

private Object[] grow() {
return grow(size + 1);
}
  • When grow() method will get called it calculates the new capacity and creates new array with that size and it will copy all existing elements to it by using Arrays.copyOf method.

We want understand how newCapacity getting calculated. It is using ArraysSupport.newLength(oldCapacity, minCapacity — oldCapacity, oldCapacity >> 1);

Let’s imagine, I have created list and filled first 10 elements and now adding 11th one. So method will get invoked like this

// oldCapacity = 10
// minCapacity = 11
// ArraysSupport.newLength(oldCapacity, minCapacity — oldCapacity, oldCapacity >> 1);
ArraySupport.newLength(10, 1, 5);
  • oldCapacity will have 10 because we call grow when only length of array and size are equal. When adding 11th element that’s exatly when they are equal.
  • minCapacity will have 11 because we are passing calling grow(size + 1)
  • >> is the signed right shift operator. Please read more here. In our case
    10 >> 1 = 5

And let’s see the newLength method itself

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0

int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}

private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError("Required array length too large");
}
if (minLength <= MAX_ARRAY_LENGTH) {
return MAX_ARRAY_LENGTH;
}
return Integer.MAX_VALUE;
}
  • int newLength = Math.max(1, 5) + 10; will give us 15. So new array will have size 15. It means all the time when we reach our internal array capacity it will grow by %50 of its original size.
  • That’s the reason they have ensureCapacity(int minCapacity) method to set capasity of internal array. Let’s say before adding a large number of elements. This may reduce the amount of resizing and copying.

Ok, let’s take a look into remove(index) method. While analyzing the source code I was expecting to see the shrinking logic of internal array. But I couldn’t find it. Basically, ArrayList will copy the array without removed element to the array of same size.

Let’s see the code:

public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;

@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);

return oldValue;
}
/**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
  • (newSize = size — 1) > i reduce size by 1 and check if removing index is not last element of ArrayList.
  • System.arraycopy(es, i + 1, es, i, newSize — i); will copy array without specified index element. This is little tricky, we will take look in more details soon.
  • es[size = new Size] = null; Makes element under index size = null
/**
* Copies an array from the specified source array, beginning at the
* specified position, to the specified position of the destination array.
*
@param src the source array.
*
@param srcPos starting position in the source array.
*
@param dest the destination array.
*
@param destPos starting position in the destination data.
*
@param length the number of array elements to be copied.
*/
@IntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);

Let’s go over the quick example:

ArrayList<Integer> nums=new ArrayList<>(Arrays.asList(1,2,3,4,5));System.out.println(nums); // [1, 2, 3, 4, 5]// remove index 2
nums.remove(2);
System.out.println(num); // [1, 2, 4, 5]

When we call remove(2);

This method System.arraycopy(es, i + 1, es, i, newSize — i); will get invoked like this

// es = internal array(we have 5 elements but it has 10)
// i = 2(index we are trying to remove)
// newSize = 4 (newSize = size - 1)
System.arraycopy([1,2,3,4,5], 3, [1,2,3,4,5], 2, 2);// indexes: 0 1 2 3 4 5 6 ...
// source array: [1, 2, 3, 4, 5, null, null, null, null, null]
// dest. array: [1, 2, 3, 4, 5, null, null, null, null, null]
// start position in source array: 3
// start position in dest. array: 2
// number of to be copied: 2
// return: [1, 2, 4, 5, 5, null, null, null, null, null]

and in the end es[size = newSize] = null; will make null the extra 5 we have in the array. Note, I’m adding nullvalues to the array because it’s size is 10 at that moment and rest of the unassing elements will have default values.

That’s all for today, thank you for reading!

Software Developer, Java Instructor https://www.techleadacademy.io/