How to Build a Dynamic Array By Using a Static Array in Java
We all know about the basic data structure, which is Array pretty well. And in java they are static. It means we have to allocate memory for the array ahead of time. The memory will define the number of elements that the array can hold. But what if we have know idea about the exact number of elements that we are going to insert before hand. Then the best thing is to have a dynamic array.
A dynamic array automatically grows when we try to make an insertion and there is no space left for the new item. A simple dynamic array can be constructed, by using an array of fixed-size. The elements of the array are stored contiguously, for an instance, if it is an integer type array it will take 4 bytes of space per integer element. The remaining positions towards the end are reserved and unused. New elements can be added to the end of the array until the reserved space is fully utilized. If you still need to add up more elements even after that, the array needs to be resized which is a very expensive task. Usually it doubles its size.
Following is the Figure 1, where you can find the Array class, to model a dynamic behavior by using a static array in Java. Basic array operations are implemented below.
First initialize the array inside the parameterized constructor with the length provided. print() method will display all the elements of the array. In here, you have to concern about having a new variable named count, instead using items.length, otherwise it will end up displaying three zeros when no number is inserted.
Variable count has to be incremented by one whenever new number is inserted. And yes, we are talking about the insert() method. Then most cruical point comes into play. When the array is full what we should do? Simply create a new array making it doubled the size. Then copy all the existing elements to the new array. Then point new array to the existing array. This will make it recursive. Big O Notation for the insertion would be O(n), since we have to copy all the elemnts to the new array which is very expensive.
Next comes the delete method which is removeAt(). This deletes an item based on their index. First make sure the provided index is within the range ( 0 - count ). Then the element based on the index, will be removed and to fill that hole, all the other elements from the right side, should be shifted left accordingly. Next decrement the count by one. Big O Notation for the best case of deleting an element would be O(1), which would be the last element. For the worst case it is O(n), which will be the element at 0th index.
Last implemented method is searching the index by value, indexOf() method. Searching the perticular value through a for loop will give the relevant index. Resulting -1 if not found.
And finally here's the Main test class in Figure 2 to run the code and check the output.
This is all about a brief explanation how you can come up with a dynamic array by using static array features. You can find the code in github from following url : https://github.com/vgunawardana/data-structures.git
