Timing analysis of Java’s LinkedList vs. ArrayList. See how long it takes to ent

Question

Timing analysis of Java’s LinkedList vs. ArrayList.
See how long it takes to enter, say 1e7 integers into a LinkedList<Integer> vs. an ArrayList<Integer>. When run, your code should print out the elapsed time after every 100000 insertions. Make sure to use the list’s add method to put the item at the end of the list.
Explain the time difference.
Repeat this by using add to repeatedly insert items at the beginning of the list. You may not want to go all the way to 1e7 with this one. Explain the difference between the two.
Timing analysis of Java’s LinkedList vs. ArrayList.
See how long it takes to enter, say 1e7 integers into a LinkedList<Integer> vs. an ArrayList<Integer>. When run, your code should print out the elapsed time after every 100000 insertions. Make sure to use the list’s add method to put the item at the end of the list.
Explain the time difference.
Repeat this by using add to repeatedly insert items at the beginning of the list. You may not want to go all the way to 1e7 with this one. Explain the difference between the two.
Timing analysis of Java’s LinkedList vs. ArrayList.
See how long it takes to enter, say 1e7 integers into a LinkedList<Integer> vs. an ArrayList<Integer>. When run, your code should print out the elapsed time after every 100000 insertions. Make sure to use the list’s add method to put the item at the end of the list.
Explain the time difference.
Repeat this by using add to repeatedly insert items at the beginning of the list. You may not want to go all the way to 1e7 with this one. Explain the difference between the two.

Explanation / Answer

// Time start insert data into ArrayList

long nano1 = System.nanoTime();

// Ice Barker to print every 100000 insertions
int ice_braker = 100000;
List<Integer> arr = new ArrayList();
for(int i=0;i<1e7 ;++i){
    arr.add(i);
   ice_braker++;
   if(ice_braker == 100000)
   {
       // Will print the time
       System.out.println( (System.nanoTime() - nano1) );
       ice_braker = 0;
   }
}

for(int j: arr){
    ;
}
System.out.println( (System.nanoTime() - nano1) );

// Time start insert data into ArrayList

long nano2 = System.nanoTime();

// Ice Barker to print every 100000 insertions
int ice_braker = 100000;
List<Integer> arrL = new LinkedList();
for(int i=0;i<1e7 ;++i){
    arrL.add(i);
       ice_braker++;
   if(ice_braker == 100000)
   {
       // Will print the time
       System.out.println( (System.nanoTime() - nano1) );
       ice_braker = 0;
   }
}

for(int j:arrL){
    ;
}
System.out.println( (System.nanoTime() - nano2) );

For LinkedList

    * get is O(n)
    * add is O(1)
    * remove is O(n)
    * Iterator.remove is O(1)

For ArrayList

    * get is O(1)
    * add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
    * remove is O(n)
  

An ArrayList is a simpler data structure than a LinkedList. An ArrayList has a single array of pointers in contiguous memory locations. It only has to be recreated if the array is expanded beyond its allocated size.

A LinkedList consists of a chain of nodes; each node is separated allocated and has front and back pointers to other nodes.

So what does this mean? Unless you need to insert in the middle, splice, delete in the middle etc. an ArrayList will usually be faster. It needs less memory allocations, has much better locality of reference (which is important for processor caching) etc.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.