Question

Introduction In this lab we are looking at using an ArrayList in place of a Linked List. You may not know all of the LinkedList methods, but you can infer what they do. RemoveFirst removes the first element, getFirst returns the first, and addLast adds an element to the end of the list. Your task is to change the list from a Linked List to and ArrayList, and rewrite the code so that it still works about the same The Program This code is computing prime numbers. The algorithm is as follows: Take a collection of positive integers. Find the largest integer in the collection. Compute the greatest factor by taking the square root of the largest integer. For every possible integer factor between 2 and the greatest factor: Find and remove every integer from the collection that a. is a multiple of that factor, and b. is not equal to that factor As you can see, you have been given code that implements this algorithm. It uses a LinkedList and a nested loop control structure to remove all non-primes from a collection of numbers. You should run it right away and verify that it runs fairly quickly and prints out prime numbers. To Get Credit Bare minimum: Change the code as indicated in the comments. Change the list variable to be of datatype List and have it refer to an ArrayList object instead of a LinkedList. Modify the rest of the code so that you still print out all the prime numbers between 1 and 100000. Your code may take a while to run. Show your TA your code and some of your output. Good: Change the algorithm to use the fast indexing of an array list. Instead of removing elements on each iteration of the inner loop and adding them back to the end, just scan through index by index and remove from the middle when necessary. Also change the printing loop similarly. You should see that this code runs faster.

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class ListPractice {
  
   private static final int[] arr = new int[100000];

   public static void main(String[] args) {
       for(int i=0; i<100000; i++)
           arr[i] = i;
      
       //TODO comment out this line
       LinkedList<Integer> list = new LinkedList<Integer>();
      
       //TODO uncomment this line
       //List<Integer> list = new ArrayList<Integer>();
      
       //TODO change the rest of the code as necessary to make this program work
      
       //let's generate some prime numbers
      
       //start with some numbers
       for(int i : arr)
           list.add(i);
       //compute the largest factor for these numbers
       int maxVal = list.getFirst();
       for(Integer i : list)
           if(i > maxVal)
               maxVal = i;
       int maxFactor = (int)Math.ceil(Math.sqrt(maxVal));
       //for every factor between 2 and maxFactor
       for(int factor = 2; factor <= maxFactor; factor++) {
           //check each Integer in the list
           int num = list.size();
           for(int i=0; i<num; i++) {
               //remove it
               Integer toCheck = list.removeFirst();
               //if it is not a multiple of factor, or is equal to factor, add it to the back
               if(toCheck == factor || toCheck % factor != 0)
                   list.addLast(toCheck);
           }
       }
       //print them out!
       while(!list.isEmpty())
           System.out.println(list.removeFirst());
   }

  

}

------------------------------

Please solve the program above by using java language.

Answer 1

import java.util.List; import java.util.ArrayList; //import java.util.LinkedList; class ListPractice { private static final int[] arr = new int[100000]; public static void main(String[] args) { for(int i=0; i<100000; i++) arr[i] = i; //TODO comment out this line //LinkedList<Integer> list = new LinkedList<Integer>(); //TODO uncomment this line List<Integer> list = new ArrayList<Integer>(); //TODO change the rest of the code as necessary to make this program work //let's generate some prime numbers //start with some numbers for(int i : arr) list.add(i); //compute the largest factor for these numbers int maxVal = list.get(0);//update:passing index of first element to get() for(Integer i : list) if(i > maxVal) maxVal = i; int maxFactor = (int)Math.ceil(Math.sqrt(maxVal)); //for every factor between 2 and maxFactor for(int factor = 2; factor <= maxFactor; factor++) { //check each Integer in the list int num = list.size(); for(int i=0; i<num; i++) { //remove it Integer toCheck = list.get(i); // update: passing index to get() ith element from list //if it is not a multiple of factor, or is equal to factor, add it to the back if(toCheck != factor && toCheck % factor == 0) { list.remove(i); i--; num--; } } } //print them out! for(int i=0;i<list.size();i++) System.out.println(list.get(i)); } }

Above code contains all the necessary changes to use ArrayList replacing LinkedList.

getFirst(), addLast() & removeFirst(): these methods are not available for ArrayList.

I have used below methods of ArrayList:

get(int index) to retrieve i-th element (0 based index) and remove(int index) to delete element from i-th index.

remove() operation is expensive in ArrayList in terms of time because after every deletion, all the elements to the right of deleted element are shifted to the left by 1.

So instead of removing element every time and adding it again, I have updated the condition to check if current element shoud be deleted or not. If condition is true then the element will be deleted once and no addition operation is needed now and after deleting element decrement the size and index by 1 because size will be reduced by 1 and also the elements will be shifted to the left by 1.

Finally to print the elements, call get() on list and print the value returned by this method.

ArraList is based on indexing hence retrieval is achieved in constant time (O(1)) which is much better than LinkedList where it is O(n).

Older code was also faster because remove operation in LinkedList can be done in much lesser time than in ArrayList because no shifting of elements is required after removing element from LinkedList. That is why without optimization previous code was still working fine. So if we change LinkedList to ArrayList simply without optimizing remove and add operations, it will take too much of time to execute and print the result. Hence with ArrayList, this optimization is required.

As a summary, i have reduced remove operations (expensive) and removed add operation again and again. To retrieve the element from list used get() method instead of calling remove() method.