Arrays From Zero To Mastery: A Complete Notes For Programmers

Introduction

Arrays are built in most programming languages. They are the most fundamental data structures of all in computer science. Arrays are the building blocks for many other, more complex data structures.

Why do we need an array to store elements? Why can't we make use of int primitive type?

Why not make use of primitives?

In Java int takes 4 bytes. So the declaration below occupies 4 bytes of memory.

int a = 100;

What if we want to store six int values (or 24 bytes)? We need to use six different variables individually, each occupying 4 bytes so that the total will be 6 * 4 = 24 bytes.

// each of the following occupies 4 bytes, which is 6 * 4 bytes
int a1 = 100;
int a2 = 200;
int a3 = 300;
int a4 = 400;
int a5 = 500;
int a6 = 600;

Creating six different variables is a bit dirty and not a good idea. What if we wanted to store a million entries, are we supposed to create a million different variables? 😢 Isn't this bad coding?

Instead, we store a million items in an array sequentially in an int[] array. This can be achieved easily by following the declaration and initialization with values.

int[] array = {100, 200, 300, 400, 500, 600};

Isn't the array beautiful? 🤩

What is an Array?

In Java and many other languages, arrays are static(fixed size). Array organizes items sequentially, one after another, in memory.

The items could be Integer, String, Object, – anything. The items are stored in contiguous (adjacent to each other) memory locations.

Each position in the array has an index, starting at the 0^th index. In Java, integers take 4 bytes, so the memory addresses of each adjacent element are added by 4 bytes.

Sketch

A simple sketch of this is as follows.

If we say our array memory, location/address starts from 100, then the following integer address will start from 104(100+4) bytes, and so on.

In the above illustration/figure, we have an array with 6 elements in it, with a memory address pointed from 100 to 120. So theoretically, anything that we store after this array takes the address from 124.

Note: In Java, we have to specify the size of the array ahead of time before initializing the array.

We knew everything on the computer is stored in bits 0 or 1. Let us see how these array numbers from the above sketch are stored in memory and addressed in binary.

Declaration and initialization

Consider an array A[] that has 5 elements. To access the last element of the array, we use A[4].

With this knowledge, if N is the array length, then (N-1) is how we access the last element. There are two ways we can declare and initialize the array in Java.

What happens if we declare an array as follows?

int[] A = new int[3]; 
// stores 3 items, capacity = 3 and size is 0(no items added, so far)

System.out.println(Arrays.toString(A)); // [0, 0, 0]

Initially, we did not add any items to the array, so the array values are defaulted to 0 as seen above.

Let us see another way where we declare and initialize the array.

// approach 1
int[] A = new int[5];

A[0] = 1;
A[1] = 2;
A[2] = 3;
A[3] = 4;
A[4] = 5;

// approach 2
int[] A = {1, 2, 3, 4, 5};

Arrays with char datatype and String class are as follows.

// String arrays
String[] fruits = new String[3]; // contains 3 strings

// char arrays
char[] chars = new char[256]; // contains 256 items

This small illustration helps you understand how we access array elements using their indexes.

How to access elements?

Following is a simple sketch of an array A with a capacity N.

int[] A;

Since arrays in Java starts from 0^th index. If you want to access the first element, you need to give A[0], and A[1] for accessing the second element, and so on A[N-1] to access the last element.

What happens if we do A[-100], A[N], and A[N+1] ? 🤔

You guessed it. We run into ArrayIndexOutOfBoundsException.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100 out of bounds for length 5
	at array.ArrayIntroduction.main(ArrayIntroduction.java:20)

At most, we can access the last element of the array using A[N-1].

How to print array elements

A simple snippet to print the array elements from 0 to (N-1) index.

public class PrintElements {
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5};

        int N = A.length;
        
        for (int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }
    }
}

The time and space complexity to print these array elements are:

Time complexity - O(N) - We iterated over all the array elements of size N, so the time complexity is linear.

Space complexity - O(1) - No algorithmic memory is used here. We just used the input A[] memory, hence Constant time.

Capacity vs. length

How long is an array? 🤔

If someone asks you how long an array is, there could be two possible answers when discussing how long an array is.

1. How many items can an array hold, and
2. How many items currently an array has?

The first point is about capacity, and the second is about length.

Let us create an array A[10] whose capacity is10, but no items are added. Technically we can say the length is 0.

int[] A = new int[10];

Let's insert integers 1, 2, 3, and 4 into the above array.

A[0] = 1;
A[1] = 2;
A[2] = 3;
A[3] = 4;

At this point, the length/size of the array is 4 and the capacity of the array that has room to store elements is 10.

The following code snippets explain the difference between array length vs. capacity.

Capacity

The capacity of an array in Java can be checked by looking at the value of its length attribute. This is done using the code A.lengthwhere A the Array's name is.

public class ArrayCapacityLength {
    public static void main(String[] args) {
        int[] A = new int[10];

        System.out.println("Array Capacity " + A.length); // 10
    }
}

Running the above snippet gives

Array Capacity is 10

Length

This is the number of items currently in the A[] array.

import java.util.Arrays;

public class ArrayCapacityLength {
    public static void main(String[] args) {
        int[] A = new int[10];

        int currentItemsLength = 0;
        for (int i = 0; i < 4; i++) {
            currentItemsLength += 1;
            A[i] = i + 10;
        }

        System.out.println(Arrays.toString(A)); // [10, 11, 12, 13, 0, 0, 0, 0, 0, 0]
        System.out.println("Array length is " + currentItemsLength); // 4
        System.out.println("Array Capacity is " + A.length); // 10
    }
}

Running the above snippet gives

Array length is 4
Array Capacity is 10

Strengths

There are many advantages to using arrays, some of which are outlined below:

1. Fast lookups (random access)
2. Fast appends
3. Simple implementation
4. Cache friendliness

Fast lookups (Random access)

Retrieving the element at a given index takes O(1) time, regardless of the array's length.

For example:

int[] A = {-1, 7, 9, 100, 1072};

The array has five elements, and the length of the array is calculated using, A.length, which is 5. As arrays are zero indexed, the last element is accessed using A[A.length - 1] which is A[4] as shown in the following sketch.

If we access array elements using the index, like A[0] or A[4], it takes a single unit of time or, in big-o terms, constant operation.

A[0]; // -1
A[3]; // 100
A[4]; // 1072
A[5]; // Index out of bounds exception, as there is no A[5] value.

All of the above operations consume a single unit of time which is O(1) time.

Fast appends

Adding a new element at the end of the array takes O(1) time if the array has space.

Let us create an array with a capacity 5 and insert values 100 and 101 at indexes 0 and 1.

The following code explains it.

int[] A = new int[5];

A[0] = 100;
A[1] = 101;

Now if we were to insert a new value into the array, we could do A[2] = 200. Which inserts value 200 at the index 2. This operation consumes a single unit of time which is constant.

This is the reason the appends at the end are fast.

Enough talk. Here is a simple algorithm that creates an array with a size 5, and inserts 100, 101 values into the array. Finally, we insert an element at the array length.

import java.util.Arrays;

public class ArrayAppends {
  public static void main(String[] args) {
    int[] A = new int[5];
    int currentLength = 0;

    // Let us add 2 elements to the array
    for (int i = 0; i < 2; i++) {
      A[i] = i + 100;
      currentLength++; // when i=1, length is set to 2
    }

    System.out.println(Arrays.toString(A)); // [100, 101, 0, 0, 0]
    System.out.println("current array items length " + currentLength); // 2
    System.out.println("Array capacity " + A.length); // 5
    System.out.println(
        "Element insert at end "
            + Arrays.toString(insertAtEnd(A, currentLength))); // [100, 101, 200, 0, 0]
  }

  // Inserting element at the end
  public static int[] insertAtEnd(int[] A, int currentLength) {
    A[currentLength] = 200;
    return A;
  }
}

/* 
Outputs:
[100, 101, 0, 0, 0]
current array items length 2
Array capacity 5
Element insert at end [100, 101, 200, 0, 0]
*/

Simple Implementation

Arrays have a straightforward implementation in most programming languages, making them easy to understand and use.

Cache Friendliness

Elements in an array are stored contiguously in memory, which improves cache performance and can lead to faster access times.

Weaknesses

There are some disadvantages to using arrays, some of which are outlined below:

1. Fixed size.
2. Memory unused or wasted.
3. Size doubling.
4. Costly inserts
5. Costly deletes

Fixed-size

Arrays have a fixed size defined at the time of creation. Adding or removing elements beyond the initial size requires creating a new array and copying the existing elements, which can be inefficient.

You need to specify how many elements you will store in your array ahead of time. (Unless you're using a fancy dynamic array).

int[] A = new int[5]; // contains 5 elements

Memory unused or wasted

If an array's size is larger than the number of elements it contains, memory is wasted.

Imagine an array with a capacity of 5. We have two elements to store in this array, and then we are wasting three unfilled cells and a waste of memory, which means 3*(4 bytes) = 12 bytes of memory is wasted (integer takes 4 bytes).

Size doubling

Let us consider an array with a capacity of 5 elements. But the elements we want to store in this array are more, which means we have to double the size, create a new array, copy the old array elements and add new elements. The time complexity is O(n).

You will learn how to double the array size in the next lessons.

Costly inserts

Inserting/appending an element at the end of the array takes O(1) time. We have seen this in the strengths(fast appends).

But, inserting an element at the start/middle of the array takes O(n) time. Why? 🤔

If we want to insert something into an array, first, we have to make space by "scooting over" everything starting at the index we're inserting into, as shown in the image. In the worst case, we're inserting into the 0th index in the array (prepending), so we have to "scoot over" everything. That's O(n) time.

Inserting an element at the 2nd index and moving the rest of the element right shift each once. The resultant array becomes – { A, B, C, D, E }.

In the next lessons, you will learn more about insertion and shifting algorithms, with clear explanations, code snippets, and sketches to understand why these inserts are expensive at the start and middle.

Costly deletes

Deleting an element at the end of the array takes O(1) time, which is the best case. In computer science, we only care about the worse case scenarios when working on algorithms. But, when we remove an element from the middle or start of the array, we have to fill the gap by scooting over all the elements after it. This will be O(n) if we consider a case of deleting an element from the 0th index.

Deleting an element at the 3rd index and filling the gap by left-shifting the rest of the elements; the resultant array becomes – { A, B, C, D, E }.

Big-O Complexities

The Big-O complexities mentioned above are for basic operations and assume an unsorted array. Some specialized data structures, such as Heaps or HashTables, can provide more efficient alternatives for specific use cases.

In the next lessons, you will learn more about array capacity vs. length, insertions, and deletion algorithms. They are the simplest yet most powerful and helps you when working on array problems.