Array Data Structure with Java

The array data structure is probably the most used in every application. If not directly used it’s indirectly used with ArrayList, ArrayDeque, Vector, and other classes.

Simply put, an array is a data structure that stores multiple variables into it so that there is no need to create many variables with different names.

Arrays in Java are always an object, therefore, they will occupy space in the memory heap and it will create a reference for this object.

Array Memory Allocation

The array is stored in the memory RAM and takes up space back to back. Most memory RAM stores 1 byte (8 bits) in each space. In Java, each primitive int number occupies 4 bytes in memory. Therefore, let’s how this would work in the following memory model if we create an array with 5 int elements:

As you can see in the above diagram, when we are creating an array we must pass the type of the elements and size from it. That’s because when creating the array the memory allocation has to be back to back.

That’s the reason why we can very quickly access an element from an array. Since we know where the array starts, in the case of the diagram above it’s in the memory address 5, the compiler makes a simple calculation.

Considering the index we pass to the array, the size, and the type of the element, we can easily calculate where the element is present in memory. To get the second element from the array, for example, we would add 4 bytes to the first element index and we would know where the second element is allocated. For this reason, to access an element in an array the time complexity will be always O(1).

To change an element in the array is also constant time O(1). That’s because we can quickly access the variable index and assign a new value to it.

To create an array the time complexity is O(n) because when creating it, we will define the type and size of the array and the required space in memory will be allocated.

Static Arrays

As the name suggests, a static array is an array that can’t be changed. We need to pass the type and size of the array and after that, we can’t change the type or size of the array.

Let’s see in the following code how to create a static array with the int type and show all the elements:

int[] array = {1, 2, 3, 4, 5}; // Create an array O(n)
for (int i = 0; i < array.length; i++) {
  System.out.print(array[i] + " ");
}

Output:
1 2 3 4 5

Notice in the code above that we create an array of int values. Once it’s created we can’t change either the type or the size of the array, that’s what makes it static.

Then we access each element of the array by index and show the values that will be 0 because those are the default values for primitive int in Java.

Insert an Element in the Middle of the Array

To insert an element in the middle of the array it will be necessary to shift the elements. Therefore, the time complexity will be O(n).

Let’s imagine we want to put 3 in the middle of 2 and 4 in the following array: { 1, 2, 4, 5 }. To do that, we will have to first create a new array with the size of 5.

Then, it will be necessary to move elements 4 and 5 to one position ahead. Once this is done we can access index 2 and insert element 3.

Dynamic Arrays

There are classes in Java that make use of a dynamic array such as ArrayList, Vector, and others. When we create an ArrayList, we have a static array under the hood that starts as empty but after adding the first element the size goes to 10. Then it doubles every time it’s needed as you can see in the following code of the JVM:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    private int size;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // This is the method that will double the array whenever it's needed
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity &gt;&gt; 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

    // Omitted other methods...

}

The elementData variable is the one that will store the data behind the scenes for the ArrayList. Therefore, notice that the dynamic array actually manipulates a static array to behave as dynamic.

When adding an element to an ArrayList, it will check if the size is greater than 10 and if that is true the time complexity will be O(n). That happens because since the array was created with the size of 10, it’s necessary to create a new array with the size of 20 copying all the elements into the new one. To do so, we need to traverse the whole array and copy element by element. Then we add the 11th element to the array.

When the array behind the scenes is created with the size of 20 then whenever we add an element we will have the time complexity of O(1). Notice that the vast majority of the time when adding an element to a dynamic array will be pretty fast, it will be O(1). Only on the edge-case scenarios when the array size needs to be doubled the time complexity will be O(n). This is also called amortized complexity.

Summary

• An array is allocated in memory from back to back.
• Accessing an array by index has the time complexity of O(1), it’s pretty fast.
• Static array is the array that is created with a size and a type pre-defined.
• Dynamic array is an adaptation of the static array that automatically resizes it when necessary.
• A dynamic array will double its size when necessary.
• Adding an element to a dynamic array will be mostly O(1) because there will be space more often.
• When adding an element to a dynamic array exceeds the size of the static array under the hood, it will be necessary to create a new array, copy the elements from the existing array, then add the new element. Therefore, the time complexity will be O(n).
• Adding an element in the middle of the array will have the time complexity of O(n). That’s because it will be necessary to shift all the elements from the right side to one position on the right. Only then we will be able to insert the element by index.
• To remove the first element from the array, it will be necessary to shift all the elements from the right to the left. Therefore, the time complexity is O(n).
• To remove an element from the array in the last position takes O(1) complexity. That’s because we only need to remove the last value and we have direct access to it.