Convert Array To Dynamic/Resizable Array?

Introduction

The previous chapter has taught you how to create/implement an array-like data structure.

Converting an array from fixed size to resizing itself is the most common use-case for creating all complex data structures like ArrayList, growable arrays, and many more. Other names of dynamic arrays are mutable arrays, resizable arrays, etc.

Why resize an array in the first place?

Arrays have fixed sizes. If we were to make this fixed-size array into a dynamic array, it's doable but comes with a cost.

So why resize an array in the first place? Why can't we use the existing array?

One thing to remember about arrays is that they're fixed-size, which means you need to figure out how many elements they can hold before you start using them.

In other words, how can this be made a dynamic array that resizes itself when it is full?

This approach is expensive as it occupies extra memory. You will learn more about Memory Management later. This is just for your understanding, and traditionally this is how it's done for all the dynamic arrays, like List, HashMap, etc., in Java API.

A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

Thought process

Steps to develop an approach for an array that resizes itself when more items are added.

1. The dynamic array needs to resize itself.
2. We need to find a way to resize the array when the array is full.
3. Copy all the previous items from the old static array to the new dynamic array.
4. De-reference the old array and assign it to the new array.

In practice, for each insert, we are incrementing the size variable. So let us check to see when an array is full.

if(size == data.length) {
  // array is full
}

With this knowledge, we can create a new array that is double the previous size.

int[] newData = new int[size * 2];

Copy all the previous items in the old array into the new dynamic array.

// copy all existing items
for (int i = 0; i < size; i += 1) {
	newData[i] = data[i];
}

With all these changes in place, insert method looks something like this:

 public void insert(int element) {

    // if the array is full, resize it
    if (data.length == size) {
      // create a new array (twice the size)
      int[] newData = new int[size * 2];

      // copy all existing items
      for (int i = 0; i < size; i += 1) {
        newData[i] = data[i];
      }
      data = newData;
    }
    data[size] = element;
    size++;
  }

Code

The final code is as follows:

package dev.ggorantala.ds.arrays;

public class Array {
  private int[] data;
  private int size;

  public Array(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  public void insert(int element) {

    // if the array is full, resize it
    if (data.length == size) {
      // create a new array (twice the size)
      int[] newData = new int[size * 2];

      // copy all existing items
      for (int i = 0; i < size; i += 1) {
        newData[i] = data[i];
      }
      data = newData;
    }
    data[size] = element;
    size++;
  }

  public boolean isOutOfBounds(int index) {
    return index < 0 || index >= size;
  }

  public void remove(int index) {
    if (isOutOfBounds(index)) {
      throw new IndexOutOfBoundsException();
    }

    for (int i = index; i < size; i += 1) {
      data[i] = data[i + 1];
    }
    size--;
  }

  public int get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    return data[index];
  }

  public int size() {
    return size;
  }

  public void print() {
    for (int i = 0; i < data.length; i += 1) {
      System.out.print(data[i] + ", ");
    }
  }
}