How To Construct An Array-Like Data Structure?

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.

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.
   A) insert()
   B) remove()
   C) get()
   D) size()
   E) print()
3. Make the array resizable automatically(covered in the dynamic array topic).
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.

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.

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

Or you can use specify the short-hand syntax:

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++, 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.

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:

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:

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.

public int size() {  
  return size;  
}

Print array items

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

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:

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

Array with all operations

All these smaller chunks are combined, and the final array we built is:

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:

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

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

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

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.

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.

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.