Question

Why is thesize saved prior to entering the for loop? 2. what is the running time of removefirsthalf if lst is an arraylist? 3. what is the running time of removefirsthalf if lst is a linkedlist?

Answer 1

After entering the loop, it should use the correct list size and the loop will be affected if the remove call changes the size of the list. If lst is an Arraylist the running time of removefirsthalf is O (n^2). So when the beginning is removed the next element will move forward. If lst is a LinkedList which is a dynamic structure the running is O (n) for removefirsthalf