ArrayList vs LinkedList: Sort, Get and Iteration

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

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:

ArrayList vs LinkedLists performance, sorting

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

ArrayList

Well, let’s use this example:

ArrayList example

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

1. Get the pure Java array:

Pure Java Array

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

Sort the 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:

LinkedList example

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

1.Copy the list into a pure Java array:

Creating a pure Java array from the LinkedList

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

Sort the pure Java array

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

Creating a LinkedList from the pure Java array

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:

ArrayList vs LinkedLists performance, getting from the middle

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

ArrayList

Well, let’s use this example:

ArrayList 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:

Access the 3 index

2. Get the value:

Get the value on the 3 index

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:

LinkedList 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:

Moving from the Head to the 3 index

2. Get the value of the 3 index:

Get the value in the Index reference

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:

ArrayList vs LinkedLists performance, iterating using a normal for

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

ArrayList

Well, let’s use this example:

ArrayList 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:

Access the 0 index

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

Access 1 index

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

Access 2 index

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

Access 6 index

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:

LinkedList 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

Poiting the Index to Head

1.2 Access the value of Index

Access the 0 index

2. For index 1:

2.1 Point a Index reference to the Head

Poiting the Index to Head

2.2 Move the Index reference to the position 1

Move to the Index

2.3 Access the value of Index

Access the 1 index

3. For index 2:

3.1 Point a Index reference to the Head

Poiting the Index to Head

3.2 Move the Index reference to the position 2

Move to the Index

3.4 Access the value of Index

Access the value of 5 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 vs LinkedLists performance, iterating using a foreach

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:

ArrayList 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:

Access the 0 index

2. Move to next, and access it:

Access 1 index

3. Move to next, and access it:

Access 2 index

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

Access 6 index

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:

LinkedList 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

Move to head

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

Move to next to 1 index

4. Move to next, and access it:

Move to next to 2 index

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

Move to next to 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:

ArrayListLinkedList
OperationMethodBestWorstBestWorst
Sortsort(comp)nlogn*nlogn*2n + nlogn* 2n + nlogn*
Get From
Middle
get(size/2)1*1*n / 2n / 2
Normal forfor(assig;cond;inc)nn(n(n – 1) ) / 2(n(n – 1) ) / 2
forEachfor(val:list)nnnn

*: Those are an approach.

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

ArrayListLinkedList
OperationMethodBestWorstBestWorst
Sortsort(comp)O(nlogn)*O(nlogn)*O(nlogn)*O(nlogn)*
Get From
Middle
get(size/2)O(1)O(1)O(n)O(n)
Normal forfor(assig;cond;inc)O(n)O(n)O(n²)O(n²)
forEachfor(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.

3 comments

Leave a Reply to ArrayList vs LinkedList: Deletion – The Coders Tower Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s