java

use starter code

In class, we implemented an IntArrayList class which internally had an array of integers but made it easy to add new elements to the end. We saw that after improvements, add ing n elements to an IntArray would only take O(n) time. It accomplished this by doubling the underlying size of the array and copyine 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 2n nd element was added, 47 th, 31, and so on down to the starting the of the array. Every time the array runs out of space, if needs to copy all the elements from the old array to the new array. However, even as n becomes very large and this series becornes arbitrarily lone, n+2n+4n+nn+16n+2n. in other words, the total number of elements we need to copy over the lifetime of an IntArraylist is bounded above by a linear function of the total number of elements added to it. (Allocating the array each time we copy is additional work which depends on the memory allocation algorithm used, but it will be efficient enough that it won't change the linear bound.) Your touk improve IALL ist by creating an addiefore method. Instead of adding an element to the end, addBefore adds it to the beginning, at poslition 0 , causing all existing elements to move forward (their position Increased by 1). However, like add, your addiefore method must also guaransee that onlo.(n) time is nceded to serformn add Aefores and adds. To accomplish this, as with add, most calls to addBefore must execute very quickly, in O(1) constant time, meaning that you can't just shift all the elements forward by 1 each call. The changes you make to IAL. Ist 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 copled. There are several ways to accomplash this task. Perhaps the eaclest: double the array when you hit the beginning, but instead of copying the old array to the beginning of the new array, copy it to the second half (leaving all the unused spoces at the end), Yoe will also need to change the implementation of rome other methods (element positions may noloneer di rectly correspend to array indexes) and add an additional instance field (to track extra information). The existing methods should continue to have their existing O runtimes as seen in the corment and they must continue to work along with the new addBetore method. Stert with the IAli ist imolementotion found on Canvas, which will resemble In tarraylist from dass. It will have an enipty addibefore method which you will need to fal in. A tester program will be released which will attempt to empirically teat that your program takes only O(n) time to perferm n addefore and adds (after testing that it seems to work; along with verifying that the other methods seem to work). EOTRA CREDIT 3 POINIS: Notice that the obeve technigue will enun outel space" when there in extra room left on the onoosite end of the array. Instead, we one whole array before trissering any coeving focosening 0(n) ecrformance, starting wath leneth 41. publie class IALISt f THIS COOF IS FOR REFEREMCR ONY Y DO. NCT USF. private int[] a; II Underlying array private int length: /f Nueber of added elenents in a public Ialist() \{ length =j if start with no added elenents in a a= new int [4];// a little roon to grow 3 pub1ic int get(1nt 1) {1/ Retrleve an added eleaent, o(1) 1f (1// Retrieve the elenent at position i pub1ic int size() f // mumber of added elenests, o(1) return length; // The number of added elenents 1 public void set(int 1 , int x)f(// Kodify an existing elenent, o(1) 14(1n length) f throw new Indexoutofebundsfixception (1); 7 a[1] =x; // Change the existine elenent at position 1 tot x public vold add(int x)(// Add an elesont to the end, o(n) for n if (length >o a.length) 1 If Create new array of double the length int [] b = new int [a. length 2] : II Copy the eleeents of a to the corresponding inderess of b for (int 1=0; 1 a. length; 1+) ) ( y b[1]=a[1]: If Reassign a reference to b 3 a a bi If place x at the ens of the riacist a[length =x; II trerease length by 1 Iength = length +11 3 j