Dynamic Arrays vs Traditional Arrays, With Illustrations and Examples

In this article, you will learn how to resize a static array. Most of the advanced and complex data structures are built on arrays.

Introduction

Arrays are fixed size. You need to specify the number of elements your array will hold ahead of time.

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.

A dynamic array resizes or expands when you add more elements than the capacity of the array.

Strengths

1. Fast lookups

Retrieving the element at a given index takes O(1) time, regardless of the array's length.

2. Array size

You can add as many elements as you need. There is no limitation. Dynamic arrays expand to hold them.

3. Cache friendly

Just like arrays, dynamic arrays place items right next to each other in memory, making efficient use of caches.

Weaknesses

1. Size doubling appends

Let us consider an array with a capacity of 5 elements.

But the elements we want to store in this array are more, which means we have to double the size, create a new array, copy the old array elements and add new elements, which takes O(n) time.

2. Costly inserts

Inserting an element at the end of the array takes O(1) time. But, inserting an element at the start/middle of the array takes O(n) time. Why?

If we want to insert something into an array, first, we have to make space by "scooting over" everything starting at the index we're inserting into, as shown in the image. In the worst case, we're inserting into the 0th index in the array (prepending), so we have to "scoot over" everything in the array.

That's O(n) time.

Inserting an element at the 2nd index and moving the rest of the element right shift each once. The resultant array becomes – { A, B, C, D, E }.

I recommend you read Array insertions and shifting algorithms(link below) with a clear explanation with code snippets and sketches to understand why these inserts are expensive at the start and middle.

3. Costly deletes

Deleting an element at the end of the array takes O(1) time, which is the best case. In computer science, we only care about the worse case scenarios when working on algorithms. But, when we remove an element from the middle or start of the array, we have to fill the gap by scooting over all the elements after it. This will be O(n) if we consider a case of deleting an element from the 0th index.

Deleting an element at the 3rd index and filling the gap by left-shifting the rest of the elements; the resultant array becomes – { A, B, C, D, E }.

Big-O worst-case time complexities

Operation	Worst-Case Time Complexity
Lookup/access a value at a given index	O(1)
Update a value at a given index	O(1)
Insert at the beginning/middle	O(N)
Insert at the end for dynamic array	O(N)
Insert at the end for Static array	O(1)
Append at the end	O(1)
Delete at the beginning/middle	O(N)
Delete at the end	O(1)
copying the array	O(N)

How To Convert Array to Dynamic/resizable array?

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 article. 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 dynamic array topic. In the next lessons, you will learn about the 2-Dimensional arrays with illustrations and sketches detailing indexes.

Comments

[Chloe-Ku]

shouldn't the "Insert at the end for Static array" be O(1)?

[Gopi Gorantala]

The table has a typo error. Thank you for pointing out the typo mistake I updated the article.