My question is how to add an element to the beginning of the IntArray, moving forward the existing elements by 1 each

My question is how to add an element to the beginning of the IntArray, moving forward the existing elements by 1 each

CS 143 Assignment 1 IntArray With Prepend DUE on Monday, October 9 at 11:59 PM In class, we implemented an IntArray class which internally had an array of integers but ENHANCEd it by making it easy to add new elements to the end. We saw that adding n elements to an IntArray would only take O(n) time. It accomplished this by doubling the underlying size of the array and copying the old array every time it ran out of space. If n total elements are added to the array, in the worst case, the array might have run out of space and had to copy itself when the very last (nth) element was added, when the-nd element was added, th, th, and so on down to the starting size of the array. Every time the array runs out of space, it needs to copy all the elements from the old array to the new array. However, even as n becomes very large and this series becomes arbitrarily long, n n + n + 4 4 + 2n. In other words, the total number of elements we need to copy is linearly proportional to the total number of elements added to the array. (Allocating the array each time we copy is additional work which depends on the memory allocation algorithm used, but it shouldn't change the linear proportionality.) 2 4 8 16 ENHANCE the implementation of IntArray so that it has a prepend method. Instead of adding an element to the end, prepend adds it to the beginning, at index 0, and causes all existing elements to have their indexes increased by 1. However, like add, your prepend method must also guarantee that only a linear number of elements are copied. The changes you make to IntArray should preserve the property that the get and set methods take a constant amount of time (not proportional to the array size) and the above property of add that only a linear number of elements is copied There are several ways to accomplish this task. Perhaps the easiest: double the array when you hit the end/beginning, but instead of copying the old array to the beginning of the new array, copy it to the middle. We may copy more often, but the series still converges. When wee append, the series will look like this: n +-n + n + n + (-) n + 4n. You will also need to change the implementation of some other methods (because elements will be indexed differently with this ENHANCEment) and add an additional instance field EXTRA CREDIT 3 POINTS: Notice that the above technique will "run out of space" when there is extra room left on the opposite end of the array. Instead, utilize the whole array before triggering any copying. Preserve the performance guarantees. One character hint: % Start with the IntArray implementation found on Canvas, which will resemble what we did in class. It will have an empty prepend method which you will need to fill in. A tester program will be released which will attempt to empirically test that your program's prepend method takes linear time (after testing that it seems to work, along with verifying that the other methods seem to work). For reference, on the next page is a program listing for IntArray as implemented in class