In previous post, we compared * LinkedList* and

*in addition operations using JMH.*

**ArrayList**In this post, we are going to compare * ArrayList* and

**LinkedList**performance using

**deletion 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 (You are here)
- Part 4: ArrayList vs LinkedList: Sort, Get and Iteration

## 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.

## Deleting from the End – `remove(size - 1)`

Now, let’s see the code for measuring how * ArrayList* and

*behave when we need to*

**LinkedList****remove from the end**:

@Test public void remove_end() throws RunnerException, IOException { Utils.populateToFile(); Options opt = new OptionsBuilder() .include( ArrayListVsLinkedListDeletionEndTest.class .getSimpleName()) .detectJvmArgs() .build(); Collection<RunResult> runResults = new Runner(opt) .run(); Result arrayListResult = Utils .find("arrayList", runResults); Result linkedListResult = Utils .find("linkedList", runResults); assertThat(linkedListResult.getScore()) .isLessThan(arrayListResult.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.remove(list.size() - 1); 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.remove(list.size() - 1); return list; }

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

Now, let’s see the results:

That is pretty interesting, ** LinkedList** and

**have pretty much a equal behavior. Let’s see why they behave like that.**

*ArrayList***NOTE**: Careful, if you run those tests multiple times, the result mightn’t be equal

### ArrayList

Well, let’s use this example:

Now, we want to **remove the index 6** of the list. So, ** ArrayList** will do the following:

- Set NULL the 6 position:

2. Change the array size variable from 7 to 6:

**TIP**: In a logic point of view, the ** ArrayList** size is now 6, however, its pure array is 7. That means, the

**next time we need to add a new element**at the end, is going

**to be fast**, there is a position available.

We can conclude:

- In the
**worst case, we just need to set NULL the last 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 **remove the 6 index from** the list. This is the process:

1.Move the Tail one index before:

2. Unlink the previous Tail from the new Tail:

3. The garbage collector is going to reclaim the unlinked node:

We can conclude:

- We only need to
**unlink the node from the Tail**. - The amount of operations is
**1**. - The complexity of this operation is
**O(1)**.

## Deleting from the Middle – `remove(size / 2)`

Now, let’s see the code for measuring how ** ArrayList** and

**behave when we need to**

*LinkedList***remove from the middle**:

@Test public void remove_middle() throws RunnerException, IOException { Utils.populateToFile(); Options opt = new OptionsBuilder() .include( ArrayListVsLinkedListDeletionMiddleTest.class .getSimpleName()) .detectJvmArgs() .build(); Collection<Integer> runResults = new Runner(opt) .run(); Result arrayListResult = Utils .find("arrayList", runResults); Result linkedListResult = Utils .find("linkedList", runResults); assertThat(linkedListResult.getScore()) .isLessThan(arrayListResult.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.remove(list.size() / 2); 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.remove(list.size() / 2); return list; }

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

Now, let’s see the results:

Again, ** LinkedList** and

**have pretty much a equal behavior. Let’s see why they behave like that.**

*ArrayList*### ArrayList

Well, let’s use this example:

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

1. Set NULL the 3 index:

2. Move the whole elements after 3 index one position before:

We can conclude:

- In the
**worst case, we need to move the half of the list one position before.** - The amount of operations is
**n/2**. - The complexity of this operation is
**O(n)**.

### LinkedList

Well, let’s use this example:

Now, we want to **remove 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. Removing the reference from the 3 index, to previous (2) and next (4):

3. Linking the 2 index to 4 index:

4. The garbage collector is going to reclaim the unlinked node:

We can conclude:

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

## Removing from the Start – `remove(0)`

Now, let’s see the code for measuring how ** ArrayList** and

**behave when we need to**

*LinkedList***remove from the start:**

@Test public void remove_start() throws RunnerException, IOException { Utils.populateToFile(); Options opt = new OptionsBuilder() .include( ArrayListVsLinkedListDeletionStartTest.class .getSimpleName()) .detectJvmArgs() .build(); Collection<RunResult> runResults = new Runner(opt) .run(); Result arrayListResult = Utils .find("arrayList", runResults); Result linkedListResult = Utils .find("linkedList", runResults); assertThat(linkedListResult.getScore()) .isLessThan(arrayListResult.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.remove(0); 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.remove(0); return list; }

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

Now, let’s see the results:

** LinkedList** is faster, pretty fast. Let’s see why they behave like that.

### ArrayList

Well, let’s use this example:

Now, we want to **remove the 0 index from the list**. So, ** ArrayList** will do the following:

1. Set NULL the 0 index:

2. Move the whole elements one position before:

2. Change the array size variable from 7 to 6:

We can conclude:

- In the
**worst case, we need to move the whole elements minus one, one position before**. - The amount of operations is
**n-1**. - The complexity of this operation is
**O(n)**.

### LinkedList

Well, let’s use this example:

Now, we want to **remove the 0 index from the list**. This is the process:

1. Move the Head one position forward:

2. Unlink the 0 index from the Head:

3. The garbage collector is going to reclaim the unlinked node:

We can conclude:

- We only need to
**unlink the node from the Head**. - The amount of operations is
**1**. - The complexity of this operation is
**O(1)**.

## Summary

Okey, this is a summary of **the amount of operations** in the deletion operations between ** ArrayList** and

**:**

*LinkedList*ArrayList | LinkedList | ||||

Operation | Method | Best | Worst | Best | Worst |

Remove From End | remove(size-1) | 1 | 1 | 1 | 1 |

Remove From Middle | remove(size/2) | n/2 | n/2 | n/2 | n/2 |

Remove From Start | remove(0) | n-1 | n-1 | 1 | 1 |

Then, this is a summary of **the Big O complexity** in the deletion operations between ** ArrayList** and

**:**

*LinkedList*ArrayList | LinkedList | ||||

Operation | Method | Best | Worst | Best | Worst |

Remove From End | remove(size-1) | O(1) | O(1) | O(1) | O(1) |

Remove From Middle | remove(size/2) | O(n) | O(n) | O(n) | O(n) |

Remove From Start | remove(0) | O(n) | O(n) | O(1) | O(1) |

## Final Thought

As we saw, ** LinkedList** is better than

**when we talk about deletion operations.**

*ArrayList*However, ** ArrayList** behaves similar in 2 of 3 deletion operations.

In the following post, we are going to talk about sort, get and iteration operations.

[…] Part 3: ArrayList vs LinkedList: Deletion […]

LikeLike

[…] Part 3: ArrayList vs LinkedList: Deletion […]

LikeLike

[…] Part 3: ArrayList vs LinkedList: Deletion […]

LikeLike