In previous post, we compared * LinkedList* and

*in deletion operations using JMH.*

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

*behave when we need to*

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

**. Let’s see why they behave like that.**

*LinkedList*### 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
is an abstraction of a pure Java array, we don’t need to do any transformation.*ArrayList* - 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

**behave when we need to**

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

**. Let’s see why they behave like that.**

*ArrayList*### 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

**behave when we loop using a simple**

*LinkedList***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,

**will do the following:**

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

**behave when we loop using a simple**

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

**. Let’s see why they behave like that.**

*for*### 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**, the difference is that the loop is using a Iterator to go through the list.`for`

- 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**. 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,`for`

**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

**are similar when we talk about**

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

**, we can conclude that we should**

*LinkedList***choose a list based on which use cases we are going to need**.

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

[…] Part 4: ArrayList vs LinkedList: Get, Contains and Sort […]

LikeLike

[…] Part 4: ArrayList vs LinkedList: Sort, Get and Iteration […]

LikeLike

[…] Part 4: ArrayList vs LinkedList: Sort, Get and Iteration […]

LikeLike