How To Convert Array To Dynamic Array?

Introduction

The previous lesson (How to implement array-like data structure) 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. The 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 keep in mind 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 to make this a dynamic array that resizes itself when the array 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 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

Following is the Array, we constructed in How to implement array-like data structure lesson. 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] + ", ");
    }
  }
}

Dynamic array execution class

Let us create an array with capacity as 4 and insert 9 numbers in it, the size of the array becomes 16.

Code

Following is the execution class

package dev.ggorantala.ds.arrays;

public class DynamicArrayExecution {
    private static final int[] INPUT = new int[] {1, 2, 3, 4, 5, 6, 7, 11, 9};

    public static void main(String[] args) {
        Array array = new Array(4);
        for (int value : INPUT) {
            array.insert(value);
        }

        array.remove(2); // removed element `3` from array

        System.out.println(array.get(0)); // 1
        System.out.println(array.size()); // 8

        // The extra o's are because of the array capacity which is 16
        array.print(); // 1, 2, 4, 5, 6, 7, 11, 9, 0, 0, 0, 0, 0, 0, 0, 0
    }
}

Illustrations & Explanation

We gave our array-like data structure with 9 elements {1, 2, 3, 4, 5, 6, 7, 11, 9}, But we initialized the size to 4 using Array array = new Array(4);.

A simple illustration is as follows:

So our array is ready to be loaded with input data. Our array instance size is 4, but we are inputting an array containing 9 elements.

private static final int[] INPUT = new int[] {1, 2, 3, 4, 5, 6, 7, 11, 9};

After adding the first 4 elements from the input array, our array has reached its maximum capacity. Now the insert method doubles the array size and adds the next round of 4 elements. The following illustration explains.

After adding the first 8 elements from the input array, our array has reached its maximum capacity again. Now the insert method doubles the array size and adds the next round of 1 elements from the input array. The following illustration explains.

The insert method doubles its size when the array is not sufficient, and there are extra elements to add. So the size increases from 4 to 8, then from 8 to 16.

Note: Do not get confused about the size variable and how it's doubling itself. Check the insert method that does this trick when the array is full. This is the reason you are seeing extra zeros for print() method in above code.

This concludes the lesson.