ArrayList in Java

ArrayList vs Array
// 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.
// 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.util package.
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())

How does ArrayList work internally?

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 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
/**
* 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;
}
/**
* 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;
}
/**
* 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.length so 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 the grow() method gets called.
  • elementData[s] = e; and then just add value to the internal array.
  • size = s + 1; increase the size of ArrayList.
/**
* 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 using Arrays.copyOf method.
// 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 the length of the array and size are equal. When adding the 11th element that’s exactly when they are equal.
  • minCapacity will have 11 because we are calling grow(size + 1)
  • >> is the signed right shift operator. Please read more here. In our case
    10 >> 1 = 5
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.
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 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 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);
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]
// 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]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store