Array Data Structure

In this article, we have explored Array Data Structure in depth. We explore key ideas in Array and how we develop our own custom implementation of Array along with different Array operations.

Table of contents:

1. Introduction to Array
2. Multi-Dimensional Array
3. Implementation of Array
4. Set an Element
5. Add an element in Array
6. Get element at an Index
7. Delete by Index
8. Remove by Element

Pre-requisites:

• Time Complexity Analysis of Array
• List of Array Practice Problems
• Array vs Linked List

Introduction to Array

An Array is the most fundamental Data Structure in Computer Science. It can be thought as an contiguous set of elements and has a specific order of elements.

Array can be visualized as follows:

Index is the position ID of each element. So, i^th has an index "i-1". Indexing starts from 0 (by convention) while counting starts from 1. In a few Programming Languages, index start from 1 but in almost all standard Programming Languages like Java, C++, Python and Rust, indexing start from 0.

All elements of the array is of same data type that is each element has same memory size. There are different data types like Integer, Float, Double, Character, String and others.

This allows an Array to calculate the memory location of i^th element in constant time O(1) provided the memory location of the first element is given and the size of the data type (for the element) is known.

So if we are given the following:

• Memory location of Element 1 (Index 0): X
• Size of Data Type of elements in the array: Y

Then, memory location of Element Z is:

Memory location of element Z = X + (Y * (Z-1))

Memory location of element Z = X + (Y * Index of Element Z)

As we have the memory location of the element, we can access it instantly in RAM (Random Access Memory). This is known as Random Access Memory. As we will see later, this is not exactly constant time.

Properties of an Array are:

• Array is defined by the starting memory location and size of the data type it is supporting.
• All elements are of same data type. More specifically, all elements should have the same memory size.
• We can calculate the memory location of i^th element is constant time.
• All elements are placed contiguously in memory.

Multi-Dimensional Array

Array can be multi-dimensional.

The simple case is of 2D array. It represented as array[][] of size A1 x A2. The total number of elements become A1 * A2.

A 2D array of size 3x3 looks like this:

arr[3][3] = 
[ a00, a01, a02 ]
[ b10, b11, b12 ]
[ c20, c21, c22 ]

An element array[i][j] denotes the element at j^th index of the row with i^th index. So, array[1][2] = element at index 2 of row at index 1 (that is 2^nd row) = b12.

Similarly, we have 3D array like array[][][] of size A1 X A2 X A3.

All multi-dimensional arrays are stored as 1-dimensional array. You can learn more about this idea in this article on: Row major and Column major order.

Implementation of Array

All Programming Languages support Array natively so you can use it directly. Usually, the syntax is as follows (in Java and C++):

int N = 100;
int array[] = new int[N];

In C, array is used as follows:

int N = 100;
int array[N];

In most Programming Languages, the syntax is similar. The ideas are more important which will make you a Great Software Developer.

If we want a custom implementation, we can build over the basic support, we can use the following class definition:

public class Array {

    private final E[] a;
    private int size;
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

It has:

• An array "a" of data type E
• A data member "size" to prepare the current total size of array. This enables you to get the current size in constant time O(1) and is used in member functions like Insert and Delete.
• A data member "MAX_ARRAY_SIZE" to maintain the maximum size that can be acheived. This is not ensure there is no runtime errors.

Set an Element

We can set an element of an array directly at a particular index. This is because random access at a given address is instant and fetching and writing data at the position is also a constant time operation.

Using the standard array support, one can get the data at i^th index as follows:

int data = array[i];

To set a specific data at a particular index, the syntax is as follows:

array[i] = data;

If you would like to support a set member function to set an element at a particular index for your custom implementation of Array, then:

• We need two inputs: input element, index where the element is to be set.
• Check if the given index is valid. This is done in the function rangeCheck().
• Get the old value at the given index. If no element is present, return a default value.
• Set the new element at the given index.
• Return the old value as a convention.

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

Following is the implementation of rangeCheck():

private void rangeCheck(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException(index);
}

Add an element in Array

To add an element, we set the new element at the index (size + 1). The steps are:

• Ensure (size + 1) is a valid index. We can do this with a separate function ensureCapacityInternal().
• Directly, set the new element at the last index that is the size of array. Note array starts at index 0.
• Return true to ensure the add operation is successful.

Following is a sample implementation:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

Note the functionality of ensureCapacityInternal() can be expanded for different variants of array which we will discuss in later chapters.

Get element at an Index

Using the standard array support, one can get the data at i^th index as follows:

int data = array[i];

If you would like to support a get member function to fetch an element at a particular index for your custom implementation of Array, then we can use this approach:

public E get(int index) {
    rangeCheck(index);
    return a[index];
}

• Using rangeCheck(), we ensure the index is valid and we do not fetch an invalid memory location. If we fetch an invalid memory location, then it may result in memory occuption issues that is Runtime Errors and bring the program execution to a sudden halt.

Delete by Index

To delete an element at a particular index, we can simply set a default value or NULL at the given index but we have to move the other elements one by one to maintain the continuous nature of array.

As we have to shift the remaining elements forward, the time complexity is O(N) on average. The worst case time complexity is O(N) while the best case is O(1) in which case we delete the last element.

Using the standard array support, one can delete the data at (index+1)^th index as follows:

public void delete_by_index(int index, int array[]) {
    int size = array.length;
    for(int i = index; i < size-1; i++) {
        array[i] = array[i+1];
    }
}

The steps to delete by index in our custom array implementation is as follows:

• Check index is valid (using rangeCheck)
• Get the previous value at the given index.
• Move the remaining elements by one position to the left.
• return the previous value as a confirmation of deletion

Following is the custom implementation:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null;

    return oldValue;
}

Remove by Element

If we want to delete a specific element, then we need to find the element in the array and then, delete the element at the index we found.

Using the standard array support, one can delete the element E as follows:

public void remove(int E) {
    int size = array.length;
    for(int i = 0; i < size; i++) {
        if(array[i] == E) {
            // We covered this function
            delete_by_index(i);
            size--;
            i--;
        }
    }
}

The steps to delete by element in our custom array implementation is as follows:

• Handle the case of element == NULL separately
• Traverse through the elements one by one and if the element matches, delete it by index.

Following is the custom implementation:

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                remove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                remove(index);
                return true;
            }
    }
    return false;
}

With this article at OpenGenus, you must have the complete idea of Array Data Structure.