author

Arrays

An Array is a data structure, in fact one of the simplest and most commonly used data structures. If you’ve ever created a software application you’ve probably used one, but do you understand how it works? This article aims to provide a more detailed insight into the implementation of the Array.

What?

Arrays are often instantiated using something like this:

Object[] objectArray = new Object[10]

This statement creates an array which can hold 10 elements, this actually means that 10 contiguous memory locations (basically a block of space) are allocated, these can then be indexed into and assigned to. Each memory location in an array can hold a primitive value (such as a char or int) or hold a reference to an object (a pointer).

Array Memory Block

Space Complexity

Depending on the language there is sometimes a memory overhead in the allocation of the array itself, but in general, the number of memory locations required is equal to the size of the array. This means that arrays have a linear space complexity, O(n), such that an array of n elements will require n memory addresses.

Accessing Elements

In order to access the individual elements we can do something similar to the following:

Object[] objectArray = new Object[10];
Object objectOne = objectArray[0]; //Object at the base memory address + 0
Object objectFive = objectArray[4]; //Object at the base memory address + 4

This snippet shows that we can lookup an item in an array in constant time O(1), it all just boils down to addition. This means that we could have any number of items in our array and it would take the same amount of time to get access a reference to any one of them.

Searching For an Element

When searching though an array, if you can not be sure that the array is sorted, you have to loop though the elements one-by-one until you find the element you are looking for:

Object[] objectArray = new Object[10];
for(int i = 0; i < objectArray.length : ++i) {
    if(objectArray[i] == theObjectWeAreLookingFor) {
        //do something
    }
}

This is a pretty simple algorithm which, in order to guarantee that the element we are looking for is found, needs to iterate through every object in the array. This means that for an array of size n we will need to iterate through the loop n time, making the time complexity of O(n).

Algorithmic Time Complexity

It’s worth mentioning that we may find the element we are looking for prematurely, meaning we could exit the loop early. On average when looking for an element in an unsorted array you should find it in n/2 iterations, so why is the time complexity not O(n/2)? This is because when talking about algorithmic complexity we normally talk about the worst case, as this is the only value that we can reliably make guarantees about. We also normally only take the highest level polynomial in the equation, assuming that the lower orders will be insignificant in comparison. For example, if an algorithm has a time complexity of n2 + 5n + 3 we would say it is in the order of n2, using the Big-Oh notation O(n2) for short.

Length

The length of an array is normally stored on creation, for example, if we were to create an array of size 10 the memory allocated would look something like this:

Array Length

When you call:

array.length

You are merely obtaining the stored value, meaning getting the length of an array has a complexity of O(1).

Summary

To conclude, arrays are blocks of memory which hold values or references to objects. Items within an array can be accessed in constant time, and searched for in linear time.