Dynamic Arrays

In my last post, I discussed static arrays. While this info is useful for strictly typed languages, many concepts do not roll over to languages like JS and Python. In these languages, dynamic arrays are the norm. The difference between the two array types is that dynamic arrays do not require us to specify a size when we initialize them. Different languages will handle this differently. In Java for example, ArrayLists (the dynamic arrays of Java) have a default size of 10.

// Let's create a dynamic array in Java!

// First, we create the class
public class DynamicArray {
    int capacity;
    int length;;
    int[] arr;

    // Initialize the Dynamic Array to start with 10 elements
    public DynamicArray() {
        capacity = 10;
        length = 0;
        arr = new int[10];
    }
}

We created the class and the default constructor. Now we need to add an append to push new elements to the end of our dynamic array. Let’s create a resize to double the dynamic array’s size when it reaches capacity.

    public void resize() {
        // Double capacity
        capacity = 2 * capacity;
        int[] newArr = new int[capacity]; 
        
        // Copy elements
        for (int i = 0; i < length; i++) {
            newArr[i] = arr[i];
        }
        arr = newArr;
    }  

    public void append(int n) {
        if (length == capacity) {
            this.resize();
        }
               
        // insert at next empty position
        arr[length] = n;
        length++;
    }

And the rest of the functionality implemented:

    // Remove the last element in the array
    public void popback() {
        if (length > 0) {
            length--;
        }  
    }     

    // Get value at i-th index
    public int get(int i) {
        if (i < length) {
            return arr[i];
        }    
        // Here we would throw an out of bounds exception
        return -1;
    }    

    // Insert n at i-th index
    public void insert(int i, int n) {
        if (i < length) {
            arr[i] = n;
            return;
        }    
        return;
        // Here we would throw an out of bounds exception  
    }        

    public void print() {
        for (int i = 0; i < length; i++) {
            System.out.println(arr[i]);
        }
    }

While static arrays have read and write at O(1) time complexity, dynamic arrays only have O(1) time if we are inserting or deleting at the end. Otherwise, it is O(n) time.

Java code from Neetcode.io.