Array Data Structure: With Sketches and Examples
Tags: beginners, programming, java, datastructures
Published: 2023-07-19 13:32:20

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

```java
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.

```java
// 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 the million items in an array sequentially in an `int[] array`. This can be achieved easily by following the declaration and initialization with values.

```java
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.


![Array with 6 elements](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ztqdyncnzilnof5bg3vi.png)

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.

![Sketch of array elements stored in RAM](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ulqfkaqelru2eyrxdr2b.png)

## 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?

```java
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.

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

Arrays with `char` datatype and `String` class is as follows.

```java
// 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`.


![Array Capacity](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mycslmt2o63xeuskxnji.png)

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

```java
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.

```java
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 is `10`, but no items are added. Technically we can say the length is `0`.

```java
int[] A = new int[10];
```

![Array with capacity N](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ulwdg435wem95kv0nt82.png)

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

```java
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`.


![Array capacity and size difference](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rsuf0szl05w9g8jo9nco.png)

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.length` where `A` the Array's name is.

```java
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

```java
// Array Capacity is 10
```

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

```java
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

```java
// Array length is 4
// Array Capacity is 10
```