In this article, we will go over the ArrayList in great detail.
The ArrayList is part of the collection framework and implements the List interface. As part of the collection framework, the main idea of ArrayList is to work with a group of objects.
ArrayList is internally based on the array and is 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); // 1System.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 a helper class to work with the collection framework. We need to import it from
java.utilpackage.
One more thing I want to talk about is using streams and collections together. In our case list with the stream. We can use streams starting from Java 8. The stream in Java is a sequence of data or a 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 the list. Basically, we are using our list as a data source for the stream.filter(e -> e % 2 == 0)this is a filter operation we have in our stream that accepts 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 around with List APIs and saw how we can use them. Now, let’s dive into the internal implementation of ArrayList.
Firstly, ArrayList is not asynchronous. It means it’s not threaded 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 in 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.SerializableArrayList is based on an array internally and the default value of that internal array is 10. When we will create an empty ArrayList the initial size of the buffer array will be 0 and when the first element will get added it will have a size 10.
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;and this is the 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 accessLet’s take a look into some constructors of ArrayList:
/**
* 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 a new element is added it will increment 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 elements to the back of the ArrayList so they are passing to the helper method:e— element to add,elementData— internal buffer array,size— the current size of ArrayList. The new element will get added to the back of the ArrayList and the size will be the index where the new element will be added to the internal array.- In the helper class
s == elementData.lengthso if the size(index where we need to add a new element) is equal to the size of the internal array then it’s full and they need to grow the array. So thegrow()method gets called. elementData[s] = e;and then just add value to the internal array.size = s + 1;increase the 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 a new array with that size and it will copy all existing elements to it by usingArrays.copyOfmethod.
Let’s see how newCapacity getting calculated. It is using ArraysSupport.newLength(oldCapacity, minCapacity — oldCapacity, oldCapacity >> 1);
Let’s imagine, I have created a list and filled the first 10 elements and now adding the 11th one. So the method will get invoked like this
// oldCapacity = 10
// minCapacity = 11
// ArraysSupport.newLength(oldCapacity, minCapacity — oldCapacity, oldCapacity >> 1);ArraySupport.newLength(10, 1, 5);
oldCapacitywill have 10 because we call grow when only the length of the array and size are equal. When adding the 11th element that’s exactly when they are equal.minCapacitywill have 11 because we are callinggrow(size + 1)>>is the signed right shift operator. Please read more here. In our case10 >> 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 a 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 the capacity of the 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 the internal array. But I couldn’t find it. Basically, ArrayList will copy the array without changing the size of the underlying array.
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) > ireduce the size by 1 and check if removing the index is not the last element of ArrayList.System.arraycopy(es, i + 1, es, i, newSize — i);will copy array without specified index element. This is a little tricky, we will take look in more detail soon.es[size = new Size] = null;Makes elements under the indexsize=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 a 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 its size is 10 at that moment and the rest of the unassing elements will have default values.
That’s all for today, thank you for reading!
Please take my Java Course for video lectures.This article is part of the series of articles to learn Java programming language from Tech Lead Academy:Introduction to programming
OS, File, and File System
Working with terminal
Welcome to Java Programming Language
Variables and Primitives in Java
Convert String to numeric data type
Input from the terminal in Java
Methods with Java
Java Math Operators and special operators
Conditional branching in Java
Switch statement in Java
Ternary operator in Java
Enum in Java
String class and its methods in Java
Loops in Java
Access modifiers in Java
Static keyword in Java
The final keyword in Java
Class and Object in Java
Object-Oriented Programming in Java
OOP: Encapsulation in Java
OOP: Inheritance in Java
OOP: Abstraction in Java
OOP: Polymorphism in Java
The method Overriding vs Overloading in Java
Array in Java
Data Structures with Java
Collection framework in Java
ArrayList in Java
Set in Java
Map in Java
Date and Time in Java
Exception in Java
How to work with files in Java
Design Patterns
Generics in Java
Multithreading in java
Annotations in Java
Reflection in Java
Reflection & Annotations - The Powerful Combination
Run terminal commands from Java
Lambda in Java
Unit Testing in Java
Big O Notation for coding interviews
Top Java coding interview questions for SDET
