Implementation

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 next chapter, "Dynamic Arrays").
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 0th index.

When we call data[size] = element, we are storing an item in the array right at the 0th 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 or starting indexes? 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.

Is there 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 [Final Code]

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] + ", ");
    }
  }
}