ArrayList v LinkedList speed comparison

[Richard Hayward]

On account of the different ways in which they implement the List interface, I understand that in theory:
ArrayList should be faster doing get() operations
LinkedList should be faster doing add() & remove() operations.
So, I thought I'd write a test to see if that really does happen.

import java.util.*;

class ArrayList_v_LinkedList{

  private static final int BIG_NUMBER = 100000;

  static void reportInsertTime(String type, List<Integer> list){
    long startTime = System.nanoTime() ;
    for(int i=0; i<BIG_NUMBER; i++){
      list.add((int) Math.random()*list.size(), new Integer(i));
    }
    System.out.printf("Time taken for %d %s insertions = %10d\n", BIG_NUMBER, type, System.nanoTime() - startTime);
  }
  static void reportGetTime(String type, List<Integer> list){
    int size = list.size();
    long startTime = System.nanoTime() ;
    for(int i=0; i<BIG_NUMBER; i++){
      Integer j = list.get((int) Math.random()*size);
    }
    System.out.printf("Time taken for %d %s gets = %10d\n", BIG_NUMBER, type, System.nanoTime() - startTime);
  }
  static void reportRemoveTime(String type, List<Integer> list){
    long startTime = System.nanoTime() ;
    for(int i=0; i<BIG_NUMBER; i++){
      list.remove((int) Math.random()*list.size());
    }
    System.out.printf("Time taken for %d %s removes = %10d\n", BIG_NUMBER, type, System.nanoTime() - startTime);
  }

  public static void main(String[] args){
    List<Integer> arrayList = new ArrayList<Integer>();
    List<Integer> linkedList = new LinkedList<Integer>();
    //compare timings for insertion
    reportInsertTime("ArrayList ", arrayList);
    reportInsertTime("LinkedList", linkedList);
    //compare timings for get
    reportGetTime("ArrayList ", arrayList);
    reportGetTime("LinkedList", linkedList);
    //compare timings for remove
    reportRemoveTime("ArrayList ", arrayList);
    reportRemoveTime("LinkedList", linkedList);
  }
}

The program prints how long it takes for a large number of add() operations on an ArrayList and a LinkedList, allowing comparison of the two.
Similarly get() and remove().

Time taken for 100000 ArrayList  insertions = 5647663879
Time taken for 100000 LinkedList insertions =   45197644
Time taken for 100000 ArrayList  gets =   17387964
Time taken for 100000 LinkedList gets =   16693183
Time taken for 100000 ArrayList  removes = 5272101064
Time taken for 100000 LinkedList removes =   20390021

Interestingly, as expected, for add() & remove(), LinkedList is much faster.
However, contrary to my expectation, and despite repeating the test several times, there is almost no difference as far as get() is concerned, and often ArrayList.get() seems slightly slower.

Is there something wrong with the way I'm testing get() performance, or in reality is there not much difference between the two?

[Jeanne Boyarsky]

Richard Hayward wrote:Is something wrong with the way I'm testing get() performance, or in reality is there not much difference between the two?

Actually yes.

This doesn't do what you think it does. It always gets the 0th index in the list.

Integer j = list.get((int) Math.random()*size);

If you change the line to this, you get an actual random index:

Integer j = list.get((int) (Math.random()*size));

With the newly added parens, the output is:
Time taken for 100000 ArrayList  insertions =  726069004 Time taken for 100000 LinkedList insertions =    7607797 Time taken for 100000 ArrayList  gets =    9990203 Time taken for 100000 LinkedList gets = 4290769138 Time taken for 100000 ArrayList  removes =  714337606 Time taken for 100000 LinkedList removes =    4753193

Where ArrayList get is MUCH faster. LinkedList is really good at getting the first element. Since your test was inadvertently asking for the first element on each time through the loop, you never hit the cost of LinkedList gets.

ps - I gave you a cow for the excellent question including all the relevant information.

[Richard Hayward]

Jeanne Boyarsky wrote:
If you change the line to this, you get an actual random index:

Integer j = list.get((int) (Math.random()*size));

Ah, yes! Thank you Jeanne.

I'd made that same error at 3 points in my code, which I've now corrected. I also made a minor adjustment to exclude time spent finding out the list sizes, in case that is an expensive operation.

import java.util.*;

class ArrayList_v_LinkedList{

  private static final int BIG_NUMBER = 100000;

  static void reportInsertTime(String type, List<Integer> list){
    long totalTime = 0; 
    long startTime;
    for(int i=0; i<BIG_NUMBER; i++){
      int index = (int) (Math.random()*list.size());
      //don't include time spent finding out how big the list is
      startTime = System.nanoTime() ;  
      list.add(index, new Integer(i));
      totalTime += (System.nanoTime() - startTime);
    }
    System.out.printf("Time taken for %d %s insertions = %12d\n", BIG_NUMBER, type, totalTime);
  }
  static void reportGetTime(String type, List<Integer> list){
    int size = list.size();
    long startTime = System.nanoTime() ;
    for(int i=0; i<BIG_NUMBER; i++){
      int index = (int) (Math.random()*size);
      Integer j = list.get(index);
    }
    System.out.printf("Time taken for %d %s gets = %12d\n", BIG_NUMBER, type, System.nanoTime() - startTime);
  }
  static void reportRemoveTime(String type, List<Integer> list){
    long totalTime = 0;
    long startTime;
    for(int i=0; i<BIG_NUMBER; i++){
      int index = (int) (Math.random()*list.size());
      //don't include time spent finding out how big the list is
      startTime = System.nanoTime();
      list.remove(index);
      totalTime += (System.nanoTime() - startTime);
    }
    System.out.printf("Time taken for %d %s removes = %12d\n", BIG_NUMBER, type, totalTime);
  }

  public static void main(String[] args){
    List<Integer> arrayList = new ArrayList<Integer>();
    List<Integer> linkedList = new LinkedList<Integer>();

    //compare timings for add
    reportInsertTime("ArrayList ", arrayList);
    reportInsertTime("LinkedList", linkedList);

    //compare timings for get
    reportGetTime("ArrayList ", arrayList);
    reportGetTime("LinkedList", linkedList);

    //compare timings for remove
    reportRemoveTime("ArrayList ", arrayList);
    reportRemoveTime("LinkedList", linkedList);
  }
}

Running this amended code, as you say, ArrayList.get is much faster than LinkedList.get, irrespective of the List size.

As previously, I was expecting LinkedList.add to be fastest, since all it has to do is adjust a pointer, pointing to the next element,  at the point where the insertion is made. Similarly with LinkedList.remove. The mental picture I have of these same operations on an ArrayList involves shifting the whole lot in memory.

However, that's not the case.

Time taken for 10 ArrayList  insertions =       117333
Time taken for 10 LinkedList insertions =        52240
Time taken for 10 ArrayList  gets =        34082
Time taken for 10 LinkedList gets =        31009
Time taken for 10 ArrayList  removes =        33526
Time taken for 10 LinkedList removes =        36039

Time taken for 1000 ArrayList  insertions =      3713574
Time taken for 1000 LinkedList insertions =      3530322
Time taken for 1000 ArrayList  gets =       451454
Time taken for 1000 LinkedList gets =      1555785
Time taken for 1000 ArrayList  removes =      2812922
Time taken for 1000 LinkedList removes =      3074138

Time taken for 100000 ArrayList  insertions =   2953297942
Time taken for 100000 LinkedList insertions =  39271723841
Time taken for 100000 ArrayList  gets =     24645870
Time taken for 100000 LinkedList gets = 139448096336
Time taken for 100000 ArrayList  removes =   2722850794
Time taken for 100000 LinkedList removes =  61213830894

For larger List sizes, LinkedList adds & removes seem to be slower than those of ArrayList.

[Jeanne Boyarsky]

Richard Hayward wrote:For larger List sizes, LinkedList adds & removes seem to be slower than those of ArrayList.

Right. Because you are trying to add to a random position in the LinkedList. Which means the LinkedList has to use the slow "get" to find the right spot and then do a quick insert. If you were trying to always add to the end, you'd see a faster time.

Compare the add with these two and see how much faster it is for linked list
list.add(new Integer(i));
list.add(index, new Integer(i));

I used the below harness and got:
Time taken for 100000 ArrayList: random index  insertions =    355068666
Time taken for 100000 LinkedList: random index  insertions =  16926676282
Time taken for 100000 ArrayList: insert at end insertions =     10364420
Time taken for 100000 LinkedList: insert at end  insertions =      6117165

Add	ArrayList	LinkedList
At random index	355068666	16926676282
At end	10364420	6117165

As you can see, both benefit from always adding at the end. LinkedList way more so than ArrayList.

public class PlayTest {

	private static final int BIG_NUMBER = 100000;
	 
	  static void reportInsertTimeInsertingAtRandomIndex(String type, List<Integer> list){
	    long totalTime = 0; 
	    long startTime;
	    for(int i=0; i<BIG_NUMBER; i++){
	      int index = (int) (Math.random()*list.size());
	      //don't include time spent finding out how big the list is
	      startTime = System.nanoTime() ;  
	      list.add(index, new Integer(i));
	      totalTime += (System.nanoTime() - startTime);
	    }
	    System.out.printf("Time taken for %d %s insertions = %12d\n", BIG_NUMBER, type, totalTime);
	  }
	  
	  static void reportInsertTimeInsertingAtEnd(String type, List<Integer> list){
		    long totalTime = 0; 
		    long startTime;
		    for(int i=0; i<BIG_NUMBER; i++){
		      int index = (int) (Math.random()*list.size());
		      //don't include time spent finding out how big the list is
		      startTime = System.nanoTime() ;  
		      list.add(new Integer(i));
		      totalTime += (System.nanoTime() - startTime);
		    }
		    System.out.printf("Time taken for %d %s insertions = %12d\n", BIG_NUMBER, type, totalTime);
		  }
	  
	 
	  public static void main(String[] args){
	    List<Integer> arrayList = new ArrayList<>();
	    List<Integer> linkedList = new LinkedList<>();
	 
	    //compare timings for add
	    reportInsertTimeInsertingAtRandomIndex("ArrayList: random index ", arrayList);
	    reportInsertTimeInsertingAtRandomIndex("LinkedList: random index ", linkedList);
	    reportInsertTimeInsertingAtEnd("ArrayList: insert at end", arrayList);
	    reportInsertTimeInsertingAtEnd("LinkedList: insert at end ", linkedList);
	 
	  }
}

[Richard Hayward]

Jeanne Boyarsky wrote:you are trying to add to a random position in the LinkedList. Which means the LinkedList has to use the slow "get" to find the right spot and then do a quick insert.

ok, I was overlooking that fact.

Those timings make sense to me now.

Thanks for your help Jeanne.
Most instructive.

[Sudd Ghosh]

I am coming back to Java Ranch after almost a decade.
Very good and useful discussion on the performance of ArrayList versus LinkedList. So, as I  understand, LinkedList is good for adding/removing to/from the end or beginning of a list, and "get" from the end and beginning. For any other indexed get, add or remove operation, ArrayList is still better, since LinkedList has to do the indexed get first for any operation, which is expensive.

[Sresh Rangi]

A problem with these benchmarks is that the effect of JIT compilation and GC collection can affect the results. Here, it's the one that runs first that's slower.

With:

reportInsertTimeInsertingAtEnd("ArrayList: insert at end  ", arrayList);
reportInsertTimeInsertingAtEnd("LinkedList: insert at end ", linkedList);

I get:

Time taken for 100000 ArrayList: insert at end   insertions =     10262753
Time taken for 100000 LinkedList: insert at end  insertions =      4809160

and with:

reportInsertTimeInsertingAtEnd("LinkedList: insert at end ", linkedList);
reportInsertTimeInsertingAtEnd("ArrayList: insert at end  ", arrayList);

I get:

Time taken for 100000 LinkedList: insert at end  insertions =     10586098
Time taken for 100000 ArrayList: insert at end   insertions =      4895989

I tried this JMH benchmark:

@Warmup(iterations=5)
@Measurement(iterations=20)
@Threads(1)
public class PlayTest {
	public static final int BIG_NUMBER = 100000;

	@Benchmark
	public int arrayList() {
		List<Integer> list = new ArrayList<>();
		for(int i=0; i<BIG_NUMBER; i++){
			list.add(new Integer(i));
		}
		return list.size();
	}
	
	@Benchmark
	public int linkedList() {
		List<Integer> list = new LinkedList<>();
		for(int i=0; i<BIG_NUMBER; i++){
			list.add(new Integer(i));
		}
		return list.size();
	}

	public static void main(String[] args) throws RunnerException {
		Options options = new OptionsBuilder()
			.include(PlayTest.class.getSimpleName())
			.build();

		new Runner(options).run();
    }
}

With results (higher is better):

Benchmark             Mode  Cnt     Score   Error  Units
PlayTest.arrayList   thrpt    2  2121.545          ops/s
PlayTest.linkedList  thrpt    2  1556.116          ops/s

So adding to the end of an ArrayList is faster.

ArrayLists do need to be resized as elements are added, but the time between each resize increases exponentially as the size increases. This gives a constant time per element added.

Also, the elements in an ArrayList are stored in an array which keeps all the elements together in RAM. A resize is just copying a contiguous block of memory from one location to another, which computers do all the time.

With a LinkedList, you need to update the previous pointer, and the current pointer, and allocate a new object for the new node. Which is more of an overhead per item.