How To Construct An Array-Like Data Structure?
Tags: beginners, programming, java, javascript
Published: 2023-07-25 04:13:32

You will learn to implement a custom array-like data structure and basic array operations.

## Introduction
Before you start solving array problems, understanding and implementing an array-like data structure is a good practice.

This lesson teaches you how to implement common array operations, such as inserting an element, removing an element, getting an element, finding the length of the array, and printing elements of the array.

## What are we building?
We are going to build an array from scratch that contains some of the most common array operations, as discussed above.

We will also learn how to convert the fixed-size array into a dynamic array by tweaking a method. This is the concept of dynamic arrays: `LinkedList`, `ArrayList`, and a few more complex data structures.

Every requirement in software is divided into pieces, we work on each piece, and finally, we bring them all together. So let's break down the requirements.

## Problem statement
Build an array from scratch and store elements in it. The array should allow inserting, deleting, getting, and printing elements.

```java
Input:
CREATE -> 10 // create an array with capacity 10
INSERT -> {1, 2, 3, 4, 5} // insert these elements
DELETE -> 2 // remove 2nd index element
GET -> 0 // print 0th element
SIZE -> `.size()` // should print how many items currently an array has
PRINT -> // print all elements shown in output
 
Output: 
{1, 2, 4, 5, 0, 0, 0, 0, 0, 0}
```

## Requirements breakdown
When asked a question or given a problem, write down the requirements on paper.

Our requirements are:
1. Create an array.
2. The array should have the following methods.
  * `insert()`
  * `remove()`
  * `get()`
  * `size()`
  * `print()`
3. Make the array resizable automatically (covered in next article release).
4. Error handling (optional, but it adds value when you work with the interviewer in building an array).
We have our requirements. Let's break down the problem.

Always break the problem into smaller chunks. It will be easy to build smaller parts and combine them to complete the requirement.

## Array Construction
## Creating an array
Create an array with two fields/properties `int[] data` and `size`. A constructor to initialize the array size.

```java
public class Array {
  private int[] data;
  private int size;

  public Array(int capacity) {
    data = new int[capacity];
    size = 0;
  }
}
```
We initialized `size = 0`, for our zero index-based arrays. When we insert elements into an array, we are inserting them from the index `0`.

We created a base `Array` class, we need to write some of the basic array operations we need to perform on the custom array data structure we created.

## Insert an element
We need to write a method that inserts items into our array.

```java
public void insert(int element) {  
  data[size] = element;  
  size += 1;  
}
```
Or you can use specify the short-hand syntax:

```java
public void insert(int element) {  
  data[size++] = element; 
}
```
We initialized the array size with `0` in the constructor. So the first element gets stored in `0`th index.

When we call `data[size] = element`, we are storing an item in the array right at the `0`th index.

In the next line, we have `size += 1`, which increments the size variable from `0` to `1`. So the next item gets stored in the next slot.

What if we want to insert elements in the middle index or starting index? do we need to replace that element in that slot? or should we shift the elements and insert an element in the slot?

In the upcoming lessons, you will learn how to write shifting algorithms in an array to insert elements.😅


## Remove an element at a specific index
Our array-like data structure should handle removing items.

What if the `index` provided to the `remove()` method is either negative or more than the size of the array?  We run into `ArrayIndexOutOfBoundsException`.

If the index provided is either negative or more than the size of the array, we purposefully throw `IndexOutOfBoundsException()`. Or we can add a message to our logger by providing the error message that prints on the console or application logs.

```java
if (index < 0 || index >= size) {  
  throw new IndexOutOfBoundsException();
}
```

After our error handling is in place, we can remove an element from the index and shift all the array elements to the left.

Anything else we need to take care of? We need to decrement the `size` variable value by `1` using `size--`.

With all these changes in place, `remove()` method looks like this:

```java
public void remove(int index) {  
  if (index < 0 || index >= size) {  
    throw new IndexOutOfBoundsException();  
  }
  
  for (int i = index; i < size; i += 1) {
    data[i] = data[i + 1];
  }
  size--;  
}
```
So why are we shifting elements?

Suppose we want to delete/remove elements in the middle or starting index? as discussed above. In that case, we need to delete the element from the given index and shift all the right elements to the left by one position to fill the deleted slot.

In the upcoming lessons, you will learn how to write shifting algorithms in an array. 😅

## Get an item at a specific index
This is no different from the above explanation. We need to check if the given is either negative or more than the size of the array.  In either case, we run into `ArrayIndexOutOfBoundsException`.

The method looks like this:

```java
public int get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  
  return data[index];
}
```

## Size of array
This is quite straightforward. In all the array operations, we decrement the size when we need to remove/delete an element and increment the size when we add a new element to the array. So returning the `size` directly gives us the result.

```java
public int size() {  
  return size;  
}
```

## Print array items
A simple for-loop to iterate through all the array elements and display them.

```java
public void print() {
  for (int i = 0; i < data.length; i += 1) {
    System.out.println(data[i]);
  }
}
```
The same code with enhanced for-loop is:

```java
public void print() {
  for (int el : data) {
    System.out.println(el);
  }
}
```

## Final-look at our custom array-like DS
All these smaller chunks are combined, and the final array we built is:

```java
package dev.ggorantala.ds.arrays;

public class Array {
  private int[] data;
  private int size;

  public Array(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  public void insert(int element) {
    data[size] = element;
    size++;
  }

  public boolean isOutOfBounds(int index) {
    return index < 0 || index >= size;
  }

  public void remove(int index) {
    if (isOutOfBounds(index)) {
      throw new IndexOutOfBoundsException();
    }

    for (int i = index; i < size; i += 1) {
      data[i] = data[i + 1];
    }
    size--;
  }

  public int get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    return data[index];
  }

  public int size() {
    return size;
  }

  public void print() {
    for (int i = 0; i < data.length; i += 1) {
      System.out.print(data[i] + ", ");
    }
  }
}
```

## Array execution class
Let us create an array with `capacity` as `10` and insert `5` numbers in it, the `size` of the array becomes `5`.

## Illustration's
A simple illustration is as follows:


![Basic Array Like DS](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jo08jcuizqx9dc9uw5lz.png)

Another illustration that clarifies the difference between `capacity` and `size` of the array.

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

What do you think is stored in the index 5 to index 9? <mark>The answer is zeros</mark>.

So `0`'s are stored from the index `5` to `9`. So when you access `A[6]` you get `0`, for `A[2]` you get `3`, and so on.

In the above, we have constructed an `Array` class and basic operations `insert`, `remove`, `get`, and `size` etc. Let us test each of the methods to ensure nothing is breaking in our code.

## Code
Following is the execution class

```java
package dev.ggorantala.ds.arrays;

public class ArrayExecution {
  private static final int[] INPUT = new int[] {1, 2, 3, 4, 5};

  public static void main(String[] args) {
    Array array = new Array(10);
    for (int value : INPUT) {
      array.insert(value);
    }

    array.remove(2); // removed element `3` from array

    System.out.println(array.get(0)); // 1
    System.out.println(array.size()); // 4

    // The extra o's are because of the array capacity which is 10
    array.print(); // 1, 2, 4, 5, 0, 0, 0, 0, 0, 0
  }
}
```

## Explanation
`Array array = new Array(10);` creates an array with a capacity `10`.

The input array we declared holds `5` elements.

```java
private static final int[] INPUT = new int[] {1, 2, 3, 4, 5};
```

Using a simple for-loop, we are storing the `INPUT` data into our newly created `array` instance variable.

```java
for (int value : INPUT) {
  array.insert(value);
}
```
We removed an element at the index `2` using `array.remove(2);`.

Finally, we called `get`, `size` and `print` methods to display data on the console.

Hurrah! You just implemented your first data structure in computer science and successfully tested it.