Array Implementation

What are we building?

We are going to build an array from scratch. Some of Java's most common array operations include adding an element, removing an element at a given index, getting the length of the array and getting an element from a specific index.

We will also learn how to convert the fixed-size array into a dynamic array by tweaking a method.

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.
4. Error handling.

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.

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.

Insert item

We need to write a method that inserts items into our array.

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

We initialized the array size with 0.

When we call data[size] = element, we store an item in the array. size is then incremented, so the next item gets stored in the next slot.

How to resize an array?

In Java, dynamic arrays are implemented using LinkedLists, and Collections.

Arrays have fixed sizes in Java. Let us make this fixed-size array dynamic, but it comes with a cost.

This approach wastes memory, but bear with me. You will learn more about Memory Management later. This is just for your understanding, and traditionally this is how it's done for all the dynamic arrays, like List, HashMap, etc., in Java API.

For each insert, we are incrementing the size variable. So let us check to see when an array is full.

if(size == data.length) {
	// array is full
}

With this knowledge, we can create a new array double the previous size. We then copy this newly created array into the data.

if (size == data.length) {  
	// If the array is full, resize it  
	int[] newData = new int[2 * data.length];  
	System.arraycopy(data, 0, newData, 0, data.length);  
	data = newData;  
}

With all these changes in place, insert method looks something like this:

public void insert(int element) {  
	if (size == data.length) {  
		// If the array is full, resize it  
		int[] newData = new int[2 * data.length];  
		System.arraycopy(data, 0, newData, 0, data.length);  
		data = newData;  
	}  
	data[size] = element;  
	size++;  
}

Remove item

Our array should handle removing items.

Removing an item isn't easy in arrays. Suppose we remove an item from the end of the array; it is ok. But if we remove items from the start/middle of the array, we need to shift all the elements to the left one step from the index we removed the item.

To learn more about the shifting algorithms. Read the following article:

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.

👨🏻‍💻 Gopi GorantalaGopi Gorantala

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 (index < 0 || index >= size) {  
	throw new IndexOutOfBoundsException();
}

So, we need to do the error handling, copy/shift array elements and decrement the size of the array.

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

public void remove(int index) {  
	if (index < 0 || index >= size) {  
		throw new IndexOutOfBoundsException();  
	}  
	System.arraycopy(data, index + 1, data, index, size - index - 1);  
	size--;  
}

Get an item at a specific index

This is no different from the above explanation. Except we only check for 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. We are incrementing/decrementing the size property in all the above operations. Just returning the size will do the trick.

public int size() {  
	return size;  
}

Print array items

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

Final Code

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

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

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

    public void insert(int element) {
        if (size == data.length) {
            // If the array is full, resize it
            int[] newData = new int[2 * data.length];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
        data[size] = element;
        size++;
    }

    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        System.arraycopy(data, index + 1, data, index, size - index - 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.println(data[i]);
        }
    }
}

Execution class

Execution class to test the solution we wrote above.

public class ArrayExecution {
    public static void main(String[] args) {
        Array array = new Array(4);
        for (int i : new int[]{1, 2, 3, 4, 5, 6, 7, 11, 9}) {
            array.insert(i);
        }

        array.remove(4);

        System.out.println(array.get(0)); // 1
        System.out.println(array.size()); // 8
        array.print(); // 1 2 3 4 6 7 11 9 9 0 0 0 0 0 0 0
    }
}

Note: Do not get confused that size is 8 but the capacityof the array is 16. This is the reason you are seeing extra zeros for print() method.

To understand array length vs array capacity. Read the following article.

Introduction To Array Data Structure

This article will dive deep into arrays introduction, array initialization, strengths, and weakness with complexity analysis. You will also see sketches and snippets explaining in detail.

👨🏻‍💻 Gopi GorantalaGopi Gorantala