Homework Sourse Homework Sourse

Java and Data structure It is almost Halloween time Three ki

Java and Data structure

It is almost Halloween time. Three kids: Larry, Curly and Moe decide to go trick or treating together dressed as an array, Array List and Linked List respectively. They go to a number of houses and get a piece of candy at each house. When they are done, they talk about their experience and realize that the candy from one of the houses was spoiled. They all go and grab that piece, and throw it away. Then they sit and eat the most recent half of candy that they just collected. Implement this situation in a method. Create an array, Array List and Linked List. The number of houses, and the specific house that had bad candy are input variables. Candy is an object that you can assume is declared and defined. You should \"visit\" each house and add a piece of candy to your list at each \"visit.\" After you have doled out all the candy, remove the piece of candy at the specified \"house\" (location). Then remove the last half of the candy. Assume you have a large number of houses (for instance 100,000), comment on the performance of each of the trick or treaters.

Solution

public static void trickOrTreat(int numberOfHouses, int badCandyIndex){ // initialize the variables Object[] array = new Object[numberOfHouses]; int arrLength = numberOfHouses; // need to hold array length to represent number of candy left ArrayList arrayList = new ArrayList<>(); LinkedList linkedList = new LinkedList<>(); // collect candy // Adding n items to an array takes O(n) // Adding n items to an arrayList takes O(n) // Adding n items to an linkedList takes O(n), But the memory requirements for linkedLinked is higher, since it has to store // additional data for references for(int i = 0; i < numberOfHouses; ++i){ array[i] = new Object(); arrayList.add(new Object()); linkedList.add(new Object()); } // remove bad candy from array // accessing the bad candy takes constant time. But removing it takes O(n) since we need to slide all the elements after that index to fill that void. for(int i = badCandyIndex; i < numberOfHouses - 1; ++i){ array[i] = array[i + 1]; } --arrLength; // removing bad candy from arrayList // It takes O(n) arrayList.remove(badCandyIndex); // removing bad candy from linkedList // It takes O(n) linkedList.remove(badCandyIndex); // removing last half of candy from array (Takes only Constant time) -> O(1) arrLength /= 2; // removing last half of candy from arrayList for(int i = arrayList.size(); i >= arrayList.size() / 2; --i){ // Takes O(n) arrayList.remove(i); } // removing last half of candy from linkedList for(int i = linkedList.size(); i >= linkedList.size() / 2; --i){ // Takes O(n) linkedList.pop(); } }
Java and Data structure It is almost Halloween time. Three kids: Larry, Curly and Moe decide to go trick or treating together dressed as an array, Array List an

Get Help Now

Submit a Take Down Notice
Tutor
Tutor: Dr Jack
Most rated tutor on our site