Array List Vs. Linked List

Question

So I've been tasked an assignment to compare LinkedLists and ArrayLists for two different things.

part 1) randomly select locations inside the list and increment those values by 1 for each list type

part 2) double each list size by adding random locations, and then immediately remove the same amount of random locations bring the list down to original size.

I feel I've accomplished this pretty well but my teacher is saying part 1 ArrayList should be faster (which it is in my code). He is saying LinkedList should be wayyy faster in part 2, which its the exact opposite for me... its way slower.. I've adding in SYSO's at different locations to verify that the lists are being modified correctly and everything and cant figure out why its not working out the way he says it should be.

can anyone spot what I've done wrong (if anything?). Thank you so much

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import javax.swing.JOptionPane; public class LinkedListVersusArrayList { public static void main(String[] args) { long startTime, endTime, duration; List<Double> LL = new LinkedList<Double>(); ArrayList<Double> AL = new ArrayList<Double>(); int size = Integer.parseInt(JOptionPane.showInputDialog("Pick a list size (whole number only please)")); //fills the Linked List with random doubles for (int i = 0; i < size; i++){ LL.add(Math.random()); } //fills the ArrayList with random doubles for (int i = 0; i < size; i++){ AL.add(Math.random()); } // //Part 1 // System.out.println("\nPART 1:\nBoth lists are now full of random numbers. \nI will now cycle through " + "and incremiment random locations " +size+ " times for each list.\n"); //testing the LinkedList first for random access startTime = System.nanoTime(); for (int i = 0; i < size; i++){ int x = (int)(LL.size()*Math.random()); double y = LL.get(x); LL.set(x, y+1); } endTime = System.nanoTime(); duration = (endTime - startTime); System.out.println("Linked List took: " +(duration/1000000) +" milli seconds"); //testing the ArrayList now for random access startTime = System.nanoTime(); for (int i = 0; i < size; i++){ int x = (int)(AL.size()*Math.random()); double y = AL.get(x); AL.set(x, y+1); } endTime = System.nanoTime(); duration = (endTime - startTime); System.out.println("Array List took: " +(duration/1000000) +" milli seconds"); // //Part 2 // System.out.println("\nPART 2:\nBoth lists will now get "+size+" slots added to them in random locations.\n" + "After this is complete, we will remove "+size+" slots from each list at random\n"); //testing the LinkedList first for random adding/subtracting startTime = System.nanoTime(); //add for (int i = 0; i < size; i++){ int x = (int)(LL.size()*Math.random()); LL.add(x, 1.0); } //delete for (int i = 0; i < size; i++){ int x = (int)(LL.size()*Math.random()); LL.remove(x); } endTime = System.nanoTime(); duration = (endTime - startTime); System.out.println("Linked List took: " +(duration/1000000) +" milli seconds"); //testing the ArrayList now for random adding/subtracting startTime = System.nanoTime(); //add for (int i = 0; i < size; i++){ int x = (int)(AL.size()*Math.random()); AL.add(x, 1.0); } //delete for (int i = 0; i < size; i++){ int x = (int)(AL.size()*Math.random()); AL.remove(x); } endTime = System.nanoTime(); duration = (endTime - startTime); System.out.println("Array List took: " +(duration/1000000) +" milli seconds"); } 

}

Answer 1

Apart from all the microbenchmarking issues which your code doesn't control for, your teacher's expectations for case 2 are also wrong. He is disregarding the cost of accessing a random element of LinkedList (the prerequisite to inserting at that spot) and overestimating the cost of inserting into the ArrayList. The cost of copying contiguous blocks of memory is much lower than the cost of chasing a long chain of pointers, which is what is required to access a random element of the LinkedList.

In reality LinkedList has a very narrow area of application where it is any improvement over ArrayList. For example, you could try to insert only near the front of the list. This way you'll emphasize the cost of moving elements in ArrayList and de-emphasize the cost of accessing a member of LinkedList.