Part A. Write a test program that stores 5 million integers in a linked list and
ID: 3541725 • Letter: P
Question
Part A.
Write a test program that stores 5 million integers in a linked list and test the time to traverse the list using an iterator vs. using the get(index) method.
My Program:
import java.util.*;
public class IteratorsOnLinkedLists
{
public static void main(String[] args)
{
Random rnd = new Random();
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 0; i < 5000000; i++)
list.add(rnd.nextInt());
System.out.printf("List contains %d values ", list.size());
Integer value = new Integer(0);
long start = System.currentTimeMillis();
for(int i = 0; i < 5000000; i++)
value = list.get(i);
long stop = System.currentTimeMillis();
System.out.printf("Elapsed time is %.3f seconds ", (stop-start)/1000);
ListIterator<Integer> listIterator = list.listIterator();
start = System.currentTimeMillis();
while(listIterator.hasNext())
value = listIterator.next();
stop = System.currentTimeMillis();
System.out.printf("Elapsed time is %.3f seconds ", (stop-start)/1000);
}
}
Explanation / Answer
Mistakes You did
You generated random numbers. They could be anything. If the list has big random numbers, it ll be a problem to assign it to integer variable value. It ll consume more time. So it ll increase the time alot. I have generated all integers in the range from 1 to 99 only. They ll repeat. You can increase the value. So ll increase the time.
Iterator method is inbuilt in java class. So it ll take very very less time when compared to for loop get(i) method.
To iterate through get(i) method, it ll take may be an hour or two as it has to do 5000000 iterations. Iterator is inbuilt so it ll do it in less than a second.
I dont know if you have the patience to let the code running for an hour. So I just changed the positions of for loop and iterator method. I have put iterator method first and then the for loop method. So that at least you ll get to see the time taken by the iterator method. If you let the code run for an hour or may be two hours, you ll also get the output of get(i) method.
Using iterator method is so fast that it ll print 0 seconds to iterate( REMEMBER IT IS BECAUSE THIS IS INBUILT IN JAVA)
If you want more precise details, then print in milliseconds and not seconds. See in the print statement, you have divided by 1000. Remove that divided by 1000. You ll get the output in milliseconds. It ll be somewhere near about 200 milliseconds.
Your print statement was also incorrect. Everything is corrected.
Kindly check the code
Code
import java.util.*;
public class IteratorsOnLinkedLists
{
public static void main(String[] args)
{
int value =0;
long start;
long stop;
Random rnd = new Random();
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 0; i < 5000000; i++){
list.add(rnd.nextInt(99-1) + 99);
}
System.out.printf("List contains %d values ", list.size());
ListIterator<Integer> listIterator = list.listIterator();
start = System.currentTimeMillis();
while(listIterator.hasNext()){
value = listIterator.next();
}
stop = System.currentTimeMillis();
System.out.println("Elapsed time in seconds using iterator method is "+ (stop-start)/1000);
start = System.currentTimeMillis();
for(int i = 0; i<list.size(); i++){
value =list.get(i);
}
stop = System.currentTimeMillis();
System.out.println("Elapsed time in seconds using for loop is "+ (stop-start)/1000);
}
}