Performance of ArrayList vs. LinkedList varies for different machine?

Question

Actually ,I have try an example from this link related proformance of Arraylist vs LinkList .But my issue is that the proformance differ for different machine ,Before i read one question from stackoverflow just like this .

Performance differences between ArrayList and LinkedList

 package com.demo.collections;
 import java.util.ArrayList;
 import java.util.LinkedList;
 public class ArraylistAndLinklist {
 public static void main(String args[]){
 ArrayList arrayList = new ArrayList();
 LinkedList linkedList = new LinkedList();
 // ArrayList add
 long startTime = System.nanoTime();
 for (int i = 0; i < 100000; i++) {
 arrayList.add(i);
 }
 long endTime = System.nanoTime();
 long duration = endTime - startTime;
 System.out.println("ArrayList add: " + duration);
 // LinkedList add
 startTime = System.nanoTime();
 for (int j = 0; j < 100000; j++) {
 linkedList.add(j);
 }
 endTime = System.nanoTime();
 duration = endTime - startTime;
 System.out.println("LinkedList add: " + duration);
 // ArrayList get
 startTime = System.nanoTime();
 for (int k = 0; k < 10000; k++) {
 arrayList.get(k);
 }
 endTime = System.nanoTime();
 duration = endTime - startTime;
 System.out.println("ArrayList get: " + duration);
 // LinkedList get
 startTime = System.nanoTime();
 for (int l = 0; l < 10000; l++) {
 linkedList.get(l);
 }
 endTime = System.nanoTime();
 duration = endTime - startTime;
 System.out.println("LinkedList get: " + duration);
 // ArrayList remove
 startTime = System.nanoTime();
 for (int m = 9999; m >=0; m--) {
 arrayList.remove(m);
 }
 endTime = System.nanoTime();
 duration = endTime - startTime;
 System.out.println("ArrayList remove: " + duration);
 // LinkedList remove
 startTime = System.nanoTime();
 for (int n = 9999; n >=0; n--) {
 linkedList.remove(n);
 }
 endTime = System.nanoTime();
 duration = endTime - startTime;
 System.out.println("LinkedList remove: " + duration);
 }

1st.machine Output:

ArrayList add: 24675693
LinkedList add: 15693734
ArrayList get: 3464166
LinkedList get: 131314610
ArrayList remove: 344500934
LinkedList remove: 127862009

2nd. machine output:

ArrayList add: 13265642
LinkedList add: 9550057.
ArrayList get: 1543352
LinkedList get: 85085551
ArrayList remove: 199961301
LinkedList remove: 85768810

Can someone tell me :

I have some question

1.Why the performance varies for different machine ?

2.Why arraylist add and remove slower than linklist ?

3.Why Arraylist get faster ?

4.In which case linklist should be prefer ?

• SimplyPanda: Presumably different machines have different processing power, and thus complete tasks at different speeds.
• kosa: Lot of things will influence this 1) which JVM? 2) How you are noting these timings (warm up times) 3) What else competing for resource while you are noting these and so on....
• Nishant: Why Arraylist get faster ? because it implements RandomAccess
• telkins: It looks proportional so it seems like your second computer is just faster overall than the first.

Answer 1

1.Why the performance varies for different machine ?

This can be caused by many factors. For this example, the speed of the RAM is likely the largest contributor, however CPU speed, system load, etc. can all effect performance. Differences of this type are fine and expected.

2.Why arraylist add and remove slower than linklist ?

Over this large of a data set, the array list will intermittently run out of space in the array which it holds the data in internally. When this occurs, the array will need to resize, which means creating a new larger array and copying all of the data over (non-trivial task). Removing can require a shift of following elements in the array. This is similar.

3.Why Arraylist get faster ?

Arraylist get can be done in O(1) time (constant time) because it's just an offset memory lookup in an array, internally. A linked list, however, must traverse the list to find that element. This takes O(n) time (linear time).

4.In which case linklist should be prefer ?

If you do more insert/remove operations than lookup, linked lists can be better in performance than an arraylist. Conversely, if you are doing more lookup operations, like update the arraylist will probably give you better performance.

Answer 2

1. because of the speed of the ram (in most cases) or jvm, OS, etc

2. because sometimes the array isnt long enaugh and sometimes its to big -> resizing needs a lot of time

3. Because you can get the data in O(1) time and for your linkedlist your get implementation is bad (you iterate over all nodes till the j th node) every time. Usually u get your iteration data in linkedlist in O(1) but you have O(n)

4. for large data because you don`t have to find a block of ram which is big enough for the data. A linkedlist can split the data over the ram

it helped me to just program a linkedlist and an arraylist by myself to better understand them

• John Allison: Regarding #2: ArrayList does grow in size automatically, but it doesn't shrink automatically. So the reference to 'too big' is incorrect. One should use the trimToSize() method that trims the capacity of an ArrayList instance to be the list's current size.