Array

Motivation

If you're familiar with arrays, then the answer to the motivation question won't come as a surprise. Arrays are used practically everywhere in computing. Okay, although that's a very slight overstatement, arrays are used in so many places that they're generally considered one of the most fundamental data structures.

Arrays are usually used as containers for objects of the same type in many computer programs. Because of this, they're usually baked into the standard library of most modern programming languages. Strings, which are sequences of characters, are fundamentally stored as arrays. Two-dimensional arrays are used in computer vision for matrix operations. Arrays can be used to implement dynamic arrays and linked lists, as we'll see in upcoming sections. And the list goes on.

So it's well worth learning about arrays.

The main idea

An array can be visualised as a container with multiple slots which are right next to each other. Here, we'll discuss a type of array known as a static array and in the next section, we'll discuss dynamic arrays.

A static array is an array with a fixed size. It can only hold objects of the same size, because it's essentially a container of contiguous slots of computer random access memory, or RAM.

Complexity analysis

The space complexity of an array is conceptually simple. In most cases, it's sufficient to say that a static array of size $n$ has a space complexity of $O\left(n\right)$. We're allocating $n$ memory slots and this, by the way, is why we specify the array size when declaring a static array. The computer needs to find a block of unused, uninterrupted memory for the array.

Most computers have direct references to their RAM slots, which means that a given element of a static array can be accessed (and updated) in constant time, or $O\left(1\right)$. Accessing an element of a static array is also known as "indexing". Array indices are usually zero-based, which means that the first slot of the array has index 0.

What if we want to search for a particular value in an array? If all we know is the value we want and we have the array, then we'll have to walk through each element of the array in turn, checking to see if it's equal to the value we're looking for. This will take $n$ steps, where $n$ is the size of the array. Therefore, searching an array is a linear-time operation, or $O\left(n\right)$.

If the array is sorted, we can take advantage of this information and construct an algorithm for searching through the array that takes roughly $\log \left(n\right)$ steps, which is an improvement. One such algorithm is binary search.

How about appending and deleting items? How long would these take? Well this depends. Suppose that the array is an unsorted list of numbers and we need to delete a particular number from the array. Then theoretically, we need to search the entire array until we find the number. This will take $n$ steps in the worst case, where $n$ is the size of the array.

Once we've found the number (if it even exists), we'll need to delete it. Assume that deletion takes constant time. Then we'll need to shift all elements on the right of the deleted number one space to the left. In the worst case, this shifting will take $n$ steps. Therefore, deleting an element from a static array is, theoretically, a linear-time operation, or $O\left(n\right)$.

However, perhaps a more common way of looking at appending and deletion is that, since a static array has a fixed size, it's not possible to add or remove elements. This is exactly the case in Java and we'll assume that this is the case for the rest of the manual, unless otherwise stated.

Key takeaways

So, we've seen that:

• An array is a contiguous block of memory.
• An array holds objects of the same size.
• Accessing elements in an array is super fast (constant-time).
• A trade-off is that we can't append or delete items, since we need to know the size of the array in advance.

One way to overcome the fixed-size limitation is to use a dynamic array, which we'll cover next.