In previous post, we introduced this * List* collection and some implementations like

*and*

**LinkedList***.*

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

**LinkedList**performance using

**addition 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 (You are here)
- Part 3: ArrayList vs LinkedList: Deletion
- 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.

## Adding at the End – `add(type)`

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

*behave when we need to*

**LinkedList****add at the end**:

@Test public void add_end() throws RunnerException, IOException { Utils.populateToFile(); Options opt = new OptionsBuilder() .include( ArrayListVsLinkedListAdditionEndTest.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.add(executionPlan.element); 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.add(executionPlan.element); return list; }

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

Now, let’s see the results:

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

### ArrayList

Well, let’s use this example:

Now, we want to **add a 2 number to the end** of the list. However, this is a pure Java array, it means, we **only have 7 spots for numbers**, nothing more. So, ** ArrayList** will do the following:

1. Creates a new pure Java array with more space:

**NOTE**: ** ArrayList** can choose to increase in different ways,

`list.size()/2`

is the more common.2. Copy the elements from our previous array to the new one:

3. Add the element we requested:

We can conclude:

- In the
**worst case, we need to create a new bigger array**, if we reach the current size, this means, we will reserve more memory than we might not use. - We need to
**copy the whole array in a new one**in the worst case, so, there are**n**operations. - The complexity of this operation is
**O(n)**. - The
**following additions are going to be fast**until we reach the new size. - There is a limit. The max capacity for a
**pure Java array is 2147483639**.

### LinkedList

Well, let’s use this example:

Now, we want to **add a 2 number to the end** of the list. This is the process:

1. Create a new node for the new element:

2. Linking the new node to the **Tail**:

3. Moving the **Tail** to the new node:

We can conclude:

- We only need to
**create a new node and linked to the tail**. - The amount of operations is
**1**. - The complexity of this operation is
**O(1)**. - The size
**limit here is defined by your JVM memory**, there is no other restriction.

## Adding to the Middle – `add(index, type)`

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

**behave when we need to**

*LinkedList***add at the middle**:

@Test public void add_middle() throws RunnerException, IOException { Utils.populateToFile(); Options opt = new OptionsBuilder() .include( ArrayListVsLinkedListAdditionMiddleTest.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.add(list.size() / 2, executionPlan.element); 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.add(list.size() / 2, executionPlan.element); return list; }

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

Now, let’s see the results:

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

### ArrayList

Well, let’s use this example:

Now, we want to **add a 2 number to the middle**, before 9 number of the list. So, ** ArrayList** will do the following:

1. Creates a new pure Java array with with more space:

2. Copy the elements from our previous array to the new one:

3. Moves the elements after the index one position:

4. Insert the element to the empty position:

We can conclude:

- In the
**worst case, we need to create a new bigger array**, if we reach the current size, this means, we will reserve more memory than we might not use. - We need to
**copy the whole array in a new one**in the worst case, so, the amount of operations is**n**. - We need to
**move the elements one position to create an empty space (n/2)** - The total amount of operations needed is
**n + n/2**. - The complexity of this operation is
**O(n)**. **Any insertion will require to move the elements one position**.- There is a limit. The max capacity for a pure Java array is 2147483639.

### LinkedList

Well, let’s use this example:

Now, we want to **add a 2 number before the 9 number **of 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. Creating the new node:

3. Changing references from 5 number and 9 number to the new node:

We can conclude:

- In the
**worst case, we need to move from the head/tail to the index (n/2)**. - The complexity of this operation is
**O(n)**. - We only
**need to create a new node**and linked to the tail. - The size limit here is defined by your JVM memory, there is no other restriction.

## Adding to the Start – `add(0, type)`

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

**behave when we need to**

*LinkedList***add at the start:**

@Test public void add_start() throws RunnerException, IOException { Utils.populateToFile(); Options opt = new OptionsBuilder() .include( ArrayListVsLinkedListAdditionStartTest.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.add(0, executionPlan.element); 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.add(0, executionPlan.element); 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 **add a 2 number to the start**. So, ** ArrayList** will do the following:

1. Creates a new pure Java array with with more space:

2. Copy the elements from our previous array to the new one:

3. Moves the elements after the index, one position, in this case, it needs to move everything:

4. Insert the element at the start:

We can conclude:

- In the
**worst case, we need to create a new bigger array**, if we reach the current size, this means, we will reserve more memory than we might not use. - We need to
**copy the whole array in a new one**in the worst case (**n**). - We need to
**move every element, one position to create an empty**space at the start (**n**). - The complexity of this operation is
**O(n)**. - There is a limit. The max capacity for a pure Java array is 2147483639.

### LinkedList

Well, let’s use this example:

Now, we want to **add a 2 number at the start** of the list. This is the process:

1. Create a new node for the new element:

2. Linking the new node to the Head:

3. Moving the Head to the new node:

We can conclude:

- We only
**need to create a new node**and linked to the head. - The amount of operations is
**1**. - The complexity of this operation is
**O(1)**. - The size limit here is defined by your JVM memory, there is no other restriction.

## Summary

Now, this is a summary of the** amount of operations** in addition between ** ArrayList** and

**:**

*LinkedList*ArrayList | LinkedList | ||||

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

Add At End | add(type) | 1 | n | 1 | 1 |

Add At Middle | add(index, type) | n/2 | n + n/2 | n/2 | n/2 |

Add At Start | add(0, type) | n | n + n | 1 | 1 |

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

**:**

*LinkedList*ArrayList | LinkedList | ||||

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

Add At End | add(type) | O(1) | O(n) | O(1) | O(1) |

Add At Middle | add(index, type) | O(n) | O(n) | O(n) | O(n) |

Add At Start | add(0, type) | O(n) | O(n) | O(1) | O(1) |

## Final Thought

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

**when we talk about addition operations.**

*ArrayList*This means, if you have a use case were you required a constant performance through the additions, you should choose the ** LinkedList**.

In the following post, we are going to talk about deletion operations.

[…] Part 2: ArrayList vs LinkedList: Addition […]

LikeLike

[…] Part 2: ArrayList vs LinkedList: Addition […]

LikeLike

[…] Part 2: ArrayList vs LinkedList: Addition […]

LikeLike