In previous post, we compared LinkedList and ArrayList in deletion operations using JMH.

In this post, we are going to compare ArrayList and LinkedList performance using sort, get and iteration operations.

TRY IT YOURSELF: You can find the source code of this post here.

Java Collections List Series

• Part 1: Java Collections: List
• Part 2: ArrayList vs LinkedList: Addition
• Part 3: ArrayList vs LinkedList: Deletion
• Part 4: ArrayList vs LinkedList: Sort, Get and Iteration (You are here)

Environment

• JDK 11.0.3, OpenJDK 64-Bit Server VM, 11.0.3+7-Ubuntu-1ubuntu218.04.1
• Ubuntu 18.04
• Memory 15,6 GiB
• Processor Intel® Core™ i7-7500U CPU @ 2.70GHz × 4
• Graphics Intel® HD Graphics 620 (Kaby Lake GT2)
• OS 64-bit
• Disk 387,9 GB
• Intellj IDE Community 2018.3

Approach

• We are going to use JMH for the micro benchmark.
• We are going to use a list of 10.000.000 of elements, generated randomly, and we are going to calculate the average response time in 10 iterations.
• As JMH doesn’t allow sharing data between benchmarks, we are going to create a file with the list of elements, and read from it by each benchmark. In that way, we guarantee we are measuring the same scenario.

Sorting – list.sort(comparator)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we need to sort:

  @Test
  public void sort()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListSortTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(arrayListResult.getScore())
            .isLessThan(linkedListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public ArrayList<Integer> arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    list.sort(Comparator.naturalOrder());

    return list;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public LinkedList<Integer> linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    list.sort(Comparator.naturalOrder());

    return list;
  }

TRY IT YOURSELF: You can find this source code here.

Now, let’s see the results:

As we can see, ArrayList is faster than LinkedList. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

Now, we want to sort the list. So, ArrayList will do the following:

1. Get the pure Java array:

2. Use Arrays.sort to sort the pure Java array:

TIP: Remember, sorting is done in situ, that means, it moves the elements from one position to other, but, it doesn’t need to increase or decrease the array structure.

We can conclude:

• As an ArrayList is an abstraction of a pure Java array, we don’t need to do any transformation.
• In the worst case, we just need to apply the sort algorithm
• The amount of operations needed to sort depends on the sort algorithm and how sorted is the list previous to sort, so, the average might be nlog(n)
• The complexity of this operation is O(nlog(n)). This is the typical average case of the best sort algorithm.

LinkedList

Well, let’s use this example:

Now, we want to sort the LinkedList. This is the process:

1.Copy the list into a pure Java array:

2. Sort the pure Java array with Arrays.sort:

3. Build a new LinkedList using the pure Java array already sorted:

We can conclude:

• We need to create a pure Java array first and come back to a LinkedList at the end.
• The amount of operations needed to sort depends on the sort algorithm and how sorted is the list previous to sort, so, the average might be n + (nlog(n)) + n, where we found 2 additional n due to the transformations from and to pure Java arrays.
• The complexity of this operation is O(nlog(n)). This is the typical average case of the best sort algorithm.

Getting from the Middle – get(size / 2)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we need to get an element from the middle:

  @Test
  public void get()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListGetTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(arrayListResult.getScore())
            .isLessThan(linkedListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public Integer arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    return list.get(list.size() / 2);
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public Integer linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    return list.get(list.size() / 2);
  }

TRY IT YOURSELF: You can find this source code here.

Now, let’s see the results:

LinkedList is slower than ArrayList. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

Now, we want to get the 3 index from the list. So, ArrayList will do the following:

1. Access the 3 index of its internal pure Java array:

2. Get the value:

We can conclude:

• In the worst case, we access directly the position.
• The amount of operations is 1.
• The complexity of this operation is O(1).

LinkedList

Well, let’s use this example:

Now, we want to get the 3 index from the list. This is the process:

1. Move to the index from the closest reference (Head or Tail), in this case, Head is closest:

2. Get the value of the 3 index:

We can conclude:

• In the worst case, we need to move from the head/tail to the index
• The amount of operations in the worst case is n / 2
• The complexity of this operation is O(n).

Loop using For – for(assig;cond;inc)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we loop using a simple for statement:

  @Test
  public void normalFor()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListForTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(arrayListResult.getScore())
            .isLessThan(linkedListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public ArrayList<Integer> arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    for(int i = 0; i < list.size(); i++){
      Integer data = list.get(i);
    }

    return list;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public LinkedList<Integer> linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    for(int i = 0; i < list.size(); i++){
      Integer data = list.get(i);
    }

    return list;
  }

TRY IT YOURSELF: You can find this source code here.

NOTE: We decreased the amount of elements here to 100.000 elements due to the huge time complexity we are going to discuss next.

Now, let’s see the results:

LinkedList is slower, pretty slow. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

Now, we want to iterate the list using a normal for. So, ArrayList will do the following:

1. Move to the 0 index and access it:

2. Increase the index in 1, move to the new index, and access it:

3. Increase the index in 1, move to the new index, and access it:

4. Continue doing this until the end of the list:

We can conclude:

• In the worst case, we need to move one by one element until the end of the list
• The amount of operations is n
• The complexity of this operation is O(n).

LinkedList

Well, let’s use this example:

Now, we want to iterate the list using a normal for. This is the process:

1. For index 0:

1.1 Point a Index reference to the Head

1.2 Access the value of Index

2. For index 1:

2.1 Point a Index reference to the Head

2.2 Move the Index reference to the position 1

2.3 Access the value of Index

3. For index 2:

3.1 Point a Index reference to the Head

3.2 Move the Index reference to the position 2

3.4 Access the value of Index

4. Repeat the above process until you reach the end

We can conclude:

• We need by each index, to move the Head to the right position, and access the value.
• This means, we are doing the get process for each index in the list. If the get method requires n operations, and we need to do a get by each index in the list, therefore, the amount of operations is the summation from 1 to n. And that is equivalent to (n(n – 1) ) / 2.
• The complexity of this operation is O(n²).

Loop using ForEach – for(val:list)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we loop using a simple forEach statement:

  @Test
  public void iterator()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListIteratorTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(arrayListResult.getScore())
            .isLessThan(linkedListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public ArrayList<Integer> arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    for(Integer integer : list){
    }

    /*
    for(Iterator<Integer> i = list.iterator(); i.hasNext(); ) {
      Integer item = i.next();
    }
    */

    return list;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public LinkedList<Integer> linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    for(Integer integer : list){
    }

    /*
    for(Iterator<Integer> i = list.iterator(); i.hasNext(); ) {
      String item = i.next();
    }
    */

    return list;
  }

TRY IT YOURSELF: You can find this source code here.

NOTE: The for(val:list) is equivalent to for(Iterator i = list.iterator(); i.hasNext(); )

Now, let’s see the results:

ArrayList is faster, however, there is not a huge difference as we saw in the normal for. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

Now, we want to iterate the list using a forEach. So, ArrayList will do the following

1. Create an iterator for a normal Java array.

2. Move to next, the 0 index and access it:

2. Move to next, and access it:

3. Move to next, and access it:

4. Continue doing this until the end of the list:

We can conclude:

• This behavior is pretty similar to the normal for, the difference is that the loop is using a Iterator to go through the list.
• In the worst case, we need to move one by one element until the end of the list
• The amount of operations is n
• The complexity of this operation is O(n).

LinkedList

Well, let’s use this example:

Now, we want to iterate the list using a forEach. This is the process:

1. Create an iterator for a LinkedList.

2. Move to Head, and access the value

3. Move to next, the 1 index and access it:

4. Move to next, and access it:

5. Continue doing this until the end of the list:

We can conclude:

• The process is pretty different in compare to the normal for. There, we needed to move the index the amount of positions needed to reach the index, each time we need a new position, doesn’t matter if the position is one place forward; Here, the Iterator only moves one position forward each time is asked about Next.
• The amount of operations is n.
• The complexity of this operation is O(n).

Summary

Okey, this is a summary of the amount of operations approx. of sort, get and iteration operations between ArrayList and LinkedList:

		ArrayList		LinkedList
Operation	Method	Best	Worst	Best	Worst
Sort	sort(comp)	nlogn*	nlogn*	2n + nlogn*	2n + nlogn*
Get From Middle	get(size/2)	1*	1*	n / 2	n / 2
Normal for	for(assig;cond;inc)	n	n	(n(n – 1) ) / 2	(n(n – 1) ) / 2
forEach	for(val:list)	n	n	n	n

*: Those are an approach.

And, this is a summary of the Big O complexity of sort, get and iteration operations between ArrayList and LinkedList:

		ArrayList		LinkedList
Operation	Method	Best	Worst	Best	Worst
Sort	sort(comp)	O(nlogn)*	O(nlogn)*	O(nlogn)*	O(nlogn)*
Get From Middle	get(size/2)	O(1)	O(1)	O(n)	O(n)
Normal for	for(assig;cond;inc)	O(n)	O(n)	O(n²)	O(n²)
forEach	for(val:list)	O(n)	O(n)	O(n)	O(n)

*: That depends on the sort algorithm.

Final Thought

As we saw, ArrayList and LinkedList are similar when we talk about sorting, however, the amount of operations is higher in the LinkedList.

In the get operation, ArrayList is the best option to choose.

And finally, about looping, the best option is always to use the forEach. Still, ArrayList is faster.

CAREFUL: do not use a normal for to iterate over a LinkedList, the performance is pretty bad.

After this whole analysis about ArrayList and LinkedList, we can conclude that we should choose a list based on which use cases we are going to need.

There is not a winner, they are only two different implementations.

If you liked this post and are interested in hearing more about my journey as a Software Engineer, you can follow me on Twitter and travel together.