Introduction To Array Data Structure

Introduction To Array Data Structure

This article will dive deep into arrays introduction on the following topics -

  1. What is an Array?
  2. Declaration and initialization.
  3. ArrayIndexOutOfBounds Exception
  4. Print Elements.
  5. Strengths.
  6. Weaknesses.
  7. Complexity analysis of each array operation.

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?

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 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. Instead, we store the items in an array int[] arrayThis 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 0th index. In Java, integers take 4 bytes, so the memory addresses of each adjacent element are added by 4 bytes.

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 numbers are stored in memory and addressed in binary.

Screenshot-2022-08-25-at-14.01.18

32 digit representation of 1, 2, 3, 4, etc… the addresses are 100, 104, 108, 112 etc.

Array 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.

// 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};

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

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

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].

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:

  1. TC -  O(N)
  2. SC - O(1) - No algorithmic memory is used here. We just used the input A[] memory, hence Constant time.  

Strengths

  1. Fast Lookups: Retrieving the element at a given index takes O(1) time, regardless of the length of the array.
  2. Fast Appends: Adding a new element at the end of the array takes O(1) time if the array has space.

Weaknesses

1. Fixed Size:

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

2. Memory unused or 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 wasted (integer takes 4 bytes).

3. 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 and create a new array, copy the old array elements and add new elements. The time complexity is O(n).

4. Costly Inserts:

Inserting an element at the end of the array takes O(1) time. 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 0​th​ index in the array (prepending), so we have to "scoot over" everything in the array. 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 }.

I recommend you read Array insertions and shifting algorithms(link below) with a clear explanation with code snippets and sketches to understand why these inserts are expensive at the start and middle.

Array Insertions and Shifting algorithms
This article details array capacity vs length and shifting algorithms to insert an element at the array’s start, middle, and end with complexity analysis.

5. 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 0theindex.

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

Arrays: Worst-case time complexities (Chart)

HTML Table

Operation Worst-Case Time Complexity
Lookup/access a value at a given index O(1)
Update a value at a given index O(1)
Insert at the beginning/middle O(N)
Insert at the end for dynamic array O(1)
Insert at the end for Static array O(N)
Append at the end O(1)
Delete at the beginning/middle O(N)
Delete at the end O(1)
copying the array O(N)