Compsci 100, Fall 2009, Timing Lists

The chart and table of values below are from adding values to the front and back of a LinkedList and an ArrayList using the code below. Questions about the code follow the code and timing results.

ListSplicer complete Java code.

public double addFront(List<String> list, int n){ double start = System.currentTimeMillis(); for(int k=0; k < n; k++){ list.add(0,new String("hello"+k)); } double end = System.currentTimeMillis(); return (end-start)/1000.0; } public static void main(String[] args){ ListMaker maker = new ListMaker(); for(int k=10000; k <= 200000; k+= 10000){ List<String> linked = new LinkedList<String>(); List<String> array = new ArrayList<String>(); double ltime = maker.addFront(linked,k); double atime = maker.addFront(array,k); System.out.println(k + "\t" + ltime + "\t" + atime); } }
Adding to front (#elements in thousands)
add to front count add to front

  1. Why is it possible to pass both ArrayList and LinkedList arguments to the method addFront?
  2. What argument to list.add ensures the element added is at the front of the list?

  3. Based on the chart and data, how long will it take using the same computer and the same code to add 400,000 elements to the front of both an ArrayList and a LinkedList (justify your answer)?
  4. Explain why adding to the front of an ArrayList, which requires shifting every element to the right, is a quadratic operation. Use math and words to justify your reasoning.
  5. The granularity of the timing code isn't completely precise, what individual timings for adding to the front of a LinkedList are "suspect" even though the general trend is reasonable (why)?
  6. Consider the code below that removes the first element of a list until the list has only one element. For ArrayList objects removing the first element requires shifting all elements one place to the left. In a LinkedList no shifting is required. Explain why you think the graphs of time for removing will be similar in shape to those for adding to the front.

    public double removeFirst(List<String> list) { double start = System.currentTimeMillis(); while (list.size() != 1){ list.remove(0); } double end = System.currentTimeMillis(); return (end-start)/1000.0; }
  7. The time for finding/accessing the kth element of an ArrayList is independent of k, so that the time to access the element with index 10,000 is the same as the time to access the element with index zero. For a LinkedList the time is proportional to k so that accessing the ten-thousandth element will take a thousand times longer than accessing the tenth element. However, removing the kth element is independent of k for a LinkedList but proportional to k for an ArrayList. The code below removes the middle element until a list has only one element. This consists of finding the middle element and then removing it. public double removeMiddleIndex(List<String> list) { double start = System.currentTimeMillis(); while (list.size() != 1){ list.remove(list.size()/2); } double end = System.currentTimeMillis(); return (end-start)/1000.0; }
    Find and Remove Middle Element (#elements in thousands)
    remove middle count remove middle

    1. Explain the shape of the curves (why are they quadratic)?
    2. How long will the code take to execute for a list with 160,000 elements (both array and linked) justify your answers.
    3. Provide a reasonable explanation for why the array times are faster than the linked list times. Try to develop something plausible, that fits the facts and evidence.