Measurement Time Does Not Confirm LinkedList Benefits

Question

I read the differences between ArrayList and LinkedList , listed in When to use LinkedList over ArrayList? . I developed a small sample application to test the main advantage of LinkedList , but the results do not confirm that LinkedList outweighs the ArrayList when performing the operation:

 ListIterator.add(E element) 

Here is my code:

 public static void main(String[] args) { int number = 100000; long startTime1 = System.currentTimeMillis(); fillLinkedList(number); long stopTime1 = System.currentTimeMillis(); long startTime2 = System.currentTimeMillis(); fillArrayList(number); long stopTime2 = System.currentTimeMillis(); System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1)); System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2)); } public static void fillLinkedList(int number){ LinkedList<Integer> list = new LinkedList<Integer>(); ListIterator<Integer> it = list.listIterator(); int i = 0; while(i++<number){ it.add(i); } // System.out.println("LinkedList size: "+list.size()); } public static void fillArrayList(int number){ ArrayList<Integer> list = new ArrayList<Integer>(); ListIterator<Integer> it = list.listIterator(); int i = 0; while(i++<number){ it.add(i); } // System.out.println("ArrayList size: "+list.size()); } 

The measurement gives:

 number 10,000 100,000 500,000 1,000,000 5,000,000 ArrayList 7 17 60 77 170 LinkedList 7 21 89 838 4127 

I notice that increasing elements significantly degrades LinkedList performance, and ArrayList provides significantly better behavior. Do I understand something false?

Answer 1

ArrayList is faster when adding an element at the end of the container or very close, since then it does not need to move many elements. It is slow when added in the middle or at the beginning. I changed your loop to the following:

  while(i++<number){ it.add(i); if(i%2 == 0) it.previous(); } 

Now it will always point to the middle of the list . LinkedList runs much faster in this test. Results for 200,000:

 LinkedList needed: 47 ArrayList needed: 4702 

Answer 2

Insertion and deletion at the beginning or in the middle (of an array or list) is a list in which an array is selected.

Answer 3

As I understand it, the advantage of LinkedList is that you enter the value in the given index (say, in the middle or at the beginning). ArrayList will not play on sequential input, as it does not need to change elements.

Once you have completed your lists, as described above, see what you get to insert positions in different places. I modified your example to show an example of where LinkedList wins significantly (at least on my installation):

 public static void main(String[] args) { int number = 5000000; LinkedList<Integer> llist = new LinkedList<Integer>(); ArrayList<Integer> alist = new ArrayList<Integer>(); long startTime1 = System.nanoTime(); fillLinkedList(number, llist); long stopTime1 = System.nanoTime(); long startTime2 = System.nanoTime(); fillArrayList(number, alist); long stopTime2 = System.nanoTime(); System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1)); System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2)); startTime1 = System.nanoTime(); llist.add(1, 4); stopTime1 = System.nanoTime(); startTime2 = System.nanoTime(); alist.add(1, 4); stopTime2 = System.nanoTime(); System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1)); System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2)); } public static void fillLinkedList(int number, LinkedList<Integer> list){ ListIterator<Integer> it = list.listIterator(); int i = 0; while(i++<number){ it.add(i); } // System.out.println("LinkedList size: "+list.size()); } public static void fillArrayList(int number, ArrayList<Integer> list){ ListIterator<Integer> it = list.listIterator(); int i = 0; while(i++<number){ it.add(i); } // System.out.println("ArrayList size: "+list.size()); }