Dynamic Array - Implementing custom ArrayList in Java

Intro

In the previous post, we covered the static arrays. Here, we will discuss and implement a dynamic array - ArrayList.

Dynamic array is a built-in class in most of the languages that is a wrapper around the static arrays.
Let's use an ArrayList class in Java as an example. 

ArrayList uses a regular (fixed-size) array as a backed data structure. With this wrapper, we can add some additional features, like adding more and more elements, disregarding the length of the backend array.

Note: The thing with arrays is if we remove an element, we need to shift all elements that come after that element - to the left, to fill in the blank.

Implementing ArrayList in Java from scratch

We will now implement our own Array List in Java:

Let's start with the basic structure:

public class ArrayList<T> {

  private static final int DEFAULT_CAPACITY = 10;

  private T[] array;
  private int size;

  public ArrayList() {
    this(DEFAULT_CAPACITY);
  }

  @SuppressWarnings("unchecked")
  public ArrayList(int size) {
    if (size < 0) {
      throw new IllegalArgumentException("Provided size must be positive number");
    }

    // initialize the array with provided size
    this.array = (T[]) new Object[size];
    this.size = 0;
  }
}

So, we have a default capacity that we set if the ArrayList is initialized using a no-arg constructor. Otherwise, we set the length (size) of the array using the provided parameter size.

Let's add a method for adding/inserting an element into ArrayList:

@SuppressWarnings("unchecked")
public void add(T data) {

  if (array.length == size) {
    System.out.println("element is: " + data);
    array = Arrays.copyOf(array, (size + (size / 2)));
  }

  array[size++] = data;
}

Here, we first check if the length of the array (in this case 10) is equal to the size of the array (size is the number of elements in the array). If yes, we increase the size of the array by 50%, by creating a new array and copying values from the old array to the new one. And we assign that to the original array.

We increment the value of size by one when we add a new element.

A method for retrieving an element based on the index position:

public T get(int index) {
  // check if index is valid
  Objects.checkIndex(index, array.length);

  return array[index];
}

Method for removing an element:

// returns true if element is removed. Otherwise returns false - in case the element is not found.
// when the element is removed, shift all elements after it to the left to fill in the blank
public boolean remove(T data) {
  int i = 0;

  if (array[array.length - 1] == data) {
    array[array.length - 1] = null;
    return true;
  }

  while (i < array.length && array[i] != data) {
    i++;
  }

  if (i == array.length) {
    return false;
  }

  while (i < array.length - 1) {
    array[i] = array[i + 1];
    i++;
  }

  array[array.length - 1] = null;

  size--;

  return true;
}

Here, we added the logic to shift all elements that come after the element that is being removed - to the left, to fill in the blank.

Method to remove an element at a specified index:

public T removeAtIndex(int index) {
  Objects.checkIndex(index, array.length);
  T element = array[index];
  int i = index;

  while (i < array.length - 1) {
    array[i] = array[i + 1];
    i++;
  }

  array[array.length - 1] = null;

  size--;

  return element;
}

Similar to the remove(T data) method, just here we immediately started from the specified index - so less code.

Replace the element at a specified index with the provided data:

public void set(T data, int index) {
  Objects.checkIndex(index, array.length);
  array[index] = data;
}

We have implemented a couple of more useful methods like isEmpty(), contains(T data), etc.

Here is the complete ArrayList class:

import java.util.Arrays;
import java.util.Objects;

public class ArrayList<T> {

  private static final int DEFAULT_CAPACITY = 5;

  private T[] array;
  private int size;

  public ArrayList() {
    this(DEFAULT_CAPACITY);
  }

  @SuppressWarnings("unchecked")
  public ArrayList(int size) {
    if (size < 0) {
      throw new IllegalArgumentException("Provided size must be positive number");
    }

    // initialize the array with provided size
    this.array = (T[]) new Object[size];
    this.size = 0;
  }

  @SuppressWarnings("unchecked")
  public void add(T data) {

    if (array.length == size) {
      System.out.println("element is: " + data);
      array = Arrays.copyOf(array, (size + (size / 2)));
    }

    array[size++] = data;
  }

  public T get(int index) {
    // check if index is valid
    Objects.checkIndex(index, array.length);

    return array[index];
  }

  // returns true if element is removed. Otherwise returns false - in case the element is not found.
  // when the element is removed, shift all elements after it to the left to fill in the blank
  public boolean remove(T data) {
    int i = 0;

    if (array[array.length - 1] == data) {
      array[array.length - 1] = null;
      return true;
    }

    while (i < array.length && array[i] != data) {
      i++;
    }

    if (i == array.length) {
      return false;
    }

    while (i < array.length - 1) {
      array[i] = array[i + 1];
      i++;
    }

    array[array.length - 1] = null;

    size--;

    return true;
  }

  public int indexOf(T data) {
    for (int i = 0; i < array.length; i++) {
      if (array[i] == data) {
        return i;
      }
    }

    return -1;
  }

  public T removeAtIndex(int index) {
    Objects.checkIndex(index, array.length);
    T element = array[index];
    int i = index;

    while (i < array.length - 1) {
      array[i] = array[i + 1];
      i++;
    }

    array[array.length - 1] = null;

    size--;

    return element;
  }

  public void set(T data, int index) {
    Objects.checkIndex(index, array.length);
    array[index] = data;
  }

  public boolean contains(T data) {
    for (int i = 0; i < array.length; i++) {
      if (array[i] == data) {
        return true;
      }
    }

    return false;
  }

  // the same as removeAll()
  public void clear() {
    Arrays.fill(array, null);
    size = 0;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public int size() {
    return size;
  }

  public void print() {
    Arrays.stream(array).forEach(item -> System.out.print(item + " "));
  }

}

Dynamic array - analysis

Let's see what is the time complexity of the most used methods:

Retrieving the element based on the index is O(1).

When it comes to adding an element - if no need for increasing the size of the backed array - the time complexity is O(1), but in case we do need to create a new array with increased size and copy the elements - it is O(n).

Retrieving the element by providing the value is O(n) since we need to iterate through the array to find the element.

Removing the element is also O(n) since we need to iterate and also shift the elements.

The conclusion is: Use the ArrayList when data reading scenarios are more common than adding or removing data.