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.

Input:CREATE->10// create an array with capacity 10INSERT->{1,2,3,4,5}// insert these elementsDELETE->2// remove 2nd index elementGET->0// print 0th elementSIZE->`.size()`// should print how many items currently an array hasPRINT->// print all elements shown in outputOutput:{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/propertiesint[] data andsize. A constructor to initialize the array size.

publicclassArray{privateint[]data;privateintsize;publicArray(intcapacity){data=newint[capacity];size=0;}}

We initializedsize = 0, for our zero index-based arrays. When we insert elements into an array, we are inserting them from the index0.

We created a baseArray 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.

publicvoidinsert(intelement){data[size]=element;size+=1;}

Or you can use specify the short-hand syntax:

publicvoidinsert(intelement){data[size++]=element;}

We initialized the array size with0 in the constructor. So the first element gets stored in0th index.

When we calldata[size] = element, we are storing an item in the array right at the0th index.

In the next line, we havesize += 1, which increments the size variable from0 to1. 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 theindex provided to theremove() method is either negative or more than the size of the array? We run intoArrayIndexOutOfBoundsException.

If the index provided is either negative or more than the size of the array, we purposefully throwIndexOutOfBoundsException(). 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){thrownewIndexOutOfBoundsException();}

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 thesize variable value by1 usingsize--.

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

publicvoidremove(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException();}for(inti=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 intoArrayIndexOutOfBoundsException.

The method looks like this:

publicintget(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException();}returndata[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 thesize directly gives us the result.

publicintsize(){returnsize;}

Print array items

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

publicvoidprint(){for(inti=0;i<data.length;i+=1){System.out.println(data[i]);}}

The same code with enhanced for-loop is:

publicvoidprint(){for(intel: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:

packagedev.ggorantala.ds.arrays;publicclassArray{privateint[]data;privateintsize;publicArray(intcapacity){data=newint[capacity];size=0;}publicvoidinsert(intelement){data[size]=element;size++;}publicbooleanisOutOfBounds(intindex){returnindex<0||index>=size;}publicvoidremove(intindex){if(isOutOfBounds(index)){thrownewIndexOutOfBoundsException();}for(inti=index;i<size;i+=1){data[i]=data[i+1];}size--;}publicintget(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException();}returndata[index];}publicintsize(){returnsize;}publicvoidprint(){for(inti=0;i<data.length;i+=1){System.out.print(data[i]+", ");}}}

Array execution class

Let us create an array withcapacity as10 and insert5 numbers in it, thesize of the array becomes5.

Illustration's

A simple illustration is as follows:

Another illustration that clarifies the difference betweencapacity andsize of the array.

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

So0's are stored from the index5 to9. So when you accessA[6] you get0, forA[2] you get3, and so on.

In the above, we have constructed anArray class and basic operationsinsert,remove,get, andsize etc. Let us test each of the methods to ensure nothing is breaking in our code.

Code

Following is the execution class

packagedev.ggorantala.ds.arrays;publicclassArrayExecution{privatestaticfinalint[]INPUT=newint[]{1,2,3,4,5};publicstaticvoidmain(String[]args){Arrayarray=newArray(10);for(intvalue:INPUT){array.insert(value);}array.remove(2);// removed element `3` from arraySystem.out.println(array.get(0));// 1System.out.println(array.size());// 4// The extra o's are because of the array capacity which is 10array.print();// 1, 2, 4, 5, 0, 0, 0, 0, 0, 0}}

Explanation

Array array = new Array(10); creates an array with a capacity10.

The input array we declared holds5 elements.

privatestaticfinalint[]INPUT=newint[]{1,2,3,4,5};

Using a simple for-loop, we are storing theINPUT data into our newly createdarray instance variable.

for(intvalue:INPUT){array.insert(value);}

We removed an element at the index2 usingarray.remove(2);.

Finally, we calledget,size andprint methods to display data on the console.

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